# Iterative improvement

From CS 61A Wiki

**Iterative improvement** is a technique that involves updating an initial guess until it reaches the correct solution. The two major components are an `update`

function and a `done`

function.

The general pattern is:

def iter_solve(guess, done, update): while not done(guess): guess = update(guess) return guess

In practice, the loop may continue forever and not get closer to the solution. To prevent this, we can (1) impose a maximum number of iterations and (2) use a `close`

function (instead of a `done`

function) that checks if the guess is within some tolerance of the solution. In code:

def iter_solve(guess, close, update, iteration_limit=32): while not close(guess): if iteration_limit <= 0: raise ValueError("failed to converge") guess = update(guess) iteration_limit -= 1 return guess

## Example

*Main article: Newton's method#Implemented with iterative improvement*