In the film “Edge of Tomorrow”, the main character, Major William Cage, fights against aliens and gets to relive the same day over and over again. Each time he dies, accidentally or with purpose, he is brought back to the same point in time. This special ability allows him to overcome the challenges he is facing by going through the same activities until he is able to defeat the aliens.

In computer science recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.

In other words recursion is a process in which a function calls itself as a subroutine. Functions that implement recursion are called recursive functions. The recursion process (the function calling itself) can continue until a certain condition is met.

Some of the problems, which can be solved with recursions are:

  • Fibonacci numbers
  • Factorial
  • Sorting
  • Sudoku

How recursion works?

If you want to go home you will call a function like “go_home”. In this function you will have the following steps:

  1. Make decision where to go
  2. Make a step
  3. If I am at home stop else go_home

In step 3 you can find the recursion and see how a function calls itself. In the pseudo code below is an example of go_home recursive function:

void go_home()
    if (I_am_at_home) then return;
    else go_home();

int main()
    ... ... ...
    ... ... ...
    return 0;

It is important for this type of functions that you always include a stop condition that will prevent executing the process over and over again (infinite loop).