Recursion in Programming

In today’s post, we will discuss a very important topic within programming: recursion. It’s true that it can be a tricky concept when you first study it, but it’s actually quite simple. Also, it’s worth mentioning that recursion is not exclusive to the .Net environment but is useful for all programming languages.

1 - What is recursion in programming?

Recursion is a concept where a method calls itself. When you create a recursive method, you need to make sure that it will eventually stop calling itself, meaning the cycle must be finite. Inside the method, you must ensure it doesn't get stuck in endless self-calls.

We must be very careful when making recursive calls. If we use recursion carelessly, we could overflow the computer’s memory, causing the program to crash.

2 - When to use recursion?

As you can see from the description above, we can use recursion to replace any type of loop. However, in the professional world, it isn’t used extensively because mistakes can be catastrophic for memory. For instance, working with a list containing millions of items can use up a lot of memory. Still, most of the time, recursion is used for search or sorting algorithms.

The base case refers to the terminating condition for recursion.

Example 1

An example is calculating the factorial of a number.^{*Multiplying all numbers between two integers. In mathematics, it’s expressed as n! where n is the last number to check. You should start from 1.}

Example using an iterative method

public static int IterativeFactorial(int number){    int i, result = 1;    for(i = 1; i <= number; i++)    {        result = result * i;    }    return result;}

The example using a recursive method

public static int RecursiveFactorial(int number){    if (number == 0) return 1;    return number * RecursiveFactorial(number - 1);}

3 - The recursion stack

A computer’s memory is divided into 4 segments

• Code segment: stores the program’s instructions in machine code.
• Data segment: stores static variables or constants.
• Heap: stores dynamic variables.
• Program stack: used for local variables and parameters of the function currently executing.

When you call a function (or method), the process is as follows:

1. Space is reserved on the stack for the function’s parameters and its local variables.
2. The address of the code line from which the method was called is saved on the stack.
3. The function’s parameters and their values are stored on the stack.
4. Finally, memory allocated on the stack is freed when the function ends, and control returns to the original line of code.

But when the function is recursive:

• Each call generates a new function invocation with its own local variables.
• The process repeats each time the function calls itself, creating new parameters and local variables on the stack for each recursive call.
• When finished, the stack memory is released in reverse order, starting from the last-created function and ending with the first—this one being the last to be freed.