Recursion is a powerful tool in your coding toolbox. Understanding it is a key skill on your path to mastery. This article gives you a thorough introduction to this important computer science concept.
What is Recursion?
Stephen Hawking used a concise explanation: “to understand recursion, one must first understand recursion.”
Recursion is a concept in computer science where a function, directly or indirectly, calls itself one or more times in its body. This is done to solve a larger problem by solving smaller instances of the same problem.
Usually, a recursive function has two main parts:
- Base Case: This is the terminating scenario that does not use recursion to produce an answer. It usually handles edge cases for which the solution is trivial and direct. The base case is essential to prevent the function from calling itself indefinitely.
- Recursive Case: This part of the function solves a piece of the problem and then calls itself to solve the remaining smaller parts.
For instance, consider a function to compute the factorial of a number using recursion. The factorial of a number n is the product of all positive integers less than or equal to n.
Here’s an example in Python:
def factorial(n):
if n == 0: # base case
return 1
else: # recursive case
return n * factorial(n-1)
In this case, factorial(n-1) is the recursive call. For each number n, it calls itself with n-1, until it reaches the base case, which is n == 0, and then it returns 1. These returns then “bubble up” through the recursive calls, multiplying all the integers from 1 up to n together.
It’s important to use recursion judiciously, as it can lead to a large amount of memory use or even stack overflow if the depth of recursion is too high. Some problems are well-suited to recursion, especially those that can be broken down into similar smaller problems. However, in other cases, an iterative approach may be more efficient.
✅ Recommended: A Simple Python Factorial Program Using Recursion
Recursion is a popular computer science concept where a problem is solved using a recursive function.
You create a recursive function f in four steps:
- Break the original problem into smaller problem instances,
- Take the smaller problem instances as the input of function f (which will then break the smaller input into even smaller problem instances and so on),
- Define a “base case” which is the smallest possible input that can be solved directly without any further call of the function f, and
- Specify how you can recombine the obtained smaller solutions into the larger solution.
What’s a Simple Example for Recursion?
Consider the factorial function that calculates the product of all numbers up to number n:
f(5) = 5 * 4 * 3 * 2 * 1 = 120 f(4) = 4 * 3 * 2 * 1 = 24 f(3) = 3 * 2 * 1 = 6
The following example shows that the factorial can be defined by using itself on a smaller problem instance. In other words, we define the factorial function recursively!
The recursive definition of the factorial function showcases an important element of recursion: every recursive function definition must specify
- how the recursion base case is defined, and
- how to obtain the solution to a bigger problem from the smaller problem.
This definition shows that the base case of the factorial function appears for n=1. The factorial of 1 is 1: there’s no need to proceed with the recursion.
You can also see that the problem is made easier in each call of the recursive function. Using the solution to the easier case (the factorial of n-1), we can directly obtain the solution of the harder case (the factorial of n) by multiplying the easier solution with n.
Here’s how the recursive factorial looks like in Python code:
def factorial(n):
if n<2:
return 1
else:
return n * factorial(n-1)
for i in range(10):
print(factorial(i))
"""
Output:
1
1
2
6
24
120
720
5040
40320
362880
"""Say, you have already found a solution to the factorial of n-1. Now, it’s easy to find the factorial of n by just multiplying n with the factorial of n-1. To prevent the recursion from proceeding forever, we define the base case for n<2.
What is Mutual Recursion?
Mutual recursion arises if function a() calls function b() — and function b() calls function a() to find a solution.
In other words, functions a() and b() are interdependent.
Here’s an example:
def ping(i):
if i>0:
return pong(i-1)
return "0"
def pong(i):
if i>0:
return ping(i-1)
return "1"
print(ping(29))Puzzle: What’s the output of this code snippet?
This puzzle gives an example for mutual recursion: function ping calls function pong which calls function ping. Each function call solves a slightly easier problem.
In recursive problem solving, a function knows the result for some base cases (i.e., the naive solutions). It breaks a complex problem into a combination of less complex subproblems. As the subproblems are getting easier, they finally reach the base cases.
These are the least complex subproblems and we know their solutions. The idea is to build the solution of the complex problem from the solutions of the subproblems.
So when you call ping(29), the ping function reduces this question to pong(28) – an easier problem. The calling function ping waits for pong to return a solution. But pong asks back ping(27) and waits for a solution. On a higher level, ping receives odd and pong even argument values for the initial input i=29. Thus, the last call is pong(0), which returns 1. Each calling function is waiting for the result of the called function. Each calling function receives the value 1 and returns it to its parent calling function. Finally, the top-most functional instance ping(29) returns the value 1 as the final result.
Related Video – Python Kata on Recursion
You can also watch this video where Finxter Creator Clement solves a Python kata using some of the concepts learned in this article.
Where to Go From Here?
The article has given you a concise introduction into recursion (and mutual recursion) using simple examples.
The examples are taken from my book “Coffee Break Python” which teaches you all important concepts and features you need to know to get started with Python.
