Understanding recursion the simple way

Recursion is a fundamental concept in computer science where a problem is solved by breaking it down into smaller, simpler subproblems. The process involves calling the function recursively, executing the tasks sequentially, and storing intermediate results in the call stack. The goal is to reach the base case, which is a termination condition. Once the base case is reached, the recursive calls are resolved in a LIFO (last in, first out) order, allowing the results to be combined and ultimately solve the original problem.

Story of 100 gold chains!

In a remote area, there was a deep well rumoured to hold hidden treasures. An adventurous excavator, eager to uncover the riches, embarks on a quest to gather the gold chains hidden within the well. However, he soon realises that the deeper he descends into the well, the heavier the chains become when carried in his pocket. Climbing back up with all the chains at once would be an arduous task.

Undeterred by the challenge, the excavator devises a clever strategy. He places a sturdy ladder into the well and begins his descent. As he descends, he keeps track of each gold chain he discovers. Instead of carrying them in his pocket, he hangs each chain on the ladder's rungs. By doing so, he lightens his load and continues his search for more chains.

With each step deeper into the well, the excavator encounters more chains, diligently hanging them on the ladder. He repeats this process until he reaches the bottom, finding the last chain. At this point, he has only one chain in hand while all the others are hanging on the ladder.

Satisfied with his findings, the excavator commences his ascent, knowing he must retrieve the chains he left behind. As he climbs, he collects each chain from the ladder, one by one. Eventually, he emerges triumphant from the well, holding all 100 gold chains in his hands.

What is recursion?

The process of a function calling itself is called recursion. And the function that calls itself is said to be a recursive function.

When a function that is being executed calls itself, a small temporary copy of the same function is created in runtime, and the copy function begins to execute. This process goes on until the termination condition is satisfied.

To understand recursion, we must know that a function is like a machine that takes an input value, processes it, and returns an output value.

Recursion in factorial

Let's take an example of factorials 5! = 1x2x3x4x5

This problem can be divided into smaller subproblems. If you observe closely, the operation performed here is the multiplication of two numbers.

The problem can be rewritten as

$$5! = 5* [4 * [3 * (2 * 1)]]$$

Steps to solve

5 x [4]!

      ↳ 4 x [3]!

             ↳ 3 x [2]!

                    ↳ 2 x [1]!

Algorithm

1. Define a function 'factorial' that finds the product of all numbers less than 'n'.

2. Declare n = 5

3. When we call the function 'factorial' with parameter value n = 5, since the value of n > 1, the function multiplies the value n = 5 by a value returned by a function named 'factorial' with parameter value n = (n-1) i.e. 4. This function is a temporary copy of the original function.

4. This process is repeated until the termination condition or the base condition i.e. n <= 1 is satisfied. And until this condition is satisfied, all the previous processes are stored in the stack memory.

5. Once the base condition or the last condition in the process is met and the assigned value is returned by the function, the processes stored in the stack memory begin to execute in LIFO (last in first out) order.

2 x 1 = 2
        2 x 3 = 6
                6 x 4 = 24
                        24 x 5 = 120

Given below is a java code for the same.

public class Factorial {
    public static int factorial(int n) {
        if (n > 1) {
            return n * factorial(n - 1); // Recursive case: multiply number by factorial of (n-1)
        } 
        else {
            return 1; // Base case: number is less than or equal to 1
        }
    }

    public static void main(String[] args) {
        int number = 5;
        int result = factorial(number);
        System.out.println("Factorial of " + number + ": " + result);
    }
}