When we think about repeating a task, we usually think about the
while loops. These constructs allow us to perform iteration over a list, collection, etc.
However, there's another form of repeating a task, in a slightly different manner. By calling a function within itself, to solve a smaller instance of the same problem, we're performing recursion.
These functions call themselves until the problem is solved, practically dividing the initial problem to a lot of smaller instances of itself – like for an example, taking small bites of a larger piece of food.
The end goal is to eat the entire plate of hot pockets, you do this by taking a bite over and over. Each bite is a recursive action, after which you undertake the same action the next time. You do this for every bite, evaluating that you should take another one to reach the goal, until there are no hot pockets left on your plate.
What is Recursion?
As stated in the introduction, recursion involves a process calling itself in the definition. A recursive function generally has two components:
- The base case which is a condition that determines when the recursive function should stop
- The call to itself
Let's take a look at a small example to demonstrate both components:
# Assume that remaining is a positive integer def hi_recursive(remaining): # The base case if remaining == 0: return print('hi') # Call to function, with a reduced remaining count hi_recursive(remaining - 1)
The base case for us is if the
remaining variable is equal to
0 i.e. how many remaining "hi" strings we must print. The function simply returns.
After the print statement, we call
hi_recursive again but with a reduced remaining value. This is important! If we do not decrease the value of
remaining the function will run indefinitely. Generally, when a recursive function calls itself the parameters are changed to be closer to the base case.
Let's visualize how it works when we call
After the function prints 'hi', it calls itself with a lower value for
remaining until it reaches
0. At zero, the function returns to where it was called in
hi_recursive(1), which returns to where it was called in
hi_recursive(2) and that ultimately returns to where it was called in
Why not use a Loop?
All traversal can be handled with loops. Even so, some problems are often easier solved with recursion rather than iteration. A common use case for recursion is tree traversal:
Traversing through nodes and leaves of a tree is usually easier to think about when using recursion. Even though loops and recursion both traverse the tree, they have different purposes – loops are meant to repeat a task whereas recursion is meant to break down a large task into smaller tasks.
Recursion with trees for example fork well because we can process the entire tree by processing smaller parts of the tree individually.
The best way to get comfortable with recursion, or any programming concept, is to practice it. Creating recursive functions are straightforward: be sure to include your base case and call the function such that it gets closer to the base case.
Sum of a List
Python includes a
sum function for lists. The default Python implementation, CPython, uses an indefinite for-loop in C to create those functions (source code here for those interested). Let's see how to do it with recursion:
def sum_recursive(nums): if len(nums) == 0: return 0 last_num = nums.pop() return last_num + sum_recursive(nums)
The base case is the empty list - the best
sum for that is
0. Once we handle our base case, we remove the last item of the list. We finally call the
sum_recursive function with the reduced list, and we add the number we pulled out into the total.
In a Python interpreter
sum([10, 5, 2]) and
sum_recursive([10, 5, 2]) should both give you
You may recall that a factorial of a positive integer, is the product of all integers preceding it. The following example would make it clearer:
5! = 5 x 4 x 3 x 2 x 1 = 120
The exclamation mark denotes a factorial, and we see that we multiply
5 by the product of all the integers from
1. What if someone enters
0? It's widely understood and proven that
0! = 1. Now let's create a function like below:
def factorial(n): if n == 0 or n == 1: return 1 return n * factorial(n - 1)
We cater for the cases where
0 is entered, and otherwise we multiply the current number by the factorial of the number decreased by
A simple verification in your Python interpreter would show that
factorial(5) gives you
A Fibonacci sequence is one where each number is the sum of the proceeding two numbers. This sequence makes an assumption that Fibonacci numbers for 0 and 1 are also 0 and 1. The Fibonacci equivalent for 2 would therefore be 1.
Let's see the sequence and their corresponding natural numbers:
Integers: 0, 1, 2, 3, 4, 5, 6, 7 Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13
We can easily code a function in Python to determine the fibonacci equivalent for any positive integer using recursion:
def fibonacci(n): if n == 0: return 0 if n == 1: return 1 return fibonacci(n - 1) + fibonacci(n - 2)
You can verify it works as expected by checking that
fibonacci(6) equals to
Now I'd like you to consider another implementation of this function that uses a for loop:
def fibonacci_iterative(n): if n <= 1: return n a = 0 b = 1 for i in range(n): temp = a a = b b = b + temp return a
If the integer is less than or equal to 1, then return it. Now that our base case is handled. We continuously add the first number with the second one by storing the first number in a
temp variable before we update it.
The output is the same as the first
fibonacci() function. It's possible that it may even be faster. The solution however, is not as easily readable as our first attempt. There lies one of recursion's greatest powers: elegance. Some programming solutions are most naturally solved using recursion.
Recursion allows us to break a large task down to smaller tasks by repeatedly calling itself. A recursive function requires a base case to stop execution, and the call to itself which gradually leads to the function to the base case. It's commonly used in trees, but other functions can be written with recursion to provide elegant solutions.