Introduction

Recursion in programming is a technique where a function calls itself directly or indirectly. This approach allows us to break down complex problems into smaller, more manageable chunks.

For an example,

def recursion():
    return recursion()

It is essential to note that, there must be a base case and a recursive case in a function. If the base case is not mentioned, the function will call itself continuously and the system's stack will be full.

That's how StackOverflow was found. Wait, what? Oops, that's when Stack Overflow exception is raised.

---

Stack

A stack is a special area of computer memory that stores information about a computer program's active subroutines or functions.

A new frame is added to the call stack each time a function is called. This frame contains the return address, local variables, parameters, and saved registers.

Yes yes, the behavior is similar to stack that we read in data structures.

---

Base Case and Recursive Case

• Base case: A condition under which the function should stop calling itself, to prevent the infinite recursion.

• Recursive Case: The part of a function where it calls itself with a modified argument towards the base case.

Let's take an example,

def print_upto_one(number):
    print(number)

    if number == 1:
        return

    print_upto_one(number-1)

Here, the function print_upto_one prints the passed number, calls itself again with decreased value. Also note that there is a condition to stop calling itself, i.e., when the value of number is 1.

• if number == 1: return is a base case where the function will stop calling itself.

• print_upto_one(number-1) is a recursive case when the function calls itself with a decreased value.

---

Recursion vs Infinite Loop

Wait, this sounds a lot like infinite loop. What's the difference?

Not exactly. Let's understand it this way,

Recursion is like Russian nesting dolls where each doll contains a smaller doll inside until you reach the smallest one.

Infinite Loop is like a song stuck on repeat, playing the same part endlessly.

A new stack frame will be allocated to each function call in recursion whereas an infinite loop runs in the same amount of memory. That's why endless recursion will raise stack overflow error but infinite loop will keep running until the user or the system terminates it explicitly.

---

Detailed Working of Recursion

Recursion works in stack memory. Each function called inside the function returns the value from where it is called.

Meaning, let's assume we have a function A and each function call as A1, A2, A3 and so on.

Now, when A1 calls A2 and A2 calls A3, A3 will return value to A2 and A2 will return value to A1 that the caller function can process.

Let's understand this with an example. This function calculates the sum of n natural numbers.

def sum(n):
    if n == 1:
        return 1
    inner_func_value = sum(n - 1)
    return n + inner_func_value

Visual Representation

Here, the function calls itself with a decreased value until the passed value reaches to 1. Then, every function output value is returned to the outer function, and so on.

I know I know, this is a bit confusing while getting started.

---

Factorial of a number using Recursion

Let's understand Recursion with one more example. This function will calculate the factorial of a number.

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

Now, let's also understand the function calls step by step.

factorial(3)                        # 1st call with value 3
    3 * factorial(2)                # 2nd call with value 2 (3-1)
        3 * (2 * factorial(1))      # 3rd call with value 1 (2-1)
        3 * (2 * 1)                 # 3rd call returns 1 (base case)
    3 * 2                           # 2nd call returns 2 (2 * 1)
6                                   # 1st call returns 6 (3 * 2)

Let's break down each step:

1. First call: factorial(3)

   • Calculates 3 * factorial(2)

2. Second call: factorial(2)

   • Calculates 2 * factorial(1)

3. Third call: factorial(1)

   • Base case: Returns 1 since factorial(1) = 1

4. Return to second call:

   • Calculates 2 * 1 = 2

   • Returns 2

5. Return to first call:

   • Calculates 3 * 2 = 6

   • Returns 6

So, the factorial of 3 is correctly calculated as 6.

---