Recursion in Python
🔹 1️⃣ What is Recursion?
Definition:
Recursion is a programming technique where a function calls itself directly or indirectly to solve a
problem.
In simple words —
A recursive function is one that solves a small part of the problem, and then calls itself again for the
remaining part.
Each recursive call reduces the problem size, until it reaches a base case that stops the recursion.
🔹 2️⃣ Syntax of a Recursive Function
A recursive function must have two parts:
1. Base Case — condition that stops the recursion.
2. Recursive Case — where the function calls itself.
def recurse():
if (base_condition):
return result # Base Case
else:
recurse() # Recursive Case
🔹 3️⃣ Example: Simple Recursion
Example: Print numbers from 1 to 5 using recursion.
def print_numbers(n):
if n == 0: # Base case
return
print_numbers(n - 1) # Recursive call
print(n)
print_numbers(5)
Output:
1
2
🔹 4️⃣ Working of Recursion (Step by Step)
Let’s trace the above example 👇
Step Function Call Action
1 print_numbers(5) Calls print_numbers(4)
2 print_numbers(4) Calls print_numbers(3)
3 print_numbers(3) Calls print_numbers(2)
4 print_numbers(2) Calls print_numbers(1)
5 print_numbers(1) Calls print_numbers(0) (Base Case)
6 print_numbers(0) Returns (stops recursion)
7 Then the function prints values while unwinding
So recursion first goes deep into calls (stacking) → reaches base case → then comes back
(unwinding).
🔹 5️⃣ Main Components of Recursion
🧩 a) Base Case
The condition where the recursion stops.
Prevents infinite calls.
Must always be included.
Example:
if n == 0:
return 1
🧩 b) Recursive Case
The part of the function that calls itself.
Reduces the size of the problem.
Example:
return n * factorial(n - 1)
🧩 c) Call Stack
When a function is called, Python stores its current state (variables, execution point) in a
call stack.
Every new recursive call adds a new frame (layer) on top of the stack.
When the base case is reached, the stack unwinds — removing frames one by one.
🔹 6️⃣ Understanding the Call Stack (Visualization)
Example: factorial of 3
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(3))
⚙️Step-by-step execution:
Step Call Return Value
1 factorial(3) 3 × factorial(2)
2 factorial(2) 2 × factorial(1)
3 factorial(1) 1 × factorial(0)
4 factorial(0) returns 1 (base case)
Now unwinding happens:
factorial(1) = 1 × 1 = 1
factorial(2) = 2 × 1 = 2
factorial(3) = 3 × 2 = 6
✅ Final Output: 6
🔹 7️⃣ Unwinding in Recursion
Unwinding = when the recursion starts returning back after reaching the base case.
Example Flow:
factorial(3)
→ factorial(2)
→ factorial(1)
→ factorial(0) = 1 # Base Case
Now the stack starts unwinding:
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
So unwinding means the process of returning results back up the stack.
🔹 8️⃣ Types of Recursion
Let’s discuss all types clearly 👇
🌀 1. Direct Recursion
A function calls itself directly.
def greet():
print("Hello")
greet() # Direct recursion
⚠️Must have a base case, or it’ll cause infinite recursion.
🔁 2. Indirect Recursion
A function calls another function, and that function calls the first one.
def funcA():
print("A")
funcB()
def funcB():
print("B")
funcA()
⚠️Without a base case, this also becomes infinite.
📉 3. Tail Recursion
If the recursive call is the last statement in the function.
def tail_sum(n, total=0):
if n == 0:
return total
return tail_sum(n - 1, total + n)
✅ Optimized recursion — easy to convert to iteration.
📈 4. Head Recursion
If the recursive call happens first, and then the result is processed.
def head_recursion(n):
if n == 0:
return
head_recursion(n - 1)
print(n)
Here, printing happens after returning — during unwinding.
🔂 5. Linear Recursion
Only one recursive call is made each time.
Example: factorial, sum of digits.
🌳 6. Tree Recursion
Function calls itself multiple times inside one call.
Example: Fibonacci series
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
The recursion here branches out like a tree.
🔹 9️⃣ Advantages of Recursion
✅ Easier to write and understand for problems like factorial, Fibonacci, tree traversals, etc.
✅ Reduces code size for repetitive problems.
✅ Some problems are naturally recursive (e.g., file directory traversal).
🔹 🔟 Disadvantages of Recursion
⚠️Consumes more memory (each call stored in stack).
⚠️Slower compared to loops due to function call overhead.
⚠️Risk of stack overflow if base case is missing.
