Iteration and Recurrence Algorithms

The Central Idea

Suppose a sequence is defined by

The recurrence tells us the mathematical relationship.

An algorithm describes the procedure:

1. start with \(4\);
2. add \(3\);
3. record the new value;
4. repeat until the desired term is reached.

This generates

The recurrence is the rule; the iteration is the repeated execution of that rule.

What Is Iteration?

Iteration is the repeated application of a procedure or transformation.

If

then the function \(f\) is applied again and again:

Each new output becomes input for the next step.

What Is a Recurrence Algorithm?

A recurrence algorithm is a step-by-step procedure for generating terms from a recurrence relation.

A recurrence algorithm usually specifies:

• the starting state;
• the update rule;
• the order in which updates occur;
• a stopping condition;
• the output to record or return.

Mathematical Rule Versus Algorithm

Consider

The recurrence is concise mathematical notation.

An algorithmic description is:

1. set the current value equal to \(2\);
2. multiply the current value by \(2\);
3. add \(1\);
4. replace the old value with the new value;
5. repeat as needed.

Both describe the same process from different viewpoints.

The Idea of State

The state is the information that must be remembered from one step to the next.

For

only the most recent term is needed.

Thus the state may consist of a single value:

State for a Second-Order Recurrence

For

the next term depends on two previous terms.

Therefore, the state must remember both:

After calculating \(a_n\), the state shifts forward.

State Update

A state update replaces the current stored information with the information needed for the next iteration.

For Fibonacci-type iteration,

becomes

The new pair contains the two most recent terms.

Example: Iterating a First-Order Recurrence

Let

and

Then

Therefore,

Indexing the Update Correctly

The recurrence

says that the value at the next index is calculated from the current one.

If \(n=0\), then

If \(n=1\), then

Careful index tracking prevents off-by-one errors.

Loops

In computational thinking, repeated execution is often organized as a loop.

A loop repeats an update until a specified condition is satisfied.

Conceptually:

Count-Controlled Iteration

Sometimes the number of repetitions is known in advance.

For example, to calculate \(a_{10}\) from

we need

updates.

This is a count-controlled iteration.

Condition-Controlled Iteration

Sometimes we do not know in advance how many repetitions will be needed.

Suppose

and we want the first term exceeding \(1000\).

We repeatedly double until

The stopping rule depends on a condition rather than a predetermined number of steps.

Stopping Conditions

A stopping condition tells an algorithm when iteration is complete.

Common stopping conditions include:

• reaching a specified index;
• exceeding a threshold;
• falling below a tolerance;
• detecting repetition;
• reaching a fixed number of iterations.

Example: Stop at a Threshold

Let

Find the first term greater than \(20\).

Iterate:

Therefore, the first term exceeding \(20\) is

Iteration Tables

A table helps track the state of an iterative process.

For

we may record:

Pseudocode

Pseudocode describes an algorithm in structured language without requiring the exact syntax of a programming language.

For

pseudocode might say:

value = 4
repeat 9 times:
    value = value + 3
output value

After nine updates, the output is \(a_{10}\).

Pseudocode Is a Mathematical Representation

Pseudocode is useful because it makes procedural structure explicit.

A recurrence answers:

Pseudocode answers:

Both are legitimate representations of the same mathematical process.

From an Explicit Formula to an Algorithm

Not every sequence requires recurrence.

Suppose

To generate the first ten terms, an algorithm can loop over

and calculate

independently at each step.

This is iterative computation without recursive dependence.

Direct Computation Versus Sequential Computation

An explicit formula often allows direct computation.

For

we can calculate \(a_{1000}\) immediately.

A recurrence such as

naturally suggests sequential computation, building terms one by one.

Equivalent Algorithms Can Have Different Efficiency

Suppose an arithmetic sequence satisfies

To find \(a_{1000000}\), repeated iteration requires many additions.

But the explicit formula

gives the same result in one direct calculation.

Mathematically equivalent methods can therefore have very different computational costs.

Algorithmic Efficiency

Efficiency concerns the resources an algorithm uses, such as:

• number of arithmetic operations;
• amount of stored information;
• number of repeated steps;
• time required as the input grows.

A mathematically correct algorithm may still be inefficient.

Fibonacci by Iteration

Consider

To generate terms efficiently, we only need to store the two most recent Fibonacci numbers.

The state update is

Fibonacci Iteration Example

Start with

Repeated updates give

Each state contains two consecutive Fibonacci numbers.

Pseudocode for Fibonacci Iteration

x = 0
y = 1

repeat:
    next = x + y
    x = y
    y = next

The temporary value

next

preserves the new sum before the older state values are shifted.

Why Update Order Matters

Suppose we begin with

The correct next Fibonacci-type state is

If we first overwrite

then \(x\) becomes \(5\).

If we then calculate

we obtain \(10\), not \(8\).

The old value of \(x\) was lost too early.

Temporary Storage

A temporary variable preserves information during a state update.

Conceptually:

1. calculate the new value;
2. store it temporarily;
3. shift the old values;
4. place the temporary value into the new state.

This idea appears throughout numerical algorithms.

Recursive Algorithms

A procedure can also call itself to solve a smaller instance of the same problem.

For example, Fibonacci numbers can be described recursively as:

A recursive algorithm mirrors this definition by requesting the values of \(F_{n-1}\) and \(F_{n-2}\).

Base Cases

A recursive algorithm needs base cases that can be answered directly.

For Fibonacci numbers, the base cases are

and

Without base cases, recursive calls would continue indefinitely.

Recursive Versus Iterative Fibonacci Computation

A direct recursive implementation closely resembles the mathematical definition.

However, a naive recursive method may repeatedly recompute the same smaller Fibonacci numbers.

Iteration avoids this repeated work by storing the current state.

Thus mathematical elegance and computational efficiency do not always point to the same implementation.

Repeated Work in Naive Recursion

To calculate

naive recursion asks for

and

But calculating \(F_4\) itself also requires \(F_3\).

The same subproblem is therefore calculated more than once.

Memoization

Memoization stores previously calculated results so they do not need to be recomputed.

For Fibonacci numbers, once \(F_k\) has been found, it can be saved and reused.

This turns repeated recursive work into lookup.

Memoization is one bridge between recursive definitions and efficient algorithm design.

Dynamic Programming

Dynamic programming solves larger problems by systematically building from solutions to smaller subproblems.

A Fibonacci table

is a simple example.

Each stored value supports later calculations.

Iteration and Function Composition

If

then

and

Repeated iteration is repeated function composition.

Iterates

The notation

can be used to mean \(n\)-fold composition of \(f\) with itself.

Then a first-order iteration may be written

when the indexing and definition are compatible.

The composition symbol helps distinguish iteration from ordinary exponentiation.

Example: Repeated Affine Transformation

Let

and

Then

Iterating:

Therefore,

Fixed Points

A fixed point of an iteration

is a value \(L\) satisfying

If an iteration reaches a fixed point exactly, every later term remains there.

Example: Finding a Fixed Point

Consider

A fixed point \(L\) satisfies

Therefore,

and

Iteration Toward a Fixed Point

Let

Then

The values move toward

This gives an early example of iterative convergence.

Tolerance-Based Stopping

Numerical algorithms often stop when successive values are sufficiently close.

For example, one might stop when

The number \(0.001\) is a tolerance.

A smaller tolerance demands closer agreement before stopping.

Approximation and Iteration

Iteration is especially useful when an exact answer is difficult to obtain directly.

An algorithm may produce

that increasingly approximate a desired value.

The algorithm stops when the approximation is accurate enough for the intended purpose.

Newton-Type Iteration

An important later example is Newton's method.

For solving

the iteration is

Each approximation is calculated from the previous one.

This is a more advanced recurrence algorithm, but its structure is the same idea developed here.

Algorithms Can Fail to Stop

A stopping condition must actually be reachable.

Suppose

and the algorithm is instructed to stop when

The sequence contains only integers

so the stopping condition will never be met.

Infinite Loops

A procedure that continues indefinitely because its stopping condition is never satisfied is called an infinite loop.

Preventing unintended infinite loops requires checking:

• whether the state changes as intended;
• whether the stopping condition can occur;
• whether the index or counter advances;
• whether numerical rounding affects the test.

Exact Equality Can Be a Poor Numerical Stopping Test

In approximate numerical computation, a value may approach a target without ever matching it exactly.

Instead of requiring

it may be more practical to require

for a chosen tolerance \(\varepsilon>0\).

Rounding Error

Repeated calculations with decimal approximations can accumulate rounding error.

An iterative algorithm may therefore produce values that differ slightly from exact mathematical values.

Good numerical practice distinguishes:

• the exact recurrence;
• the implemented approximation;
• the chosen precision or tolerance.

Verification by Independent Calculation

An algorithm can often be checked against another representation.

For an arithmetic sequence,

an iterative calculation of \(a_{20}\) can be checked using

Independent methods provide a strong error check.

Verification with Invariants

An invariant is a property that remains true throughout an algorithm.

For example, if a recurrence always generates even numbers, then obtaining an odd value signals an error.

Invariants can help verify long iterative computations without checking every detail separately.

Example: Parity as an Invariant

Let

and

If \(a_n\) is even, then

is even, and adding \(4\) preserves evenness.

Therefore, every term must be even.

Iteration and Tables

An algorithm can be represented as a table of states.

For

a table gives:

The table makes the iterative trend visible.

Iteration and Discrete Graphs

The pairs

can be plotted as a discrete graph.

The graph may reveal:

• growth;
• decay;
• oscillation;
• approach to a fixed point;
• periodic repetition;
• rapid divergence.

Periodic Iteration

Some iterative rules cycle through values.

For example, suppose

with

Then

repeats with period \(2\).

Divergent Iteration

Consider

with

Then

grows without bound.

Not every iteration approaches a stable value.

Iteration Can Depend on the Index

Some recurrence algorithms use both the current state and the current index.

For example,

The algorithm must track both:

• the current sequence value;
• the current index.

The state is therefore larger than the sequence value alone.

Algorithm for an Index-Dependent Recurrence

For

a procedure is:

value = 1
for n = 2 through target:
    value = value + n
output value

The loop counter \(n\) is itself part of the computation.

Accumulation Algorithms

Finite sums can also be computed iteratively.

To calculate

initialize

and repeatedly update

This is a general accumulation algorithm.

Product Accumulation Algorithms

To calculate

initialize

and update

The initial value \(1\) is used because it is the multiplicative identity.

Example: Iterative Factorial Algorithm

Since

factorial can be computed iteratively:

product = 1
for k = 1 through n:
    product = product * k
output product

For \(n=5\), the running products are

Recursive Factorial

Factorial also has a recursive definition:

and

Thus the same mathematical quantity can be implemented recursively or iteratively.

Recursive and Iterative Forms Can Be Equivalent

Consider factorial.

Recursive form:

Iterative form:

Both compute the same value but organize the computation differently.

Common Error: Forgetting Initialization

Every iterative recurrence needs a valid starting state.

The rule

does not determine a unique sequence without an initial term.

Likewise, an algorithm cannot begin if its state has not been initialized.

Common Error: Off-by-One Iteration

Suppose \(a_1\) is already known and we want \(a_{10}\).

We need

updates.

Performing ten updates would produce \(a_{11}\).

Common Error: Overwriting State Too Early

In a multi-value recurrence, later calculations may still need an old state value.

Updating one variable before saving the necessary information can change the mathematical recurrence being implemented.

Temporary storage or simultaneous assignment prevents this problem.

Common Error: Using the Wrong Initial Identity

For summation, initialize the accumulator with

For multiplication, initialize with

Starting a product at \(0\) would force every later product to remain zero.

Common Error: Stopping Before Recording the Desired State

An algorithm may test its stopping condition before or after an update.

That choice affects which state is returned.

A correct algorithm must clearly specify whether it stops:

• before executing the next update; or
• after executing and recording it.

Common Error: Assuming Iteration Must Converge

Repeated application of a rule does not guarantee approach to a limit.

An iteration may:

• converge;
• diverge;
• oscillate;
• cycle;
• behave more irregularly.

Long-run behavior must be analyzed rather than assumed.

A Reliable Procedure for Turning a Recurrence into an Algorithm

1. Identify the initial condition or conditions.
2. Determine what information must be stored as state.
3. Translate the recurrence into an update rule.
4. Determine the correct starting index.
5. Choose a loop structure.
6. Specify the stopping condition.
7. Update state in a safe order.
8. Record or return the required output.
9. Check the first few results against hand calculations.

A Reliable Procedure for Checking an Iterative Algorithm

1. Verify the initialization.
2. Check one update by hand.
3. Check the index change.
4. Confirm that required old values are not overwritten too early.
5. Verify the stopping condition.
6. Compare against an explicit formula when one exists.
7. Check invariants or expected qualitative behavior.
8. Test simple boundary cases.

Example: Full Algorithmic Workflow

Let

Find \(a_5\).

The initial state is

Five updates are required:

Therefore,

Example: Full Fibonacci State Workflow

Use

Begin with state

Update by

Then

After five updates, the state contains

Practice 1: First-Order Iteration

Let

Find \(a_1,a_2,a_3\).

Practice 2: Count the Updates

A sequence begins at \(a_1\).

How many recurrence updates are required to reach \(a_{25}\)?

Practice 3: State Size

For

how many previous sequence values must an iterative algorithm retain?

Practice 4: Fibonacci Update

If the current Fibonacci state is

what is the next state?

Practice 5: Threshold Stopping

Let

Find the first term greater than \(50\).

Practice 6: Accumulator Initialization

What initial value should be used for an accumulator computing

What initial value should be used for

Practice 7: Fixed Point

Find the fixed point of

Practice 8: Iterative Factorial

Use iterative multiplication to calculate

Practice 9: Identify the Update Error

A student wants to update the Fibonacci state \((x,y)\) and writes:

x = y
y = x + y

Explain why this may produce the wrong result.

Practice 10: Convergence Assumption

A student says that every recurrence algorithm eventually settles at a fixed value.

Explain the error.

Practice Answers

Practice 1

Therefore,

Practice 2

Starting from \(a_1\), reaching \(a_{25}\) requires

updates.

Practice 3

The recurrence depends on

and

Therefore, the algorithm must retain

Practice 4

Practice 5

Therefore, the first term greater than \(50\) is

Practice 6

For a sum, use the additive identity:

For a product, use the multiplicative identity:

Practice 7

Let \(L\) be the fixed point:

Therefore,

Thus,

Practice 8

Practice 9

After

x = y

the old value of \(x\) has been lost.

Then

y = x + y

uses the new \(x\) instead of the old one.

A temporary value or simultaneous update is needed.

Practice 10

Iterative sequences may converge, diverge, oscillate, cycle, or behave in other ways.

For example,

produces

which grows without approaching a finite fixed value.

What to Remember

A recurrence relation describes how states are related:

An algorithm turns that relationship into an executable procedure:

• Iteration repeatedly applies an update rule.
• State is the information that must be remembered between steps.
• First-order recurrences may need one stored term; higher-order recurrences need more.
• Stopping conditions may be count-based, threshold-based, or tolerance-based.
• Update order matters when several state values depend on old information.
• Recursive and iterative algorithms can compute the same mathematical object.
• Equivalent algorithms can differ greatly in efficiency.
• Accumulation algorithms use \(0\) for sums and \(1\) for products.
• Iteration may converge, diverge, oscillate, or cycle.
• Independent formulas, invariants, and boundary tests help verify algorithms.

Where We Go Next

Recurrence algorithms show how discrete mathematical objects evolve one state at a time. We can now step back and compare the broader behavior of discrete functions and sequence patterns, including what it means for their values to approach a stable number.

The next lesson, Discrete Functions, Patterns, and Introductory Convergence, brings together explicit rules, recurrences, graphs, iteration, and long-run behavior while introducing the basic language of convergence.