Recursion

A function that calls itself

• Recursion is when a function calls itself.
• Each call should work on a smaller version of the problem.
• Done right, the problem shrinks until it is trivial to solve.

Base case and recursive case

• The base case is the simplest case — it stops the recursion.
• The recursive case calls the function again on a smaller input.
• Without a base case the function never stops (an error).

def countdown(n):
    if n == 0:
        print("Go!")
        return
    print(n)
    countdown(n - 1)

countdown(3)

A worked example: factorial

• The factorial n! means n × (n-1) × ... × 1.
• In recursive form: n! = n × (n-1)!, and the base case is 0! = 1.
• Each call multiplies n by the factorial of one less.

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

print(factorial(4))

How the computer runs it

• Each call is paused on a call stack while it waits for the inner call.
• When the base case returns, the paused calls finish one by one.
• Too many calls overflow the stack — Python raises a RecursionError.

In Cambridge pseudocode

• A recursive function names its base case and recursive case clearly.

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
    IF n = 0 THEN
        RETURN 1                       // base case
    ELSE
        RETURN n * Factorial(n - 1)    // recursive case
    ENDIF
ENDFUNCTION

Now you try

• Give each function a base case and a recursive case.
• Press Check answer to test your code.