Python Recursion
4 min read ·
Recursion means a function calling itself.
Instead of solving a big problem at once, recursion solves a small part of the problem and then calls itself to solve the remaining part.
The same function repeats until a stopping condition is reached.
Why Recursion Exists
Some problems are naturally repetitive in nature.
Examples
Calculating factorial
Traversing folders inside folders
Working with tree structures
Breaking a number into digits
In such problems recursion makes the logic easier to understand.
Two Mandatory Parts of Recursion
Every recursive function must contain two things.
Base Condition
The base condition tells Python when to stop calling the function.
Without it the function will keep calling itself forever.
Recursive Call
The recursive call is the function calling itself with a smaller input.
This moves the problem closer to the base condition.
Important
If either base condition or recursive call is missing recursion will fail.
First Recursion Example Explained Step by Step
Execution flow
show(3) prints 3
show(2) prints 2
show(1) prints 1
show(0) stops execution
The function stops because base condition is met.
Understanding the Call Stack
Python uses a call stack to remember function calls.
Each recursive call is placed on the stack.
The function finishes only after the inner call finishes.
Real World Scenario
Think of stacked plates. You can remove the top plate first. Recursion works the same way.
Factorial Using Recursion With Clear Logic
Factorial means multiplying a number by all numbers below it.
5 factorial equals
5 multiplied by factorial of 4
4 multiplied by factorial of 3
Until factorial of 1
Flow explanation
factorial(5) waits for factorial(4)
factorial(4) waits for factorial(3)
factorial(1) returns 1
Values return in reverse order
Returning Values in Recursion
Return does not go forward.
Return comes back step by step.
Each function waits for the return value of the next function call.
Sum of Numbers Using Recursion
Working
4 plus sum of 3
3 plus sum of 2
2 plus sum of 1
1 plus sum of 0
0 stops recursion
Recursion vs Loop Explained Simply
Loop
Repeats using a single function call
Uses less memory
Recursion
Creates multiple function calls
Uses more memory
Recursion is chosen for clarity not speed.
Pro Tip
If recursion depth becomes large convert recursion into a loop.
Fibonacci Using Recursion Explained
Why this is slow
Same values are recalculated many times
This increases function calls rapidly
Optimizing Recursion With Memoization
Memoization stores already calculated values.
This avoids repeated calculations.
Recursion With Strings
Each call removes one character until string becomes empty.
Recursion With Lists
Index increases until list ends.
Tail Recursion Explained
Tail recursion happens when recursive call is the last statement.
Python does not optimize tail recursion.
Common Recursion Mistakes
Missing base condition
Wrong stopping condition
Very large input values
Caution
Always test recursion with small values first.