2.2.1 - Recursion and iteration

A recursive solution needs a stopping rule

Recursion occurs when a subroutine calls itself, directly or through other subroutines. A useful recursive algorithm identifies a simple base case that returns without another recursive call, and a recursive case that reduces the problem toward that base case.

Consider the sum of integers from 1 to n, for a non-negative integer n. The sum for 0 is 0. For a positive n, the answer is n plus the sum for n-1. That relationship defines both the answer and how to make progress:

function triangular(n)
    if n == 0 then
        return 0
    else
        return n + triangular(n - 1)
    endif
endfunction

The parameter n supplies each call's input; return supplies the function's result to its caller. OCR assumes value passing unless stated otherwise, so this example's smaller argument does not modify the caller's n. The function is called with an expression such as result = triangular(3).

For every permitted positive n, subtracting one eventually reaches zero. A base case alone is insufficient: triangular(n + 1) moves away from it. The input contract matters too. A negative n repeatedly decreases and never reaches zero in this definition. A real interface must reject negative input or use a separately specified meaning for it. Python also places a practical limit on call depth; a mathematically terminating algorithm is not a promise that arbitrarily large input can run in this environment.

The Python translation is direct:

def triangular(n):
    if n == 0:
        return 0
    return n + triangular(n - 1)

Defining the function does not calculate anything yet. A call starts the calculation. Printing a value inside a function is different from returning it: a caller using the result needs return, even if a screen message looked correct.

A faulty progress rule can keep adding calls until Python raises RecursionError. That runtime limit stops execution; it is not a returned answer or proof that the algorithm reaches its intended base case. The ungraded experiment below contrasts reaching zero with exhausting the available call depth.

Calls wait for results and return in reverse order

Each recursive call has its own stack frame: saved information such as its parameter, local variables and the place to continue after the called function returns. A call stack keeps these active calls in last-in, first-out order. Calling a function adds a frame; returning removes that frame and resumes its caller.

For triangular(3), the outer call cannot finish 3 + triangular(2) until triangular(2) returns. It waits with its own n still equal to 3. The next calls similarly wait:

The deepest call finishes first. triangular(1) resumes and returns 1+0 = 1; triangular(2) returns 2+1 = 3; triangular(3) returns 3+3 = 6. Arguments entered are 3,2,1,0, while returned values are 0,1,3,6. Confusing these two orders loses the pending calculation.

The same rule applies to instructions after a call:

def display(n):
    if n == 0:
        return
    print("enter", n)
    display(n - 1)
    print("leave", n)

display(2)

Its output is:

enter 2
enter 1
leave 1
leave 2

The zero call prints nothing. The line after display(n - 1) is delayed until that call completes, and each resumed frame still has its own n. This is why tracing only the input changes is inadequate for a recursive routine.

A loop can maintain the same partial result

An iterative solution repeats instructions without adding a new recursive frame for each step. To translate a recursive calculation into a loop, identify the state that the calls change and the work that their returns combine.