Recursion is a fun programming concept but can be a little tricky to learn. Recursion simply means something that repeats itself. If you want to see a cheeky example of recursion, try searching for recursion on Google. You will find an Easter egg where the search result suggestions are recursive. If, on the other hand, you would like to learn how to code a recursive function, read on!
What is a Recursive Function?
A recursive function is a function that calls itself. You essentially create a loop with a function. As you can imagine, these can be tricky functions to write. You do not want your code to run forever.
Similar to a loop, a recursive function will be controlled by a condition. Once the condition is met, the function stops calling itself, which stops the loop. This is how you can create a function that calls itself without it running forever.
Although a recursive function acts like a loop, it is executed by the computer differently. So, some algorithms are more efficient in a loop and others benefit from a recursive function. But before we look at how to use a recursive function, you need to know how to write one.
How to Write a Recursive Function
All recursive functions have the same basic structure:
FUNCTION name
IF condition THEN
RETURN result
ELSE
CALL FUNCTION name
END FUNCTION
The above example is written in pseudo-code. It outlines the structure of the function, which can be applied to any language. For simplicity, in this article, we will concentrate on Python.
The first thing to note about a recursive function is that when the condition is met, the function exits the recursion. This means when you write a recursive function, the first thing you will want to determine is when to stop the recursion.
If the condition is not met, the function will call itself. So, if you want to send information to the next loop, you will have to send it as an argument in your function. This can give recursive functions much more power.
Recursive Function Example in Python
It will be much easier to understand how recursion works when you see it in action. To demonstrate it, let's write a recursive function that returns the factorial of a number.
Factorials return the product of a number and of all the integers before it. For example, the factorial of 5 is 5 x 4 x 3 x 2 x 1 or, 120.
def factorialFunction(numberToMultiply):
if numberToMultiply == 1 :
return 1
else :
return numberToMultiply * factorialFunction(numberToMultiply - 1)
result = factorialFunction(3)
print(result)
//Outputs: 6
The above program will give you the result 6, which is the factorial of the number 3. This can be a little confusing at first. It will help if we run through the program step-by-step.
- When the function is called, numberToMultiply equals 3.
- The condition is not met, so we go into the else condition.
- Our function returns 3 * but is then paused. It must call itself to determine the rest of the value it is returning.
- When the function is called this time, the value of numberToMultiply equals 2.
- The condition is not met, so we go into the else condition.
- Our function returns 2 * but is then paused. It must call itself to determine the rest of the value it is returning.
- The function is called yet again. This time, the value of numberToMultiply equals 1.
- Our if condition is met. The function returns 1.
- The function from step 6 can now return 2 * 1 to the function on step 3.
- The function on step three can now return 3 * 2 * 1, which is 6.
Recursion is a tricky concept. It can be helpful to think of it as stacking one function on top of another function. Once one function is finally resolved, it can send the information back down the stack, until all the functions have their answer.
This is actually pretty much what your computer does. When you call the function, it is held in memory until it is returned. This means that recursive functions can use much more memory than a loop.
So, it might not be efficient to write loops as recursive functions, but it is a great way to practice constructing them. You should be able to code loops as recursive functions with similar results.
An Example of How to Convert a Loop to a Recursive Function
print("Enter an even number:")
i = int(input())
while (i % 2) != 0 :
print("That number is not even. Please enter a new number:")
i = int(input())
This loop can also be written recursively as:
def recursiveFunction(number) :
if (number % 2) == 0 :
return number
else:
print("That number is not even. Please enter a new number:")
recursiveFunction(int(input()))
print("Enter and even number:")
i = recursiveFunction(int(input()))
The first step is to determine when you want your function to stop. In this case, we want it to stop once an even number is entered. In our example, number tracks the user's input. If they input an even number, we return the number. Otherwise, we will continue to ask for a new number.
To set up the loop, we call our function again. But this time, the number we pass to the next function is the new number entered in by the user. The next function call will check the number.
This is a really bad function! Yes, it is checking if the number is even, like our loop, but it isn't efficient. Each time the user enters an odd number, the function is held in memory and a new function is called. If you do this enough times, you will run out of memory!
A Real-World Example of a Recursive Function
The above examples were good examples of when not to use recursion. So, where is recursion used? A good example of when you would want to use recursion is searching a binary tree.
When data is structured in a binary tree, you have to go down a lot of paths to search for data. At each point in the tree, you have to decide whether you want to continue to search on the right or left. You could save which part of the tree you visited in a variable, but a recursive function can naturally track that information.
Imagine that we are looking for the number six in the tree above. We could make a recursive function that searches the tree from left to right. The algorithm would look something like this:
FUNCTION searchTree(branchToSearch)
IF find 6 OR end of tree THEN
RETURN result
ELSE
PROCESS branch
CALL FUNCTION searchTree(left)
CALL FUNCTION searchTree(right)
END FUNCTION
In this pseudocode example, the algorithm would search the left side of the tree first. Each time it visits a new number, the function is paused and held in memory. This allows us to track where we have been.
The algorithm will always search the left side as far as it can first. once it reaches the end of the tree, the searchTree(left) will complete and it will check the right side. Once both sides are checked, the search backs up one branch and continues to check the right side.
If the algorithms searched the whole tree, it would do it in the order:
2, 7, 2, 6, 5, 11, 5, 9, and 4
See if you can follow along using the pseudo-code above.
Review of Recursion
Recursion is an advanced topic. It will take some time to understand and even longer to get good at coding it. It will help if you walk through recursive functions step by step. It might even help to stack index cards or post-it notes as you go through a function when learning to represent each function call.
When writing a recursive function, begin by deciding how you want to exit the function. Next, determine how to set up your loop. Identify what information needs to be sent to the next function call and what needs to be returned.
The best way to learn recursion is to practice it and learn from your mistakes. Look at some of your old code and challenge yourself to re-write loops as recursive functions. It likely won't make your code more efficient, but it will be good practice.