Recursion

Algorithms & Problem Solving, lesson 1 of 6

🧠 Algorithms & Problem Solving, lesson 1 of 6

Recursion

Solve problems by having a function call itself on smaller inputs.

11 min

2 exercises

1 quiz

0/3 solved

Getting Python ready… examples can run in a moment.

A recursive function calls itself to solve a smaller version of the same problem. It needs two parts:

  • a base case: an input so simple you answer it directly (this stops the recursion)
  • a recursive case: shrink the problem and call the function again

Factorial is the classic: 5! = 5 × 4!, and 1! = 1.

Example

Factorial

factorial(5) becomes 5 * factorial(4), then 5 * 4 * factorial(3), and so on down to 1. Python ints never overflow: try factorial(30).

Example

Watch the calls stack up

Each call waits for the call below it to finish, then carries on where it left off. That pile of waiting calls is the call stack.

Quiz

What does this print?

Exercise

Sum the digits

Write a recursive sum_digits(n) for a non-negative integer:

  • base case: if n < 10, return n
  • otherwise: last digit (n % 10) plus sum_digits(n // 10)

Where recursion shines: nested data. Folders inside folders, comments with replies, menus with submenus. A loop can't easily handle unknown depth, but a recursive function simply calls itself for each inner level.

Example

Folders within folders

Nest another folder like [1, [2, [3]]] anywhere in disk. The function copes with any depth.

Example

RecursionError

Python compresses the repeated lines of the traceback. Add if n == 50: return n as a base case to fix it.

Exercise

Flatten a nested list

Write a recursive flatten(items) that returns one flat list with every number from any depth, in order: flatten([1, [2, [3, 4]], 5]) is [1, 2, 3, 4, 5].