In most programming languages, we use loop constructs like ‘while’ and ‘for’ to repeatedly execute a block of code until a certain condition is met. A recursive function does pretty much the same thing; except that it does this by calling itself within itself! And just as in loops it stops calling itself when a certain condition is met. Thus, in computer programming, recursion is when a function calls itself.
In code this is what recursion looks like:
def decrement_number_until_zero(number):
print(number)
decrement_number_until_zero(number - 1)
Oh that Works ?
Well, it wouldn’t! Why? When executed this function will throw a stack overflow error.
Stack Overflow Error ?
A stack at the most basic level is a data structure that only exposes its topmost element. Think of a stack as a cylinder with one end open and the other end closed. In such a cylinder you obviously can only add and remove items from the open end. A stack is often referred to as a first in last out data structure. This is true because since stacks only allow you to add and remove items from the top of the stack only, then the last element to go into the stack will be the first to go out and the first to go into the stack will be the last to go out. Adding an element to a stack is called pushing and removing an element from a stack is called popping.
Okay, How is this Connected to Stack Overflow You Ask?
Well, anytime you make a function call, in Python and most programming languages, the function is pushed into a stack data structure called the call stack. And when the function returns, the function is popped from the call stack. Each function pushed into a stack is called a stack frame. A stack frame basically stores information like the variables used in a function and where the function is suppose to return to among others. In recursive functions every single time a function references itself that same function is pushed into the call stack. In Python there is an upper bound to the number of functions a call stack could accommodate at once.
Our function above will throw the stack overflow error because our function will attempt to add it self to the call stack for an infinite number of times. Remember, the call stack in python has a threshold. The stack overflow error is thrown when the threshold is reached.This is happening because the function definition does not specify the condition for when the function is suppose to stop calling itself. This condition is called the base case. So a better way of writing the function above will be this:
def decrement_number_until_zero(number):
if number > 0:
print(number)
decrement_number_until_zero(number - 1)
This revised function wouldn’t attempt to execute to infinity because now a condition for when it should stop executing had been provided.
A second example of seeing recursion in action is seen below:
def reverse_string_recursively(string):
if len(string) == 0:
return string
else:
return reverse_string_recursively(string[1:] )+ string[0]
The function above reverses a string recursively. Again this is a great example of recursion because it specifies a condition for when the program should end execution.
As you might have figured out already, a good recursive function has two parts:
- Base case: a boolean expression that when it evaluates to ‘true’ the program execution terminates
- Recursive case: is the part that executes when the base case evaluates to false. Usually this is where the function references itself.
Now I’ve said a lot about call stacks, base cases and recursive cases. Let me quickly demonstrate how recursive functions are executed under the hood.
The way recursive functions execute under the hood could be likened to a storyteller who is telling a story about Person A then switches mid way to a story about person B then again switches mid way to a story about Person C. At the end of Person C’s story, the storyteller then goes back to the story about Person B where s/he left off. At the end of person B’s story, the storyteller then moves on and completes Person A’s story where s/he left off.
Didn’t Get that ?
Let’s first of all start by looking at an example of how this works in regular functions.
def c():
print(“at the beginning of c”)
c()
print(“at the end of c”)
def b():
print(“at the beginning of b”)
c()
print(“at the end of b”)
def a():
print(“at the beginning of a”)
b()
print(“at the end of a”)
a()
First of all, the function a is loaded into the call stack and just as in the story teller analogy, mid way into it’s execution, the main execution thread switches to function b and there too it switches to function c. when function c is done executing the main execution thread switches to function b. It ends its execution with function a.
So the output of calling function a above would be:
at the beginning of a
at the beginning of b
at the beginning of c
at the end of c
at the end of b
at the end of a
As mentioned earlier on when the last line of a function is executed, the function returns. As a result that function is popped from the call stack.
Beginning to Understand How this Works?
Alright let’s look at how this works in recursive functions. Let’s try to understand this by looking at a popular problem in recursion: finding the factorial of a number.
def factorial(number):
"""factorial recursive implementation"""
if number <0:
return -1
elif number < 2:
return 1
else:
return number * factorial(number-1)
factorial(5)
First of all factorial(5) * 5 is called. But because 5 is greater than 2, factorial(5) will again trigger a call to factorial(5-1) * 5-1. This will continue until one of the conditions specified evaluates to true. This happens when factorial(1) is called. Because 1 is less than 2 factorial(1) returns some value that is then passed to the functions below it in the stack. Of course after factorial(1) * 1 returns, it is popped from the stack. visualize it this way :
factorial(1) * 1
factorial(2) * 2
factorial(3) * 3
factorial(4) 4
factorial(5) 5
Note that the item at the bottom is the first item loaded into the call stack
Because 1 is less than 2, based on our function definition, factorial(1) will return 1 and this output is then multiplied by 1. The result from the layer above is then passed to the function below: 1 is passed to factorial(2). factorial(2) then returns what it’s been passed and the output, 1, is multiplied by 2. Thus the second layer returns 2 and again this is passed to the function below, which is factorial(3). It continues this way until the function at the bottom of the stack returns.
This is how recursive functions are executed !
Still Don’t get it?
Well just give up on recursion and keep using your loops… lol
But see, frankly speaking, any recursive function could be implemented with loops. For example, the reverse string and factorial functions above could be implemented using loops like so:
def reverse_string(string):
“””iterative implementation”””
length = len(string) - 1
reversed_string = " "
while length >= 0:
reversed_string += string[length]
length -= 1
return reversed_string
def factorial(number):
"""iterative implementation of factorial"""
if number <0:
return -1
elif number < 2:
return 1
else:
factorial = 1
for num in range(1, number+1):
factorial = factorial * num
return factorial
Furthermore, when compared with their iterative counterparts, recursive solutions do not necessarily have better space and time complexity. In fact, because recursive functions repeatedly add stack frames to the call stack, one could even argue that they have a terribly bad space complexity. Recursive solutions are just more elegant.! They are more concise! This in turn improves code readability and by extension code quality.
References
Freecodecamp: How Recursion Works Explained
Youtube: Recursion for Beginner, a Beginners Guide to Recursion
Latest comments (0)