# What are and how to use recursive functions

Recursion is a concept in programming in which a function calls itself to solve a problem.

Recursion is always something problematic and difficult to understand. Especially for those who are just starting out in programming.

However, some problems are easier to solve by applying recursion. Not all, by any means. More of a small part of the problems.

## Operation of Recursion

In reality, recursion is easy to implement. We simply have a function that, at some point, invokes itself.

In reality, this structure is quite similar to a loop, in that it is a fragment of code that is executed several times.

However, it is not exactly the same. Each function call generates its own frame, where local variables are stored.

On the other hand, just as in a loop we have the risk of having an infinite loop, a recursive function can fall into an endless loop.

That is, when does this series of calls stop? At some point, the function has to do “something” other than calling itself. We will call these cases the base case.

As the base case is reached and the subproblems are solved, the recursive calls return, releasing the stack frames and allowing the original function to complete its task.

## How to detect recursive solutions

How can we detect solutions that might be easier to solve with a recursive approach?

When we have a problem that involves multiple steps, and the result of executing each step returns a problem that is similar to the previous one.

For example, let’s say we have a tray with 5 cakes and 5 guests. We need to give one cake to each guest.

We take the first cake and do whatever needs to be done. We decide if one guest is hungrier than another, if they are intolerant to something, if they prefer chocolate or cream. It doesn’t matter, the point is we assign a cake.

Now we have one cake assigned, and the remaining problem is the same. But now we have 4 cakes and 4 guests left. This is a very silly example, but it serves to explain recursion.

At each step, the new problem remaining is identical to the previous one, but with fewer elements. This indicates that a recursive approach could be simpler.

## Examples of recursive functions in different languages

Let’s see examples of recursive functions in different languages. To do this, we will use a very simple example, the calculation of the factorial of a number.

It is not the most interesting case in the world, nor the most practical. But it is very good because it is very simple.

Remember that a factorial is a mathematical function that multiplies an integer by all positive integers less than it, including the number itself.

For example, the factorial of 5 (denoted as 5!) is equal to 5 x 4 x 3 x 2 x 1, which is equal to 120.

We can identify that it is a problem susceptible to being solved by a recursive approach because, at each step, “what we have left to calculate” is identical to “what we have already calculated”.

That is,

And so on until we reach 1.

Let’s see how we would solve this problem recursively in different languages.

#include <iostream>

int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}

int main() {
int num = 5;
std::cout << "El factorial de " << num << " es: " << resultado << std::endl;
return 0;
}
using System;

public class Program {
public static int Factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * Factorial(n - 1);
}
}

public static void Main() {
int num = 5;
Console.WriteLine("El factorial de " + num + " es: " + resultado);
}
}
function factorial(n) {
if (n === 0 || n === 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}

let num = 5;
console.log(El factorial de ${num} es:${resultado});
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)

num = 5
print(f"El factorial de {num} es: {resultado}")

## Stack overflow and base cases

We have said that one of the problems of recursive functions is knowing when to stop. This is what we call the base cases.

If we do not stop the recursive calls, we get into an infinite loop. Each recursive call adds a stack frame to memory, and if these stack frames accumulate without being released, a stack overflow occurs.

Stack overflow occurs when a recursive function calls itself too many times, and the size of the call stack exceeds the established limit.

Let’s see an example that would generate a Stack Overflow.

int funcionRecursivaConStackOverflow(int n) {
return funcionRecursivaConStackOverflow(n + 1);
}

int main() {
int num = 0;
return 0;
}

In the previous example, the funcionRecursivaConStackOverflow function calls itself without a base case, which will cause a stack overflow and an abrupt closure of the program.

Therefore, we need one or more base cases that stop the process of recursive calls.

int funcionRecursivaConStackOverflow(int n) {
return funcionRecursivaConStackOverflow(n + 1);
}

int main() {
int num = 0;
return 0;
}

In this case, we have added a conditional that stops the recursive calls. If n > 10, the recursive call is not made.

In the example, the result of the entire series of calls would be to show 10 on the screen. We have just made a counter up to 10 unnecessarily complicated. But for the example, it works 😉

The important thing is to understand that a recursive function has to have some kind of condition in which it does not call itself. Otherwise, you will have an endless loop and a stack overflow.

## Logical equivalence of recursion - iteration

Any recursive function can be converted into a non-recursive function using an iterative approach. This often improves performance and avoids the risk of stack overflow.

For example, the calculation of the factorial in its recursive version

int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}

int main() {
int num = 5;
std::cout << "El factorial de " << num << " es: " << resultado << std::endl;
return 0;
}

Can be changed to an iterative version, for example as follows,

int factorialNoRecursivo(int n) {
for (int i = 1; i <= n; i++) {
}
}

int main() {
int num = 5;
std::cout << "El factorial de " << num << " es: " << resultado << std::endl;
return 0;
}

In this example, we have replaced the recursive function of calculating the factorial with a non-recursive version that uses a for loop to calculate the result iteratively.

• Ease: In certain specific cases, implementing a recursive solution can be simpler than an iterative solution

• Problem Division: Recursion allows us to divide a complex problem into simpler subproblems and solve each subproblem recursively.

• Efficiency for Hierarchical Structures: In problems involving hierarchical structures such as trees or graphs, recursion can be a natural and efficient way to traverse and manipulate these elements.