Recursion
When learning programming, we often deal with tasks in a linear, straightforward manner. But what if we encounter a problem that requires breaking it down into smaller, similar problems? That's where recursion is used.
In plain English, recursion is when a function calls itself during its execution. This might sound like it would create an endless loop, but if we design our function correctly, it will eventually reach a point where it no longer calls itself.
Imagine a Matryoshka doll. Each time you open a doll, there's a smaller one inside, and you keep going until you reach the smallest doll that cannot be opened. This process of opening dolls is a bit like recursion. To reach the smallest doll, which is like solving the most difficult problem, you solve it by repeatedly solving easier versions of the same problem (opening the larger dolls) until you reach a point where the problem can't be reduced any further (the last doll).
The process of solving a large problem by recursively dividing it into smaller problems until reaching the smallest/easiest possible one is best understood with the concept of the “recursive leap of faith”.
Recursive Leap of Faith
When implementing a recursive solution to a problem, one usually creates a function that works by calling itself at some point. The part of calling itself is usually referred to as the recursive call.
The great part about recursive solutions is that one can assume that the function works correctly when called with some simple arguments, and then implement the correct behavior for the harder ones. Similar to calling other functions like
sqrt, max, abs, and others that we’ve been using before, you can assume that the function works for some smaller/simpler arguments and call those to build the current result on top of those.💡
The only requirement is to make sure the function will arrive at the base case (the simplest case). Otherwise, we would have an infinitely running recursive function and might get a StackOverflow!
As a demonstration of how one might have a computation inside a recursive function, we can try to calculate the sum of all the numbers from
0, 1, 2, …, n given a number n.Let’s implement the
sum function step-by-step. The first step is to make sure the function works properly for the simplest case (properly count the sum for n being 0 or 1):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0: # In case n is 0 => the sum is 0
return 0 # Stop the function execution here
if n == 1: # In case n is 1 => the sum is 1
return 1 # Stop the function execution here
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> None (as we haven't implemented this part)Having this part of the function, we can already use the fact that
sum(0) will always correctly return 0, while sum(1) will always return 1. The function will work correctly even if we call the sum function with arguments 0 or 1 from the sum function itself.So, we can go one step further and implement the
sum function for n = 2 and n = 3 by having the results for sum(1) and sum(0):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2: # If n is 2, we can add 2 to the result of sum(1) implemented above
return n + sum(1) # or `n + sum(n - 1)`
if n == 3: # If n is 3, we can add 3 to the result of sum(2) implemented above
return n + sum(2) # or `n + sum(n - 1)`
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> None (as we haven't implemented this part)This way, it’s obvious that the
sum function works properly for small cases like n being equal to 0, 1, 2, or 3.Having this, we can implement the function for other values of
n larger than 3. The only requirement is to arrive at those smaller values of n (0, 1, 2, or 3) when calling the function sum from itself. So, for larger values of n, like 4, 5, or 6, etc. we can implement the sum function by using the fact that to calculate the sum(4), we can add 4 to the result of sum(3), while calculating the sum(5) can be done by adding 5 to the result of sum(4):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return n + sum(1)
if n == 3:
return n + sum(2)
# For all other cases (4, 5, 6, ...)
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...The key parts of a recursive function are:
- Base case: A condition that stops the recursion. Without this, the function would call itself indefinitely, causing an infinite loop.
Here, it's
n == 0andn == 1.
- Recursive step: Where the function calls itself, usually with a different argument.
Here, it's
sum(n - 1).
As the calls for
n == 1, n == 2, and n == 3 are exactly the same as for n == 4, n == 5, etc., we can even simplify the sum function by having only 1 base case (for n == 0):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...This way, having the recursive leap of faith, we assume/know that the function works properly for smaller/simpler cases, and construct the rest of the function based on those simpler cases. That helps in understanding how recursive functions work and how they can be implemented.
💡
Calling the function recursively is like calling a completely different function that you know for sure will work with the passed arguments.