Recursion is a powerful programming technique where a function calls itself to solve a problem. It allows complex problems to be broken down into simpler, more manageable subproblems.
It is built upon three key concepts: base case, recursive case & the call stack.
What is recursion?
The Base Case
The base case is a condition that stops the recursion. It defines the simplest instance of the problem, which can be solved directly without further recursion. If the base case is not defined, the function will call itself indefinitely, leading to a stack overflow.
def factorial(n): if n == 0: # Base case return 1
A recursive function must have at least one to prevent it from calling itself indefinitely.
The Recursive Case
The recursive case is the part of the function where the recursion happens. It reduces the problem into smaller subproblems and calls the function itself with these smaller inputs. The recursive case must eventually reach the base case.
def factorial(n): if n == 0: # Base case return 1 else: # Recursive case return n * factorial(n - 1)
Recursive Case
Call Stack
The call stack refers to the data structure that stores information about the active subproblems of a recursive function. Each time a function calls itself, a new frame (or context) is pushed onto the stack. This frame contains important details, including:
The function's parameters
Local variables
The return address (where to return after the function call completes)
Each time a recursive function calls itself, it is creating a new of that function on the call stack.
How the Stack Works in Recursion
1. Function Call
When a recursive function is called, a new stack frame is created. This frame contains all the necessary information to execute that specific call of the function.
2. Stack Growth
Each recursive call adds a new frame to the stack. This continues until a base case is reached.
3. Base Case Reached
Once the base case is encountered, the function starts returning values. Each returning function call removes its corresponding frame from the stack.
4. Unwinding the Stack
As the function returns, control goes back to the previous call, which continues execution from where it left off.
Which of the following is a base case in recursion?
Factorial Example
def factorial(n): # Base case if n == 0: return 1 # Recursive case else: return n * factorial(n - 1) # Example usage print(factorial(5)) # Output: 120
This recursive function factorial(n) calculates the factorial of a given number n. It has a base case where if n == 0, it returns 1 (since the factorial of 0 is defined as 1).
For all other values of n, the function returns n * factorial(n - 1), which continues to call itself with decreasing values of n until it reaches the base case.
For example, when factorial(5) is called, the function computes 5 * 4 * 3 * 2 * 1, ultimately returning 120. Each recursive call stores the current value of n and multiplies it by the result of the factorial of n-1.
Recursive Breakdown of factorial(5) Call
Let's break down what happens when factorial(5) is called:
Step 1: factorial(5)
Since n = 5 (not 0), it returns 5 * factorial(4).
Step 2: factorial(4)
Now, factorial(4) returns 4 * factorial(3).
Step 3: factorial(3)
factorial(3) returns 3 * factorial(2).
Step 4: factorial(2)
factorial(2) returns 2 * factorial(1).
Step 5: factorial(1)
factorial(1) returns 1 * factorial(0).
Step 6: factorial(0)
The base case is reached, so factorial(0)
The process of breaking a problem down into smaller subproblems that resemble the original problem is known as .
