Lesson 1 � Beginner

Recursion: Khud ko Call Karna

Recursion DSA ka sabse fundamental concept hai. Jab ek function apne aap ko call kare � use recursion kehte hain. Backtracking, trees, graphs, DP � sab recursion pe based hain. Is lesson mein hum recursion ka complete foundation banayenge.

? 22 min✓ Beginner✓ Programming basics

Recursion kya hai?

WHAT

Recursion mein ek function apne aap ko call karta hai � ek chhota version of same problem solve karta hai. Har recursive call ek chhoti problem solve karta hai jab tak base case na aa jaye. Base case woh condition hai jahan recursion rukta hai.

WHEN

Jab problem naturally recursive ho � jaise factorial, Fibonacci, tree traversals, divide and conquer, backtracking. Jab problem ko chhote sub-problems mein tod sako jo same pattern follow karein.

WHERE

Factorial, Fibonacci, Tower of Hanoi, Tree Traversals, Backtracking problems (N-Queens, Sudoku), Graph DFS, Dynamic Programming � sab recursion se start hote hain.

Mental Model: Imagine karo tum ek bade gift box khol rahe ho. Har box mein ek chhota gift box milta hai. Tum chhote box kholte jaate ho jab tak ek chhota sa note na mil jaye � "Gift yahan hai!" � ye hai base case. Phir tum ek ek karke sab boxes band karte jaate ho � ye hai unwinding.

Recursion ka Structure

Har recursion mein 2 cheezein hoti hain � base case aur recursive case. Base case recursion ko rokta hai, recursive case problem ko chhota karta hai:

# Factorial using recursion
# factorial(n) = n * factorial(n-1)
# Base case: factorial(0) = 1

def factorial(n):
 if n <= 1: # Base case � yahan ruko!
 return 1
 return n * factorial(n - 1) # Recursive call � khud ko call karo

print(factorial(5)) # 120

Key Rule: Har recursive call mein problem chhoti honi chahiye. Agar problem chhoti nahi ho rahi toh infinite recursion ho jayega aur stack overflow ho jayega. Base case HONA chahiye � warna recursion kabhi rukega nahi.

Call Stack Visualization

Recursion kaise kaam karta hai call stack pe � ye samajhna bahut zaroori hai. Har call stack mein push hoti hai, jab base case milta hai toh unwinding hoti hai:

# factorial(3) ka execution:

# Step 1: factorial(3) call hua
# ? 3 * factorial(2) � ab factorial(2) call hua
# ? 2 * factorial(1) � ab factorial(1) call hua
# ✓ n <= 1 hai, return 1 ✓ Base case mila!

# Unwinding starts:
# factorial(1) = 1
# factorial(2) = 2 * 1 = 2
# factorial(3) = 3 * 2 = 6

# Visual:
# Call Stack: Unwinding:
# +----------+ +----------+
# � fact(3) � --? � fact(3)=6�
# +----------� +----------�
# � fact(2) � --? � fact(2)=2�
# +----------� +----------�
# � fact(1) � --? � fact(1)=1� ✓ Base case
# +----------+ +----------+

Stack Overflow: Agar base case nahi hai ya problem chhoti nahi ho rahi toh calls badhti jaati hain aur stack memory khatam ho jaati hai. Python mein default recursion limit 1000 hai � sys.setrecursionlimit() se badha sakte ho.

Recursion vs Iteration

Dono approaches hain problem solve karne ki. Kab recursion use karo aur kab iteration � ye samajhna important hai:

# Iterative Factorial
def factorial_iterative(n):
 result = 1
 for i in range(2, n + 1):
 result *= i
 return result

# Recursive Factorial
def factorial_recursive(n):
 if n <= 1:
 return 1
 return n * factorial_recursive(n - 1)

# Dono same result dete hain
print(factorial_iterative(5)) # 120
print(factorial_recursive(5)) # 120

Recursion kab use karo

Tree/Graph traversals, Divide & Conquer, Backtracking, jab problem naturally recursive ho, jab code concise aur readable chahiye.

Iteration kab use karo

Simple loops, jab space efficiency chahiye (recursion extra stack use karta hai), jab recursion depth zyada ho sakti hai.

Hybrid Approach

Kai baar recursion + iteration dono use hote hain. Jaise tree BFS mein recursion + queue, ya tail recursion optimization.

Recursion ke Classic Examples

# Fibonacci Series
# fib(0) = 0, fib(1) = 1
# fib(n) = fib(n-1) + fib(n-2)

def fibonacci(n):
 if n <= 0:
 return 0
 if n == 1:
 return 1
 return fibonacci(n - 1) + fibonacci(n - 2)

# fib(5) = fib(4) + fib(3)
# = (fib(3)+fib(2)) + (fib(2)+fib(1))
# = ((fib(2)+fib(1)) + fib(2)) + (fib(2)+1)
# = ... = 5

for i in range(8):
 print(fibonacci(i), end=" ") # 0 1 1 2 3 5 8 13

# Power Calculation: x^n
def power(x, n):
 if n == 0:
 return 1
 if n % 2 == 0:
 half = power(x, n // 2)
 return half * half
 return x * power(x, n - 1)

print(power(2, 10)) # 1024

# Sum of Digits
def digit_sum(n):
 if n < 10:
 return n
 return n % 10 + digit_sum(n // 10)

print(digit_sum(1234)) # 1+2+3+4 = 10

Tail Recursion

Tail recursion mein recursive call function ka last operation hota hai. Kuch languages isko optimize kar sakti hain (iteration mein convert). Python mein ye optimization nahi hoti but concept samajhna important hai:

# Normal recursion � return ke baad multiplication hota hai
def factorial(n):
 if n <= 1:
 return 1
 return n * factorial(n - 1) # multiplication pending hai

# Tail recursion � recursive call LAST hai
def factorial_tail(n, accumulator=1):
 if n <= 1:
 return accumulator
 return factorial_tail(n - 1, n * accumulator) # koi pending kaam nahi

print(factorial_tail(5)) # 120

Try it: code khud likho

Exercise

Question: Recursion use karke fibonacci(7) ka answer nikalo. Sirf answer number daalo.

Question: Recursive function likho jo power(2, 5) calculate kare. Answer mein result daalo.

Common mistakes

Base case bhool jaana: Agar base case nahi likha toh infinite recursion ho jayega aur stack overflow ho jayega. Hamesha pehle base case likho.
Problem chhoti nahi ho rahi: Har recursive call mein argument change hona chahiye. Agar factorial(n) mein n decrease nahi ho raha toh infinite loop hai.
Recursion depth ka dhyan nahi rakhna: Python mein default limit 1000 hai. Bahut deep recursion mein sys.setrecursionlimit() use karo ya iterative approach socho.
Overlapping subproblems: Fibonacci mein same values baar baar calculate hoti hain � isliye memoization use karo (DP lesson mein seekhenge).
Recursion vs Iteration confusion: Har jagah recursion zaroori nahi hai. Simple loops ho sakein toh iteration use karo � recursion overhead kam karo.

Lesson complete?

Recursion samajh aa gaya✓ Ab recursion patterns seekhte hain � subsets, permutations, combinations � ye sab recursion se bante hain.