Recursion is a difficult topic to understand for beginners. Sometimes it is a difficult a full study case in the academy that shows why it is important to master the topic. Therefore, many students ask how important is recursion in programming? Thinking that maybe they will never have to use in a real-life situation.
The short answer to this question is a lot! Recursion is very important in many topics in computer science. It is a must-have skill that you will want to have on your stock. For instance, a prerequisite to learning the tree data structure and algorithms (which have many applications) is recursion.
Let me show you how important recursion is in programming using some examples. But before showing you the examples, I’ll give you a necessary background for you to understand the examples.
What is recursion in programming?
As you might know, we use programming to model problems from the real-life. Some other problems are just abstractions, but still, we model them and give a solution using a certain programming language.
Sometimes there are big differences in how other programming topics are implemented in specific programming languages. But it is not the case of recursion. Although I’ll write the examples in python, you will see that it is the same in other programming languages.
We can think about recursion as a way to define a problem using a smaller instance of the same problem.
So, if you can define a problem (or the solution) by using smaller instances of the same problem, then you can do it using recursion.
A typical example you will find in books (maybe not the more appropriate) is the factorial of a number. A factorial of the number is defined as follows:
f(n) = n * f(n-1), f(0)=f(1)=1As you can see from the example, you calculate the factorial of n by multiplying n times the factorial of n-1 (same problem, smaller instance).
I mentioned that maybe this is not the more appropriate example, because we if there is a simple non-recursive implementation to solve a problem, we have to use it. In this case, there is one.
But it is easy to get a picture of what recursion with this example.
Now, let’s look at real problems that show us how important is recursion in programming.
Examples
The first problem is the game The Towers of Hanoi. There is a great explanation in this Wikipedia article of the origin and some history behind the game.
A brief summary of the game. We have three towers in a row and n disks, the disks are of different size. The rules are simple, move all the discs from tower 1 to tower 3, moving only one disc each time. Also, at any time a bigger disk cannot be on top of a smaller disk.
It is a game played by many kids.
Can a computer play this game? Sure, let’s create the algorithm that will make the computer play the game.
Iterative solution
See an example of an iterative solution implemented in c.
I borrowed the code bellow form this blog post.
Just see the code and keep scrolling down. Don’t try to understand it now.
// C Program for Iterative Tower of Hanoi
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
// A structure to represent a stack
struct Stack
{
unsigned capacity;
int top;
int *array;
};
// function to create a stack of given capacity.
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack =
(struct Stack*) malloc(sizeof(struct Stack));
stack -> capacity = capacity;
stack -> top = -1;
stack -> array =
(int*) malloc(stack -> capacity * sizeof(int));
return stack;
}
// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{
return (stack->top == stack->capacity - 1);
}
// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{
return (stack->top == -1);
}
// Function to add an item to stack. It increases
// top by 1
void push(struct Stack *stack, int item)
{
if (isFull(stack))
return;
stack -> array[++stack -> top] = item;
}
// Function to remove an item from stack. It
// decreases top by 1
int pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack -> array[stack -> top--];
}
//Function to show the movement of disks
void moveDisk(char fromPeg, char toPeg, int disk)
{
printf("Move the disk %d from \'%c\' to \'%c\'\n",
disk, fromPeg, toPeg);
}
// Function to implement legal movement between
// two poles
void moveDisksBetweenTwoPoles(struct Stack *src,
struct Stack *dest, char s, char d)
{
int pole1TopDisk = pop(src);
int pole2TopDisk = pop(dest);
// When pole 1 is empty
if (pole1TopDisk == INT_MIN)
{
push(src, pole2TopDisk);
moveDisk(d, s, pole2TopDisk);
}
// When pole2 pole is empty
else if (pole2TopDisk == INT_MIN)
{
push(dest, pole1TopDisk);
moveDisk(s, d, pole1TopDisk);
}
// When top disk of pole1 > top disk of pole2
else if (pole1TopDisk > pole2TopDisk)
{
push(src, pole1TopDisk);
push(src, pole2TopDisk);
moveDisk(d, s, pole2TopDisk);
}
// When top disk of pole1 < top disk of pole2
else
{
push(dest, pole2TopDisk);
push(dest, pole1TopDisk);
moveDisk(s, d, pole1TopDisk);
}
}
//Function to implement TOH puzzle
void tohIterative(int num_of_disks, struct Stack
*src, struct Stack *aux,
struct Stack *dest)
{
int i, total_num_of_moves;
char s = 'S', d = 'D', a = 'A';
//If number of disks is even, then interchange
//destination pole and auxiliary pole
if (num_of_disks % 2 == 0)
{
char temp = d;
d = a;
a = temp;
}
total_num_of_moves = pow(2, num_of_disks) - 1;
//Larger disks will be pushed first
for (i = num_of_disks; i >= 1; i--)
push(src, i);
for (i = 1; i <= total_num_of_moves; i++)
{
if (i % 3 == 1)
moveDisksBetweenTwoPoles(src, dest, s, d);
else if (i % 3 == 2)
moveDisksBetweenTwoPoles(src, aux, s, a);
else if (i % 3 == 0)
moveDisksBetweenTwoPoles(aux, dest, a, d);
}
}
// Driver Program
int main()
{
// Input: number of disks
unsigned num_of_disks = 3;
struct Stack *src, *dest, *aux;
// Create three stacks of size 'num_of_disks'
// to hold the disks
src = createStack(num_of_disks);
aux = createStack(num_of_disks);
dest = createStack(num_of_disks);
tohIterative(num_of_disks, src, aux, dest);
return 0;
}
Ugh! That is a lot of code for something that looks like a simple problem.
It is quite of lengthy code. But that is how can be implemented without using recursion.
As you will see below, one of the advantages of using recursion is to have less, clearer and easy to understand code.
Using recursion
Let me show now a code in python that uses recursion.
# Move n discs from column1 to column3 using column2
def hanoi(n, column1, column3, column2):
if n == 1:
print (f"Move disk {n} from {column1} to {column3}")
else:
# move n-1 disks from colum1 to column2 using column 3
hanoi(n-1, column1, column2, column3)
print(f"Move disk {n} from {column1} to {column3}")
# move n-1 disks from column2 to column3 using column 1
hanoi(n-1, column2, column3, column1)
if __name__ == '__main__':
hanoi(2, 1, 3, 2)
The answer is yes, and it can happen because of recursion. So, imagine if you don’t know recursion, you have to create the first code. But if you understand recursion you can create the second one.
Which one do you think it will be better for you? Is it worthy to spend time learning recursion if you want to be a good programmer? You can answer those questions in the comment section.
Let’s study the python solution to get a better understanding of what is happening. Remember that in the case of recursion, it is almost the same in every programming language. It is not short or clear just because is python. It is like that because of the method.
So, the main problem is to move n discs from tower 1 (column1 in the python code) to tower 3 (column 3 in the python code) using tower 2 (column 2). That is exactly the function definition.
def hanoi(n, column1, column3, column2):
Analysing the code, we can see that the problem is defined in terms of smaller instances (two) of the same problem:
- hanoi(n-1, column1, column2, column3)
- hanoi(n-1, column2, column3, column1)
The smaller instances are, move n-1 discs from tower 1 to tower 2 using 3 as auxiliary, and then move n-1 discs from tower 2 to tower 3 using 1 as auxiliary. Notice the instances are smaller because the size of the original one is n, and the other two are of size n-1.
This is basically a logical division of your problem. If you think about it, move n-1 discs from 1 to 2 using 3, then you can move the biggest disk from 1 to 3. Now what is left is to move n-1 discs from 2 to 3 using 1 as auxiliary.
In recursion, we always must have a trivial or base case. In our example is when n=1. Why do we call it trivial? Because if n equals 1, the solution is trivial: move the disc from column 1 to column 3.
if n == 1:
print (f"Move disk {n} from {column1} to {column3}")
The power of is that we don’t have to visualise the whole solution, you just model the solution using smaller instances, and combine them. Then recursion does its magic.
Isn’t it awesome?
As you already saw, recursion is a powerful tool to have. However, there is something we have to consider.
You should only use recursion when the iterative version (iterative means there is no recursion) is complex and difficult to maintain.
Recursions add a lot in spatial complexity (amount of memory that is needed to execute the program). This means that this type of algorithms uses a lot more of memory that iterative algorithms.
Said that, don’t use recursion to calculate the factorial of a number. The iterative solution is very easy to implement and have almost the same number of lines of code that when using recursion.
Summary
I hope by now you understand how important recursion in programming is.
I’ll just say it again, recursion in programming is extremely important to create simple and clear algorithms! Although it must be used with caution.
To create a solution using recursion, we must do the following steps:
- Identify the trivial case. Here is when the recursion is not needed anymore.
- Model the solution using smaller instances of the same problem.
- Combine the solutions to the smaller problems to give the solution to the original problem.
Related topic:
How to learn algorithms in programming
H@appy coding!