Recursion:

• Recursion is a programming technique where a function calls itself to solve a smaller part of the same problem.

• Each time the function calls itself, it breaks the problem down into smaller and smaller parts until it reaches a point where it can stop (the base case).

• It is a phenomenon when a function calls itself indefinitely until a specified condition is fulfilled

• if there is no condition to stop the recursive calls, the calls will run indefinitely until the stack runs out of memory ( stack overflow ).

• Recursion is useful when a problem can be divided into smaller, repeating subproblems that follow the same pattern.

Base case:

• it is the condition that is written in a recursive function in order for function to get completed and not to run infinitely.

• After encountering the base condition, the function terminates and returns back to its parent function simultaneously.(it is the stopping condition that prevents function calling itself infinitely).

Recursive case:

function calling itself until it reaches the base case, When a recursive call gets completed, the control returns back to its parent function which is then further executed until the last function waiting in the recursive stack returns.

Working:

Each recursive call waits for the result of the next call until the base case is reached. Once the base case returns a value, the function begins to adding up or combining results as it goes back up through each call.

What is Stack Overflow in Recursion?

Whenever recursion calls are executed, they’re simultaneously stored in a recursion stack where they wait for the completion of the recursive function. A recursive function can only be completed if a base condition is fulfilled and the control returns to the parent function.

But, when there is no base condition given for a particular recursive function, it gets called indefinitely which results in a Stack Overflow i.e, exceeding the memory limit of the recursion stack and hence the program terminates giving a Segmentation Fault error.

if there is no terminating condition for recursion to stop, hence it will also result in a memory limit exceeded error (the case of a Stack Overflow ).

Understanding recursion through example:

# Let’s calculate the sum of numbers from `num1` to `num2` using recursion.

def recursum(num1, num2):
    if num1 > num2:  # Base case
        return 0
    return num1 + recursum(num1 + 1, num2)  # Recursive case

# Usage
num1, num2 = 3, 6
print(recursum(num1, num2))  # Output: 18 (3 + 4 + 5 + 6)

Step-by-Step Explanation:

1. Initial Call: recursum(3, 6) returns 3 + recursum(4, 6)

2. Second Call: recursum(4, 6) returns 4 + recursum(5, 6)

3. Third Call: recursum(5, 6) returns 5 + recursum(6, 6)

4. Fourth Call: recursum(6, 6) returns 6 + recursum(7, 6)

5. Base Case (Fifth Call): recursum(7, 6) returns 0 (because num1 > num2) #

As each call returns, the results are combined:

- >6 + 0 = 6

- >5 + 6 = 11

- >4 + 11 = 15

- >3 + 15 = 18

Final Result: \(3 + 4 + 5 + 6 = 18\)