DEV Community

loading...
Cover image for understanding recursion

understanding recursion

Gabriele Boccarusso
programmer and tech appassionate
Updated on ・4 min read

Recursion is a function that calls itself, and if this phrase can make it look simple, it can get complicated very quickly.
In this article we'll see the difference between recursion and iteration, when to use it, how to use it, how it actually works and its possible problems.

Table of contents:

  1. How its made?
    1. The base case
    2. The normal case
  2. How recursion works
  3. Possible problems
  4. Example in varius languages

How its made?

It all begins with the main function that calls the recursive function, and for then the function calling itself.
The pseudocode for it will be similar to
pseudocode of a calling of a recursive function

obviously, everything begins with a calling from the main function, for then the function taking two possible ways: calling itself or the base case.

The base case

Without the base case, the recursion would never stop, and it would break the program.
The most common way is to use an if...else statement.
Through this guide will use the most simple example to understand it: the factorial.

If we want to calculate the factorial of a number we don't want the function to go on forever, but to stop at a certain point.
For the factorial of number 3, we would to

factorial_3 = 3 * 2 * 1
Enter fullscreen mode Exit fullscreen mode

And besides to multiplicate for one is useless, we could still do it, but with recursion, we can set it as the base case.

recursion_function (number)
{
  if (number <= 1) 
  {
    return 1
  }
  ...
Enter fullscreen mode Exit fullscreen mode

And in this way, we have prevented the recursion to be infinite, but there are still a lot of obscure points; we have talked about how to not make it go forever to not destroy our computer, but how do we actually write a recursive function?

The normal case

The normal case is not its exact name, but for understanding, it will be good enough to make the point clear.
If we want to calculate the factorial of a number with recursion we have to actually call the normal case in the other part of the if...else statement; so inside the else.

else 
{
  return number * recursive_function(number - 1)
}
Enter fullscreen mode Exit fullscreen mode

Let's take a moment to really understand what's going on here:
we return the number multiplied for itself minus 1, but we do it by calling the function so that the recursive function can be actually recursive.
If we look at the complete code of the function we will see the big picture:

recursive_function (number) 
{
  if (number <= 1) 
  {
    return 1
  }
   else 
   {
    return number * recursive_function(number * 1)
   }
}
Enter fullscreen mode Exit fullscreen mode

Ans those were the guidelines to write a recursive function that does actually work, but to use it in our work we have to actually understand what's going on and why.

How recursion works

When we call this function to calculate the factorial we pass a number as a parameter, what the function has to do is to reduce this number to one for then return the results, but said with words it can cause confusion.

First of all we set as the base case that every number that equals or is less than 1 return 0, this to make the function actually bugs free, otherwise, we could call the function with -4 or -7 and break the program, plus if we give 1 to the function it returns its factorial that is 1.

But what happens when we pass to the function 7, 4 or 3? Why and How it works?
Let's an example with the factorial of three:
what the recursion does under the hood
And now we know that the recursion calls itself with a different number each time, but when it does the actual calculus?

the various result of multiples calls to a recursive function
The actual result that we wants come only after the function has stopped calling itself.

Possible problems

Recursion can be a great way to make the code cleaner and is especially useful when used with problems that concerns data structures and advanced algorithms, but it can be very problematic if used in improper ways.

Recursion uses more processor time, sometimes a recursive solution can be more complicated and harder to debug than its iterative counterpart, if used for the wrong things it can even end with a stack overflow.

Example in various languages

python

def factorial (number):
  number = int(number)
  if number <= 1:
    return 1
  else:
    return number * factorial(number - 1)

def main ():
  number = input('enter a number: ')

  number = factorial(number)

  print(f'its factorial is: {number}')

main()
Enter fullscreen mode Exit fullscreen mode

Cpp

#include <iostream>

using namespace std;

int factorial (int number)
{
    if (number <= 1)
    {
        return 1;
    }
    else 
    {
        return number * factorial(number - 1);
    }
}

int main()
{
    int number;

   cout << "enter a number: ";
   cin >> number;

   number = factorial(number);

   cout << "its factorial is " << number;

   return 0;
}
Enter fullscreen mode Exit fullscreen mode

Javascript

const factorial = number => {
    if (number <= 1) {
        return 1;
    } else {
        return number * factorial(number - 1);
    }
}

let number = factorial(number);

console.log(number);
Enter fullscreen mode Exit fullscreen mode

Recursion can be very complicated or very easy, but after this little guide it should be clearer how to use it in your programs, for any doubt feel free to leave a comment.

Discussion (0)