Recursion (vs iteration)¶

Estimated time to complete: one hour.

Introduction¶

Although we have now seen all the essential tools for describing mathematical calculations and working with functions, there is one more algorithmic tool that can be very convenient, and is also of fundamental importance in the study of functions in both mathematics and theoretical computer science.

This is recursively defined functions: where the definition of the function refers to other values of the same function. To avoid infinite loops, the other values are typically for input values that are in some sense “earlier” or “smaller”, such as lower values of a natural number.

We have already seen two familiar examples in Unit 5; the factorial: $$ \begin{split} 0! &= 1 \\ n! &= n \cdot (n-1)! \text{ for } n \geq 1 \end{split} $$

and the Fibonacci numbers $$ \begin{split} F_0 &= 1 \\ F_1 &= 1 \\ F_n &= F_{n-1} + F_{n-2} \text{ for } n \geq 2 \end{split} $$

Iterative form¶

These can be implemented using iteration, as seen in Unit 5; here are two versions:

def factorial_iterative(n):
    n_factorial = 1
    for i in range(2, n+1):  # n+1 to include the factor n
        n_factorial *= i
    return n_factorial

n = 5
print(f'{n}! = {factorial_iterative(n)}')
print('Test some edge cases:')
print('0!=', factorial_iterative(0))
print('1!=', factorial_iterative(1))

5! = 120
Test some edge cases:
0!= 1
1!= 1

def first_n_factorials(n):
    factorials = [1]
    for i in range(1, n):
        factorials.append(factorials[-1]*i)
    return factorials

n = 10
print(f'The first {n} factorials (so up to {n-1}!) are {first_n_factorials(n)}')

The first 10 factorials (so up to 9!) are [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

Recursive form¶

However we can also use a form that is closer to the mathematical statement.

First, let us put the factorial definition in more standard mathematical notation for functions $$ \begin{split} f(0) &= 1 \\ f(n) &= n \cdot f(n-1) \text{ for } n \geq 1 \end{split} $$

Next to make it more algorithmic and start the segue towards Python code, distinguish the two cases with an if

if n = 0:
$\qquad f(n) = 1$
else:
$\qquad f(n) = n \times f(n-1)$

Here that is in Python code:

def factorial_recursive(n):
    if n == 0:
        return 1
    else:
        return n * factorial_recursive(n-1)

n = 9
print(f'{n}! = {factorial_recursive(n)}')

9! = 362880

Yes, Python functions are allowed to call themselves, though one must beware that this could lead to an infinite loop.

Exercise A¶

Can you see how you could cause that problem with this function?

Try, and you will see that Python has some defences against this kind of infinite loop.

It can be illuminating to trace the steps with some extra print commands:

def factorial_recursive_with_tracing(n, trace=False):
    if trace:
        print(f'n = {n}')
    if n == 0:
        factorial = 1
    else:
        factorial = n * factorial_recursive_with_tracing(n-1, trace)
    if trace:
        print(f'{n}! = {factorial}')
    return factorial

n = 5
nfactorial = factorial_recursive_with_tracing(n, trace=True)
print('The final result is', nfactorial)

n = 5
n = 4
n = 3
n = 2
n = 1
n = 0
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
The final result is 120

Experiment: Try sending this tracing version into an infinite loop. (In JupyterLab, note the square “stop” button to the right of the triangular “play” button!)

Exercise B: Fibonacci numbers by recursion¶

Write and test a recursive function to evaluate the $n$-th Fibonacci number $F_n$, mimicking the first, simplest recursive version for the factorial above.

Do this without using either lists, arrays, or special variables holding the two previous values!

If you have access to Spyder (or another Python IDE) develop and test this in a Python file “exercise7b.py” and submit that as well as a final notebook for this unit.

Test for $n$ at least 5.

Exercise C: tracing the recursion¶

Write and test a second recursive function to evaluate the first $n$ Fibonacci numbers, adding the option of tracing output, as in the second recursive example above.

Again test for $n$ at least 5.

Again, develop and test this in a Python file “exercise7c.py” initially if you have access to a suitable IDE.

Comment on why this illustrates that, although recursive implementations can be very concise and elegant, they are sometimes very inefficient compared to expressing the calculation as an iteration with for or while loops.

Exercise D: present your work in a Jupyter notebook¶

If you have not done so already, put all your code for the above exercises into a single Jupyter notebook.

Make sure that, like all documents produced in this course, the notebook and any other files submitted have an appropriate title, your name, and the correct date at the top!

Note the way I express the date as “Last modified”; keep this up-to-date when you revise.

Bonus Material: Tail Recursion¶

Some recursive algorithms are so-called tail recursive, which means that when a function calls itself, the “calling” invocation of the function has nothing more to do; the task is handed off entirely to the new invocation. This means that it can be possible to “clean up” by getting rid of all memory and such associated with the calling invocation of the function, eliminating that nesting seen in the above tracing and potentially improving efficiency by a lot.

Some programming languages do this “clean up” of so-called “tail calls”; indeed functional progamming languages forbid variables to have their values changed within a function (so that functions in such a language are far more like real mathematical functions), and this rules out many while loop algorithms, like those above. Then recursion is a central tool, and there is a high piority on implementing recursion in this efficient way.

For example, here is a tail recursive approach to the factorial:

def factorial_tail_recursive(n):
    '''For convenience, we wrap the actual "working" function inside one with simpler input:
    '''
    def tail_factorial(result_so_far, n):
        print(f'result_so_far = {result_so_far}, n = {n}')
        if n == 0:
            return result_so_far
        else:
            return tail_factorial(result_so_far*n, n-1)
    result_so_far = 1
    return tail_factorial(result_so_far, n)

n = 9
print(f'factorial_tail_recursive gives {n}! = {factorial_tail_recursive(n)}')
print('\nFor comparison,')
print(f'factorial_recursive gives {n}! = {factorial_recursive(n)}')
print(f'factorial_iterative gives {n}! = {factorial_iterative(n)}')

result_so_far = 1, n = 9
result_so_far = 9, n = 8
result_so_far = 72, n = 7
result_so_far = 504, n = 6
result_so_far = 3024, n = 5
result_so_far = 15120, n = 4
result_so_far = 60480, n = 3
result_so_far = 181440, n = 2
result_so_far = 362880, n = 1
result_so_far = 362880, n = 0
factorial_tail_recursive gives 9! = 362880

For comparison,
factorial_recursive gives 9! = 362880
factorial_iterative gives 9! = 362880

However, tail recursion is in general equivalent to iteration with a while loop, with the input and output of the tail recursive function instead being variables that are updated in the loop. Thus it is mostly a matter of preference as to how one expresses the algorithm.

For example, the above can be rather straightforwardly translated to the following:

def factorial_tailless(n, tracing=False):
    result_so_far = 1
    while n != 0:
        if tracing:
            print(f'result_so_far = {result_so_far}, n = {n}')
        (result_so_far, n) = (result_so_far*n, n-1)
    return result_so_far

print(f'factorial_tailless gives {n}! = {factorial_tailless(n)}')

factorial_tailless gives 9! = 362880

A final challenge (optional, and maybe hard!)¶

Write a tail-recursive Python function for computing the Fibonacci number $F_n$.

Python for Scientific Computing