Introduction

Based on merriam-webster.com, recursion is a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself one or more times until a specified condition is met.

The function that does the bolded sentence is called the recursive function. There’s a bunch of visual representations of how recursion works, such as the Sierpiński triangle and recursive tree shown below.

Recursive Tree & Sierpiński Triangle

Recursion is a great example of problem-solving methods in computer programming. Decomposition really plays its role in this algorithm. What is decomposition? You can read it here ;)

To solve our main problem here, which is to make our fifth recursion, we first have to know how to make the smaller triangle, and that is categorized as our sub-problem.

Direct and Indirect Function

To make everything seems clear, I'll provide you with some examples first.

void dirFun(){
  // some code..
  dirFun();
  // some code..
}

The code above is called as a direct function as it calls the same function dirFun()

void indirFun1(){
  // some code..
  indirFun2();
  // some code..
}

void indirFun2(){
  // some code..
  indirFun1();
}

Now this one is called as an indirect function as it calls another function (say, indirFun1) and it calls another function (indirFun2) directly or indirectly.

Specific condition

Earlier, I said that recursive function keeps calling itself one or more times until a specific condition is met. What did I mean by this? A specific condition is usually also called as a base condition, a condition which make our program stops at a certain condition, thus prevent to be an infinite loop.

Determining the right base condition

I believe example is a great way to visualize a concept, so we'll start with that again. Take a look at a block of code below.

int fact(int n){
  if (n == 100){ // <-- wrong base case!
    return 1;
  }
  else {
    return n*fact(n-1);
  }
}

On the code above, we use recursive function to find the factorial of a number n. Do you realize why it went wrong? First, let me translate that code into a more human-friendly language.

Hey, I’m gonna make a function to find the factorial of n. These are the requirements. If n is equal to 100, please give me 1. Whatever else, just gimme n*factorial(n-1) please!

Wait, what? A factorial will only equals to one if and only if the number n is 0 or 1, not 100. It's getting more clear now, isn't it?

What may happen if we keep running the function with the wrong base condition

Stack overflow! You may be familiar with this one ;) Well, stack overflow is an error in a computer program due to excessive memory usage. This error occurs in the call stack. We can imagine the stack as the container of our codes and it has a limited amount of memory available. Its size is determined by the programming language, architecture, whether multi-threading is available on the CPU, and how much memory is available. When stack overflow occurs, it usually freezes or closes the program. Ouch!

How iteration is related with recursion

You may wondering, is recursion function related to iteration and the answer to that is yes. Recursion is usually used as an alternative for making the code look cleaner and more simple. I have a code comparison using iteration and recursion below to find the total sum from the mumber a to number b.

Iteration

int main(){
 int a,b;
 cout << “a= “;
 cin >> a;
 cout << “b= “;
 cin >> b;
int sum = 0;
 for (int i=a; i<=b; i++){
 sum += i;
 }
 cout << “total sum from “ << a << “ to “ << b << “ is “ << sum;
 return 0;
}

Recursion

int recursion101(int a , int b){
 if (a == b){
 return a;
 } else {
   return a +recursion(a+1, b);
 }
}
int main(){
 int a,b;
 cout << “a= “;
 cin >> a;
 cout << “b= “;
 cin >> b;
cout << “total sum from “ << a << “ to “ << b << “ is “ << sum;
 return 0;
}

Note that i<=b in for (int i=a; i<=b; i++) and if (a == b) has the same functionality! They work as a base condition!

Even though recursion has cleaner code than iteration, it is not always necessary to use recursion. It is better to solve Fibonacci with iteration than recursion. Redundancy will happen if we refuse to use iteration. I made a small illustration to show it. In this illustration, Tia wants to find the 5th Fibonacci number by iteration and Rosi wants to find using recursion. When you use iteration, it keeps each previous value and then counts the next one, without setting them as an output. When you use recursive function, each time you iterate, it will set as a new value. On Tia’s side, there’s only one value at each F(n). But on Rosi’s side, there are two values of F(3) and F(0), three values of F(2), and five values of F(1).

Actually, the implementation of recursion is not as easy and simple as this one, but I hope this post will help you to grasp the general concept to understand the recursive algorithm and how it works. Great luck!