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 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.
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.