Free preview

100 lessons

Python Done Right

Free preview

Python Done Right · 100 lessons

Learn Python from scratch - syntax through to OOP

No surprise gaps

Actually remember it

Skip what you know

One subscription. All learning paths included.

Our content is best on a larger screen

Introduction to recursion

What is recursion

Explanation

Sometimes the best way to solve a problem is to break it down into smaller versions of itself. When a function solves a problem by calling itself with a simpler input, we call this recursion.

Recursion appears naturally in mathematics. Consider the factorial function:

n! = n \times (n-1) \times (n-2) \times \ldots \times 2 \times 1

We can also define this recursively:

n! = n \times (n-1)!

The factorial of $n$ is defined in terms of the factorial of $n-1$ . This self-referential pattern - where a problem is expressed in terms of a smaller version of itself - is the essence of recursion.

Here is a simple recursive countdown function. Notice how countdown calls itself with a smaller argument each time:

def countdown(n):
    if n == 0:
        print("Done!")
    else:
        print(n)
        countdown(n - 1)

Tracing countdown(3)

Details

Example

Recursive sum from $1$ to $n$ :

The sum $1 + 2 + 3 + \ldots + n$ can be expressed as:

\text{sum}(n) = n + \text{sum}(n-1)

For example, once we already know the total from $1$ to $8$ , we can get the total up to $9$ simply by adding $9$ to the previous sum.

def sum_to_n(n):
    if n == 1:
        return 1
    else:
        return n + sum_to_n(n - 1)

print(sum_to_n(5))  # Output: 15

Tracing through sum_to_n(5):

Call	Returns
`sum_to_n(5)`	`5 + sum_to_n(4)` → `5 + 10` → `15`
`sum_to_n(4)`	`4 + sum_to_n(3)` → `4 + 6` → `10`
`sum_to_n(3)`	`3 + sum_to_n(2)` → `3 + 3` → `6`
`sum_to_n(2)`	`2 + sum_to_n(1)` → `2 + 1` → `3`
`sum_to_n(1)`	`1` (stops here)

Practice questions

4 questions

Which statement best describes recursion in programming?

Select the correct answer:

A function that runs forever.

A function that calls itself.

A function that calls other functions.

A function with multiple return statements.

+ 3 more questions

Base case and recursive case

Explanation

Every recursive function needs two parts:

Base case - the condition that stops the recursion. Without it, the function would call itself forever.

Recursive case - where the function calls itself with a simpler input, moving towards the base case.

Here is the factorial function with both parts labelled:

def factorial(n):
    if n == 1:           # Base case
        return 1
    else:                # Recursive case
        return n * factorial(n - 1)

Part	Code	Purpose
Base case	`if n == 1: return 1`	Stops recursion: $1! = 1$
Recursive case	`return n * factorial(n - 1)`	Reduces problem: $n! = n \times (n-1)!$

Warning

Without a base case, recursion never stops. Python will raise a RecursionError when the call stack becomes too deep.

What happens without a base case?

Details

Example

Tracing through factorial(4):

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

print(factorial(4))  # Output: 24

Call	Evaluates to	Result
`factorial(4)`	`4 * factorial(3)`	`4 * 6 = 24`
`factorial(3)`	`3 * factorial(2)`	`3 * 2 = 6`
`factorial(2)`	`2 * factorial(1)`	`2 * 1 = 2`
`factorial(1)`	`1` (base case)	`1`

The recursion "unwinds" as each call returns its result to the caller.

Practice questions

4 questions

What is the purpose of the base case in a recursive function?

Select the correct answer:

To make the function run faster.

To stop the recursion and return a value without further recursive calls.

To call the function with a larger input.

To call the function with a smaller input.

+ 3 more questions

Recursion in practice

Explanation

The Fibonacci sequence starts with $1, 1$ , then each subsequent number is the sum of the two before it:

1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots

This is naturally recursive - each term depends on two previous terms:

\text{fib}(n) = \text{fib}(n-1) + \text{fib}(n-2)

Since the recursive case references both $n-1$ and $n-2$ , we need two base cases: $\text{fib}(1) = 1$ and $\text{fib}(2) = 1$ .

def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

Risks of recursion

Recursion is not always the best approach:

Risk	Description
No base case	Function calls itself forever until Python raises `RecursionError`
Memory consumption	Each recursive call uses memory; deep recursion can exhaust the stack
Inefficiency	Some recursive solutions repeat the same calculations many times

Why is recursive Fibonacci inefficient?

Details

Example

Tracing through fib(5):

def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

Call	Evaluates to	Result
`fib(5)`	`fib(4) + fib(3)`	`3 + 2 = 5`
`fib(4)`	`fib(3) + fib(2)`	`2 + 1 = 3`
`fib(3)`	`fib(2) + fib(1)`	`1 + 1 = 2`
`fib(2)`	`1` (base case)	`1`
`fib(1)`	`1` (base case)	`1`

So fib(5) returns 5, which is correct: the sequence is 1, 1, 2, 3, 5.

Practice questions

4 questions

Why does the Fibonacci function need two base cases (n == 1 and n == 2) instead of just one?

Select the correct answer:

Because Fibonacci numbers are always even.

Because the recursive case calls fib(n - 1) and fib(n - 2), so we need stopping points for both.

Because Python requires at least two base cases for recursion.

Because one base case would make the function run slower.

+ 3 more questions

Part of

User-defined functions

See all 10 lessons, what comes first, and what this unlocks.