Python Notes
HubHistory of Python - Complete Guide 2026Python Applications - Complete Guide 2026Python Features - Complete Guide 2026What is Python? - Complete Guide 2026Why Learn Python? - Complete Guide 2026Your First Python Program – Hello World & Beyond 2026How to Install Python on Windows, Mac & Linux – Complete Guide 2026Install VS Code for Python – Complete Setup Guide with Extensions 2026Python Environment Setup – Virtual Environments, pip & Project Structure 2026Python IDLE – Complete Guide for Beginners 2026Python CommentsPython Data TypesPython Input and OutputPython OperatorsPython SyntaxPython Strings BasicsPython Type CastingPython VariablesBreak, Continue and Pass in PythonElif Statement in PythonFor Loop in PythonIf-Else Statement in PythonIf Statement in PythonNested If in PythonPattern Programs in PythonWhile Loop in PythonDecorators in PythonFunction Arguments in PythonFunctions Basics in PythonGenerators in PythonLambda Functions in PythonRecursive Functions in PythonReturn Statement in PythonScope of Variables in PythonAbstraction in PythonClasses and Objects in PythonConstructors in PythonEncapsulation in PythonInheritance in PythonMagic Methods (Dunder Methods) in PythonMethod Overriding in PythonPolymorphism in PythonPython Comprehensions – List, Dict, Set & GeneratorPython Dictionaries – Key-Value StorePython Dictionary Methods – Complete ReferencePython List Methods – All Built-in MethodsPython Lists – Complete GuidePython Set Methods – Complete ReferencePython Sets – Unordered Unique CollectionsPython Tuples – Immutable SequencesPython Asynchronous Programming with asyncioPython Context ManagersAdvanced Python DecoratorsAdvanced Python GeneratorsPython Iterators - Advanced GuidePython Memory ManagementPython MultiprocessingPython MultithreadingCRUD Operations in Python DatabasesMySQL with Python (mysql-connector-python)ORM Introduction with SQLAlchemyPostgreSQL with Python (psycopg2)SQLite3 with PythonIntroduction to DjangoDjango Models and ORMDjango REST API with DRFDjango ViewsIntroduction to FlaskFlask RoutingFlask Templates with Jinja2Email Automation with PythonPDF Automation with PythonSelenium Web Automation with PythonTask Scheduler with PythonWeb Scraping with PythonData Analysis with PythonData Cleaning with PythonData Visualization ProjectData Visualization with MatplotlibNumPy IntroductionPandas IntroductionStatistical Visualization with SeabornClassification AlgorithmsClustering AlgorithmsIntroduction to Machine LearningMachine Learning Project: Churn PredictionModel Evaluation and SelectionRegression AlgorithmsSave pipeline (includes preprocessing + model)AI Assistant ProjectCalculator ProjectChatbot ProjectExpense Tracker ProjectFace Detection ProjectPassword Generator ProjectWeather App ProjectPython Coding Interview QuestionsPython OOP Interview Questions and AnswersPython Master CheatsheetPython Interview Questions and AnswersPython Best PracticesCommon Python Errors and SolutionsPython Debugging TechniquesPython Learning Resources
Python mein recursion ki complete guide — base case, recursive case, call stack, fibonacci, factorial, binary search aur tree traversal ke saath Hindi explanations.
Recursion woh technique hai jisme ek function khud apne aap ko call karta hai jab tak koi stopping condition (base case) nahi mil jaati.
1️⃣ Pehla Recursion — Countdown
Example
# ─────────────────────────────────────
# Simplest recursive function
# ─────────────────────────────────────
def countdown(n):
"""n se 0 tak countdown karta hai"""
# Base Case — yahan rukna hai
if n <= 0:
print("🚀 LAUNCH!")
return
# Current work karo
print(f" {n}...")
# Recursive call — chhoti problem
countdown(n - 1)
countdown(5)
Example
# OUTPUT:
5...
4...
3...
2...
1...
🚀 LAUNCH!
Example
# ─────────────────────────────────────
# Sum of first N numbers
# ─────────────────────────────────────
def sum_n(n):
"""1 se n tak ke numbers ka sum"""
# Base case
if n == 1:
return 1
# Recursive case: n + sum of (1 to n-1)
return n + sum_n(n - 1)
print(sum_n(5)) # 15 (1+2+3+4+5)
print(sum_n(10)) # 55 (1+2+...+10)
print(sum_n(100)) # 5050
Example
# OUTPUT:
15
55
5050
2️⃣ Factorial — Classic Recursion
Example
# ─────────────────────────────────────
# Factorial: n! = n × (n-1) × ... × 1
# ─────────────────────────────────────
def factorial(n):
"""
n ka factorial calculate karta hai.
n! = n × (n-1)!
Base case: 0! = 1, 1! = 1
"""
# Input validation
if not isinstance(n, int) or n < 0:
raise ValueError("n positive integer hona chahiye")
# Base cases
if n == 0 or n == 1:
return 1
# Recursive case
return n * factorial(n - 1)
# Test karo
for i in range(8):
print(f"{i}! = {factorial(i)}")
Example
# OUTPUT:
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
Example
# ─────────────────────────────────────
# Factorial call stack visualize karna
# ─────────────────────────────────────
def factorial_verbose(n, depth=0):
indent = " " * depth
print(f"{indent}▶ factorial({n}) called")
if n <= 1:
print(f"{indent}◀ Base case: factorial({n}) = 1")
return 1
result = n * factorial_verbose(n - 1, depth + 1)
print(f"{indent}◀ factorial({n}) = {n} × ... = {result}")
return result
print(f"\nFinal result: {factorial_verbose(4)}")
Example
# OUTPUT:
▶ factorial(4) called
▶ factorial(3) called
▶ factorial(2) called
▶ factorial(1) called
◀ Base case: factorial(1) = 1
◀ factorial(2) = 2 × ... = 2
◀ factorial(3) = 3 × ... = 6
◀ factorial(4) = 4 × ... = 24
Final result: 24
3️⃣ Fibonacci Series
Example
# ─────────────────────────────────────
# Fibonacci: f(n) = f(n-1) + f(n-2)
# ─────────────────────────────────────
def fib_simple(n):
"""nth Fibonacci number (simple but slow)"""
if n <= 0: return 0
if n == 1: return 1
return fib_simple(n - 1) + fib_simple(n - 2)
# Pehle 10 numbers
print("Fibonacci Series:")
fibs = [fib_simple(i) for i in range(11)]
print(fibs)
# ─── Problem: Exponential time complexity ───
# fib(30) → ~2^30 calls! Very slow for large n
# ─── Solution: Memoization ───
from functools import lru_cache
@lru_cache(maxsize=None) # Cache results
def fib_memo(n):
"""nth Fibonacci number (with memoization)"""
if n <= 0: return 0
if n == 1: return 1
return fib_memo(n - 1) + fib_memo(n - 2)
# Ab large numbers fast hain!
print(f"\nfib(50) = {fib_memo(50)}")
print(f"fib(100) = {fib_memo(100)}")
Example
# OUTPUT:
Fibonacci Series:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
fib(50) = 12586269025
fib(100) = 354224848179261915075
4️⃣ Tower of Hanoi
Example
# ─────────────────────────────────────
# Tower of Hanoi — Classic recursive puzzle
# ─────────────────────────────────────
"""
RULES:
1. Ek waqt mein sirf ek disk move karo
2. Badi disk chhoti disk ke upar nahi jaa sakti
3. n disks ke liye: 2^n - 1 moves lagte hain
"""
move_count = 0
def hanoi(n, from_rod, to_rod, aux_rod):
"""
n disks ko from_rod se to_rod pe move karo
using aux_rod as auxiliary.
"""
global move_count
if n == 1:
move_count += 1
print(f" Move {move_count:2d}: Disk 1 ║ {from_rod} ──► {to_rod}")
return
# Step 1: n-1 disks ko aux pe move karo
hanoi(n - 1, from_rod, aux_rod, to_rod)
# Step 2: Largest disk ko destination pe move karo
move_count += 1
print(f" Move {move_count:2d}: Disk {n} ║ {from_rod} ──► {to_rod}")
# Step 3: n-1 disks ko aux se to_rod pe move karo
hanoi(n - 1, aux_rod, to_rod, from_rod)
print("🗼 Tower of Hanoi (3 disks)")
print("=" * 35)
hanoi(3, "A", "C", "B")
print(f"Total moves: {move_count} (= 2³-1 = 7)")
| Move 1 | Disk 1 ║ A ──► C |
| Move 2 | Disk 2 ║ A ──► B |
| Move 3 | Disk 1 ║ C ──► B |
| Move 4 | Disk 3 ║ A ──► C |
| Move 5 | Disk 1 ║ B ──► A |
| Move 6 | Disk 2 ║ B ──► C |
| Move 7 | Disk 1 ║ A ──► C |
| Total moves | 7 (= 2³-1 = 7) |
5️⃣ Recursive Binary Search
Example
# ─────────────────────────────────────
# Binary Search — Divide & Conquer
# ─────────────────────────────────────
def binary_search(arr, target, low, high, steps=0):
"""
Sorted array mein target dhundhta hai recursively.
Returns: index ya -1
"""
steps += 1
# Base case: search space khatam
if low > high:
print(f" Steps taken: {steps-1}")
return -1
mid = (low + high) // 2
print(f" Step {steps}: Checking index {mid} → value={arr[mid]}")
if arr[mid] == target:
print(f" ✅ Found at index {mid} in {steps} steps!")
return mid
elif arr[mid] < target:
return binary_search(arr, target, mid + 1, high, steps)
else:
return binary_search(arr, target, low, mid - 1, steps)
# Sorted array
data = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91]
print(f"Array: {data}")
print(f"Size : {len(data)} elements\n")
print("🔍 Searching for 38:")
idx = binary_search(data, 38, 0, len(data) - 1)
print(f"Result: Index = {idx}\n")
print("🔍 Searching for 100:")
idx = binary_search(data, 100, 0, len(data) - 1)
print(f"Result: Index = {idx}")
| Array | [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91] |
| Size | 11 elements |
| Step 1: Checking index 5 | value=23 |
| Step 2: Checking index 8 | value=56 |
| Step 3: Checking index 6 | value=38 |
| Result | Index = 6 |
| Step 1: Checking index 5 | value=23 |
| Step 2: Checking index 8 | value=56 |
| Step 3: Checking index 10 | value=91 |
| Steps taken | 3 |
| Result | Index = -1 |
6️⃣ Flatten Nested List
Example
# ─────────────────────────────────────
# Nested list ko flat karna recursively
# ─────────────────────────────────────
def flatten(nested_list):
"""
Kitni bhi deep nested list ko flat karta hai.
"""
result = []
for item in nested_list:
if isinstance(item, list):
# Aur ek recursive call!
result.extend(flatten(item))
else:
result.append(item)
return result
# Test cases
simple = [1, [2, 3], [4, [5, 6]]]
deep = [1, [2, [3, [4, [5, [6, [7, [8]]]]]]]]
mixed = [[1, 2], [3, [4, 5]], [6, [7, [8, [9]]]]]
print(f"Input : {simple}")
print(f"Flat : {flatten(simple)}")
print()
print(f"Input : {deep}")
print(f"Flat : {flatten(deep)}")
print()
print(f"Input : {mixed}")
print(f"Flat : {flatten(mixed)}")
| Input | [1, [2, 3], [4, [5, 6]]] |
| Flat | [1, 2, 3, 4, 5, 6] |
| Input | [1, [2, [3, [4, [5, [6, [7, [8]]]]]]]] |
| Flat | [1, 2, 3, 4, 5, 6, 7, 8] |
| Input | [[1, 2], [3, [4, 5]], [6, [7, [8, [9]]]]] |
| Flat | [1, 2, 3, 4, 5, 6, 7, 8, 9] |
7️⃣ Directory Tree Traversal
Example
# ─────────────────────────────────────
# Folder structure recursively print karna
# ─────────────────────────────────────
import os
def print_tree(path, prefix="", is_last=True):
"""
Directory tree print karta hai recursively.
"""
connector = "└── " if is_last else "├── "
print(prefix + connector + os.path.basename(path))
if os.path.isdir(path):
new_prefix = prefix + (" " if is_last else "│ ")
try:
items = sorted(os.listdir(path))
for i, item in enumerate(items):
full_path = os.path.join(path, item)
is_last_item = (i == len(items) - 1)
print_tree(full_path, new_prefix, is_last_item)
except PermissionError:
print(new_prefix + "└── [Permission Denied]")
# Demo tree (using a mock structure)
def show_mock_tree():
"""Simulated directory tree"""
tree = {
"project": {
"src": {
"main.py": None,
"utils.py": None,
"models": {
"user.py": None,
"product.py": None,
}
},
"tests": {
"test_main.py": None,
"test_utils.py": None,
},
"README.md": None,
"requirements.txt": None,
}
}
def print_dict_tree(d, prefix="", name="root"):
items = list(d.items()) if isinstance(d, dict) else []
print(prefix + name + ("/" if isinstance(d, dict) else ""))
for i, (k, v) in enumerate(items):
is_last = (i == len(items) - 1)
sub_prefix = prefix + (" " if is_last else "│ ")
connector = "└── " if is_last else "├── "
if isinstance(v, dict):
print(prefix + connector + k + "/")
for j, (k2, v2) in enumerate(v.items()):
last2 = j == len(v) - 1
conn2 = "└── " if last2 else "├── "
print(sub_prefix + conn2 + k2 + ("/" if isinstance(v2, dict) else ""))
else:
print(prefix + connector + k)
print_dict_tree(tree["project"], "", "📁 project")
show_mock_tree()
# OUTPUT:
📁 project
├── 📁 src/
│ ├── main.py
│ ├── utils.py
│ └── 📁 models/
│ ├── user.py
│ └── product.py
├── 📁 tests/
│ ├── test_main.py
│ └── test_utils.py
├── README.md
└── requirements.txt
8️⃣ Memoization — Recursion Optimize Karna
Example
# ─────────────────────────────────────
# Memoization — results cache karna
# ─────────────────────────────────────
import time
# Without memoization (slow)
def fib_slow(n):
if n <= 1: return n
return fib_slow(n-1) + fib_slow(n-2)
# With manual memoization
memo = {}
def fib_memo_manual(n):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo_manual(n-1) + fib_memo_manual(n-2)
return memo[n]
# With @lru_cache (best way)
from functools import lru_cache
@lru_cache(maxsize=1000)
def fib_cached(n):
if n <= 1: return n
return fib_cached(n-1) + fib_cached(n-2)
# Performance comparison
import time
n = 35
start = time.time()
result = fib_slow(n)
slow_time = time.time() - start
start = time.time()
result = fib_cached(n)
fast_time = time.time() - start
print(f"fib({n}) = {result}")
print(f"\n⏱️ Without cache : {slow_time:.4f}s")
print(f"⚡ With lru_cache : {fast_time:.6f}s")
print(f"🚀 Speedup : {slow_time/max(fast_time, 0.000001):.0f}x faster!")
| ⏱️ Without cache | 3.2451s |
| ⚡ With lru_cache | 0.000012s |
| 🚀 Speedup | 270425x faster! |
⚠️ Recursion Limit aur Stack Overflow
Example
# ─────────────────────────────────────
# Python mein recursion limit
# ─────────────────────────────────────
import sys
# Default limit check karo
print(f"Default recursion limit: {sys.getrecursionlimit()}") # 1000
# Limit badhana (caution ke saath)
sys.setrecursionlimit(2000)
print(f"New recursion limit: {sys.getrecursionlimit()}")
# ─── Recursion vs Iteration comparison ───
def sum_recursive(n):
"""Recursive — stack overflow possible for large n"""
if n <= 0: return 0
return n + sum_recursive(n - 1)
def sum_iterative(n):
"""Iterative — no stack overflow"""
total = 0
for i in range(1, n + 1):
total += i
return total
# Small numbers pe same result
print(f"\nsum_recursive(100) = {sum_recursive(100)}")
print(f"sum_iterative(100) = {sum_iterative(100)}")
# Large numbers ke liye iterative use karo
print(f"sum_iterative(10000) = {sum_iterative(10000)}")
# sum_recursive(10000) → RecursionError!
Example
# OUTPUT:
Default recursion limit: 1000
New recursion limit: 2000
sum_recursive(100) = 5050
sum_iterative(100) = 5050
sum_iterative(10000) = 50005000
📊 Recursion vs Iteration
| RECURSION | ITERATION |
|---|---|
| Code clean hota | More verbose code |
| hai | |
| Stack memory | Constant memory (O(1)) |
| use karta hai | |
| Stack overflow | Koi limit nahi (theoretically) |
| possible | |
| Trees, graphs, | Simple loops, counters |
| divide & conquer | |
| Debugging hard | Debug karna aasan |
| ho sakta hai |
❓ Interview Questions
Q1: Recursion mein base case kyu zaroori hai?
python example
# Without base case → infinite recursion → RecursionError
def bad_recursion(n):
return n + bad_recursion(n - 1) # Never stops!
# With base case ✅
def good_recursion(n):
if n == 0: return 0 # BASE CASE
return n + good_recursion(n - 1)Q2: Recursion ka time complexity kaise calculate karo?
- Fibonacci (without memo): O(2^n) — exponential - Factorial: O(n) — linear - Binary search: O(log n) — logarithmic - Merge sort: O(n log n)
Q3: Tail recursion kya hai? Python support karta hai?
Tail recursion — last operation recursive call ho. Python *tail call optimization* support nahi karta. Isliye deep recursion ke liye iteration prefer karo.
Q4: Mutual recursion kya hoti hai?
python example
def is_even(n):
if n == 0: return True
return is_odd(n - 1) # even calls odd
def is_odd(n):
if n == 0: return False
return is_even(n - 1) # odd calls even
print(is_even(10)) # True
print(is_odd(7)) # True📋 Summary
┌─────────────────────────────────────────────────────┐
│ RECURSION — KEY CONCEPTS │
├─────────────────────────────────────────────────────┤
│ ✅ Function jo khud ko call kare = recursion │
│ ✅ Base case ZAROOR hona chahiye │
│ ✅ Har call mein problem chhoti honi chahiye │
│ ✅ Default limit = 1000 (sys.setrecursionlimit) │
│ ✅ Memoization se performance improve karo │
│ ✅ Trees/graphs ke liye recursion best hai │
│ ✅ Large n ke liye iteration prefer karo │
│ ✅ @lru_cache se memoize karo easily │
└─────────────────────────────────────────────────────┘
🚀 Next: Scope of Variables aur LEGB rule ke liye scope-of-variables.mdx padhein!⚠️ Common Mistakes
❌ Mistake 1: Base Case Bhoolna
python example
# ❌ WRONG — infinite recursion, stack overflow!
def factorial_bad(n):
return n * factorial_bad(n - 1) # Kab rukegi? 🤔
# ✅ CORRECT — base case add karo
def factorial_good(n):
if n <= 1: # 👈 Base case ZAROOR lagao
return 1
return n * factorial_good(n - 1)
print(factorial_good(5))Example
# OUTPUT:
120
❌ Mistake 2: Base Case Galat Condition
python example
# ❌ WRONG — negative numbers ke liye infinite loop
def countdown_bad(n):
if n == 0: # Agar n = -1 pass kiya toh?
return
print(n)
countdown_bad(n - 1)
# ✅ CORRECT — <= use karo, edge cases handle karo
def countdown_good(n):
if n <= 0: # 👈 <= se negative values bhi cover hoti hain
print("🚀 Done!")
return
print(n)
countdown_good(n - 1)
countdown_good(3)Example
# OUTPUT:
3
2
1
🚀 Done!
❌ Mistake 3: Problem Size Reduce Na Karna
python example
# ❌ WRONG — n change hi nahi ho raha!
def infinite_loop(n):
if n == 0:
return 0
return n + infinite_loop(n) # 👈 n wahi ka wahi hai!
# ✅ CORRECT — har step mein problem chhoti karo
def correct_sum(n):
if n == 0:
return 0
return n + correct_sum(n - 1) # 👈 n-1 se problem shrink ho rahi hai
print(correct_sum(5))Example
# OUTPUT:
15
❌ Mistake 4: Return Statement Bhoolna
python example
# ❌ WRONG — recursive call ka result return nahi kiya
def factorial_no_return(n):
if n <= 1:
return 1
factorial_no_return(n - 1) * n # 👈 return missing! None milega
# ✅ CORRECT — return lagao!
def factorial_with_return(n):
if n <= 1:
return 1
return factorial_with_return(n - 1) * n # 👈 return added
print(factorial_no_return(5)) # None 😱
print(factorial_with_return(5)) # 120 ✅Example
# OUTPUT:
None
120
❌ Mistake 5: Mutable Default Arguments Use Karna
Example
# ❌ WRONG — list share ho jayegi across calls!
def collect_bad(n, result=[]):
if n == 0:
return result
result.append(n)
return collect_bad(n - 1, result)
print(collect_bad(3)) # [3, 2, 1] ✅ pehli baar sahi
print(collect_bad(3)) # [3, 2, 1, 3, 2, 1] ❌ duplication!
# ✅ CORRECT — None default use karo
def collect_good(n, result=None):
if result is None:
result = [] # 👈 Har baar fresh list
if n == 0:
return result
result.append(n)
return collect_good(n - 1, result)
print(collect_good(3)) # [3, 2, 1] ✅
print(collect_good(3)) # [3, 2, 1] ✅
Example
# OUTPUT:
[3, 2, 1]
[3, 2, 1, 3, 2, 1]
[3, 2, 1]
[3, 2, 1]
❌ Mistake 6: Deep Recursion Bina Optimization
python example
# ❌ WRONG — fib(40) mein millions of redundant calls
def fib_slow(n):
if n <= 1: return n
return fib_slow(n-1) + fib_slow(n-2) # 👈 Same subproblems repeatedly!
# ✅ CORRECT — memoization lagao
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_fast(n):
if n <= 1: return n
return fib_fast(n-1) + fib_fast(n-2) # 👈 Results cached!
print(fib_fast(50))Example
# OUTPUT:
12586269025
❌ Mistake 7: Global Variables Misuse in Recursion
python example
# ❌ WRONG — global variable unpredictable behavior
count = 0
def count_bad(n):
global count
if n == 0: return
count += 1
count_bad(n - 1)
count_bad(5)
print(count) # 5
count_bad(3) # Previous value affect karega!
print(count) # 8 (not 3!) ❌
# ✅ CORRECT — parameter pass karo, pure function banao
def count_good(n):
if n == 0: return 0
return 1 + count_good(n - 1)
print(count_good(5)) # 5 ✅
print(count_good(3)) # 3 ✅ — independent resultsExample
# OUTPUT:
5
8
5
3
✅ Key Takeaways
- 🔁 Recursion = function jo khud ko call kare — same problem ka chhota version solve karta hai har step pe
- 🛑 Base case hamesha define karo — bina base case ke RecursionError (stack overflow) aayega guaranteed
- 📉 Har recursive call mein problem shrink honi chahiye — agar size same rahi toh infinite loop ban jayega
- 🧠 Memoization (@lru_cache) se performance dramatically improve hoti hai — O(2^n) se O(n) ban jaata hai Fibonacci mein
- 📏 Python ki default recursion limit 1000 hai —
sys.setrecursionlimit()se badha sakte ho par carefully - 🌲 Trees, graphs, nested structures ke liye recursion naturally fit hai — iteration se zyada clean code milta hai
- 🔄 Simple loops ke liye iteration prefer karo — factorial/sum jaise problems mein iteration faster + safer hai
- 📦 Call stack visualize karo debugging ke liye — depth parameter add karke indentation print karo
- 🎯 Divide & Conquer pattern recursion pe based hai — Binary Search, Merge Sort, Quick Sort sab recursive hain
- ⚡ Tail recursion Python mein optimize nahi hoti — large inputs ke liye iterative conversion karo
❓ FAQ
Q1: Recursion aur Loop mein kya difference hai? Kab kya use karein?
Loop (Iteration) mein aap explicitly repeat karte ho usingfor/while. Recursion mein function apne aap ko call karta hai. Rule of thumb: Simple counting/summing → Loop use karo. Tree traversal, nested structures, divide & conquer → Recursion use karo. Recursion code cleaner hota hai par memory zyada khata hai.
Q2: Python mein maximum kitni depth tak recursion kar sakte hain?
Default limit 1000 calls hai. sys.setrecursionlimit(5000) se badha sakte ho, par bahut zyada badhana dangerous hai — OS crash bhi ho sakta hai! Deep recursion ke liye iterative approach ya tail-call conversion use karo.Q3: Memoization aur Dynamic Programming mein kya relation hai?
Memoization ek top-down approach hai — recursion karo aur results cache karo. Dynamic Programming (DP) bottom-up approach hai — chhote subproblems pehle solve karo, phir bade. Dono ka goal same hai: overlapping subproblems ko baar baar solve na karna.
Q4: RecursionError aaye toh kaise fix karein?
3 solutions hain: 1. Base case check karo — kahi missing toh nahi ya galat condition toh nahi 2. sys.setrecursionlimit() badhao — temporary fix 3. Iterative version likho — best permanent fix for deep recursions
Q5: Kya har recursive function ko iterative mein convert kar sakte hain?
Haan, theoretically har recursion ko iteration mein convert kar sakte hain — explicit stack (list) use karke. Par kuch problems (tree traversal, backtracking) mein recursive version zyada readable hota hai. Tradeoff samajhna zaroori hai!
Q6: Tail recursion kya hoti hai aur Python mein kyu kaam nahi karti?
Tail recursion = jab function ka last statement recursive call ho (koi aur operation baaki na ho). Some languages (Scheme, Haskell) isko optimize kar ke loop bana deti hain. Python deliberately TCO support nahi karti — Guido van Rossum ne readability aur debugging ke liye ye decision liya.
Q7: Recursion mein space complexity kaise calculate karein?
Space complexity = maximum depth of recursion × per-frame memory. Factorial mein O(n) space lagta hai (n frames stack pe). Binary Search mein O(log n). Fibonacci without memoization mein bhi O(n) — kyunki maximum depth n hai (left-most branch).
Q8: Indirect/Mutual recursion kya hoti hai? Real-world mein kahan use hoti hai?
Mutual recursion mein do ya zyada functions ek dusre ko call karte hain (A calls B, B calls A). Real-world use: parsers (expression parsing mein), state machines (even/odd checking), aur compiler design mein common hai. Production code mein carefully use karo — debugging mushkil ho sakti hai.
🎯 Interview Questions
Q1: Recursion mein base case kyu zaroori hai? Bina base case ke kya hoga?
Base case recursion ko terminate karta hai. Bina base case ke function infinitely khud ko call karega, call stack full ho jayega, aur Python RecursionError: maximum recursion depth exceeded throw karega. Ye essentially stack overflow hai. Base case wo condition hai jo recursion ke bina directly answer return karti hai.Q2: Fibonacci function ka time complexity O(2^n) kyu hoti hai? Isko optimize kaise karein?
Simple recursive Fibonacci mein har call do aur calls generate karti hai, forming a binary tree. Same subproblems baar baar solve hote hain —fib(3)multiple times calculate hota hai. Optimization: (1)@lru_cachese memoization — O(n) time, O(n) space. (2) Bottom-up DP — O(n) time, O(1) space. (3) Matrix exponentiation — O(log n) time.
Q3: Tail recursion kya hai? Python support karta hai?
Tail recursion = last operation recursive call ho, uske baad koi computation na ho. Example: return factorial_tail(n-1, n*acc). Python TCO (Tail Call Optimization) support nahi karta by design — Guido van Rossum ne stack traces preserve karne aur debugging easy rakhne ke liye ye consciously reject kiya. Deep recursion ke liye manually iterative conversion karo.Q4: Recursion vs Iteration — interview mein kaise explain karoge ki kab kya use karna chahiye?
Recursion prefer karo: Tree/graph traversal, backtracking (N-Queens, Sudoku), divide & conquer (Merge Sort, Quick Sort), nested structures (JSON parsing, directory walk). Iteration prefer karo: Simple sequences, large input sizes, performance-critical code, jab stack depth concern ho. Key insight: Recursion readability deta hai, iteration performance.
Q5: Call stack kaise kaam karta hai recursion mein? Diagram draw karke explain karo.
Har recursive call ek new stack frame push karta hai memory mein (local variables + return address ke saath). Base case hit hone pe frames LIFO order mein pop hote hain. Example: factorial(4) → stack: [fact(4), fact(3), fact(2), fact(1)]. fact(1) return karta hai 1, phir fact(2) return karta hai 2×1=2... ye unwinding phase hai jab actual computation hota hai.Q6: Write a recursive function to check if a string is palindrome.
Example
def is_palindrome(s):
"""Recursively check if string is palindrome"""
# Base case: empty string ya single char
if len(s) <= 1:
return True
# First aur last char match karo
if s[0] != s[-1]:
return False
# Beech ka portion recursively check karo
return is_palindrome(s[1:-1])
print(is_palindrome("racecar")) # True
print(is_palindrome("hello")) # False
print(is_palindrome("madam")) # True
print(is_palindrome("a")) # True
Example
# OUTPUT:
True
False
True
True
Q7: Stack overflow kaise avoid karoge production code mein?
(1) sys.setrecursionlimit() carefully badhao — par ye band-aid fix hai. (2) Iterative conversion karo with explicit stack. (3) Memoization use karo repeated subproblems ke liye. (4) Trampoline pattern use karo — function return kare next function call instead of directly calling. (5) Input size validate karo — recursion depth exceed hone se pehle error throw karo.
Q8: Merge Sort recursion kaise use karta hai? Time complexity explain karo.
Merge Sort divide & conquer approach follow karta hai: (1) Array ko half mein divide karo recursively (2) Jab single elements reh jayein (base case) (3) Merge karo sorted halves ko. Har level pe n elements merge hote hain → O(n) per level. Total levels = log₂(n). Total: O(n log n) — best, average, aur worst case same hai. Space: O(n) auxiliary array ke liye.
Q9: Power function pow(base, exp) recursively kaise likhoge with O(log n) complexity?
python example
def power(base, exp):
"""O(log n) power calculation using recursion"""
# Base cases
if exp == 0: return 1
if exp < 0: return 1 / power(base, -exp)
# Agar exp even hai: base^n = (base^(n/2))^2
if exp % 2 == 0:
half = power(base, exp // 2)
return half * half
# Agar odd hai: base^n = base * base^(n-1)
else:
return base * power(base, exp - 1)
print(power(2, 10)) # 1024
print(power(3, 5)) # 243
print(power(5, 0)) # 1
print(power(2, -3)) # 0.125Example
# OUTPUT:
1024
243
1
0.125
Q10: Recursive function mein memory leak kaise hota hai aur kaise avoid karein?
Memory leak tab hota hai jab: (1) Mutable objects accumulate hote hain across recursive calls (especially mutable default args). (2) Large closures har frame mein capture hote hain. (3) Circular references ban jaate hain. Avoid karne ke liye: immutable data prefer karo,Nonedefault use karo mutable args ke liye,@lru_cachekomaxsizeke saath use karo (unlimited cache bhi memory kha sakta hai), aurcache_clear()call karo jab cache ki zaroorat na ho.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Recursive Functions in Python.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Python Master Course topic.
Search Terms
python-master-course, python master course, python, master, course, functions, recursive, recursive functions in python
Related Python Master Course Topics
Continue learning this concept
FunctionsDecorators in PythonDetailed guide to Python decorators — function decorators, class decorators, stacking, functools.wraps, and real-world use cases. Learn with examples and best practices.FunctionsFunction Arguments in PythonComplete guide to Python function arguments — positional, keyword, default, *args, **kwargs and their real-world use cases. Understand argument types with best practices.FunctionsFunctions Basics in PythonPython mein functions ki complete guide — definition, calling, types, aur best practices. Samjho functions ka syntax, purpose, aur real-world usage Hindi explanations ke saath.FunctionsGenerators in PythonPython generators ki detailed guide — yield keyword, generator functions, generator expressions, send/throw/close, aur real-world use cases jaise infinite sequences, data pipelines, aur memory-efficient file processing. Hindi mein.FunctionsLambda Functions in PythonComplete guide to Python lambda functions — syntax, use cases, usage with map/filter/sorted, and comparison with regular functions. Learn with practical examples.FunctionsReturn Statement in PythonPython mein return statement ki poori guide — single/multiple return values, early return, None return, aur real-world patterns. Hindi mein samjho return ke saare use cases.