Recursion — call stack visualization, base case, recursive case: Exercises

1.2.37 · D4 · Coding › Introduction to Programming (Python) › Recursion — call stack visualization, base case, recursive c

B crash karta hai. a n == 0 ko pakad leta hai aur recursion kiye bina return karta hai, isliye ruk jaata hai. b mein koi if nahi hai jo khud ko call kiye bina return kare — har call ek aur call karta hai hamesha ke liye → RecursionError: maximum recursion depth exceeded.

Level 2 — Application

Goal: machine ko haath se chalao — winding aur unwinding trace karo.

Exercise 2.1

fact(4) ko trace karo is code se:

def fact(n):
    if n == 0: return 1
    return n * fact(n-1)

Final number aur charon calls ke return hone ka order do.

Recall Solution 2.1

Winding (push): fact(4) → fact(3) → fact(2) → fact(1) → fact(0). Base: fact(0) pehle return karta hai $1$ (sabse gehri frame, LIFO). Unwinding (pop, upar jaate waqt multiply):

fact(1): $1 \cdot 1 = 1$
fact(2): $2 \cdot 1 = 2$
fact(3): $3 \cdot 2 = 6$
fact(4): $4 \cdot 6 = 24$

Return order: fact(0), phir fact(1), fact(2), fact(3), fact(4). Answer $= 24$ .

Exercise 2.2

power(2, 3) ko trace karo ( $2^{3}$ compute karo):

def power(base, exp):
    if exp == 0: return 1
    return base * power(base, exp - 1)

Result do aur batao ki sabse gehre point par stack par kitne frames hain.

Recall Solution 2.2

Descent exp ko shrink karta hai: $3 \to 2 \to 1 \to 0$ .

power(2,0) = $1$ (base)
power(2,1) = $2 \cdot 1 = 2$
power(2,2) = $2 \cdot 2 = 4$
power(2,3) = $2 \cdot 4 = 8$

Deepest stack: exp = 3, 2, 1, 0 ke frames sab ek saath alive hain → 4 frames. Generally $2^{exp}$ ke liye exp + 1 frames chahiye hote hain.

Exercise 2.3

summ([5, 3, 8, 1]) ko trace karo parent note ke list-sum function se. Result do.

Recall Solution 2.3

Har call head L[0] ko peel karta hai aur tail L[1:] par recurse karta hai: $5 + (3 + (8 + (1 + base: [] 0)))$ Wapas build karte hue: $1 + 0 = 1$ , $8 + 1 = 9$ , $3 + 9 = 12$ , $5 + 12 = 17$ . Answer $= 17$ .

Level 3 — Analysis

Goal: depth, break-points, aur kyun order matter karta hai — is par reason karo.

Exercise 3.1

Python ka default recursion limit lagbhag 1000 frames hai. Is function ko deep(0) ke roop mein call kiya jaata hai:

def deep(n):
    if n == 1000: return n
    return deep(n + 1)

Rukne se pehle lagbhag kitne frames stack ho jaate hain, aur kya ye ruk-ta hai ya crash karta hai?

Recall Solution 3.1

n $0, 1, 2, \dots, 1000$ chadhta hai. Ye n == 1000 par ruk-ta hai — ye base case hai. Sabse gehre point par alive frames: $n = 0 \dots 1000$ mein se har ek ke liye ek, yaani 1001 frames. Kyunki $1001 > 1000$ , ye default limit se zyada ho jaata hai aur base case tak pahunchne se pehle RecursionError raise karta hai. (Dekho Big-O and Recursion Depth — depth, sirf correctness nahi, matter karti hai.)

Exercise 3.2

Ye dono functions sirf is baat mein alag hain ki print kahan hai. Batao ki input 3 ke liye har ek kya print karta hai.

def down(n):              # A
    if n < 0: return
    print(n)
    down(n - 1)
 
def up(n):                # B
    if n < 0: return
    up(n - 1)
    print(n)

Recall Solution 3.2

A (down) winding ke dauran print karta hai (call se pehle): 3, 2, 1, 0.
B (up) unwinding ke dauran print karta hai (call return hone ke baad): 0, 1, 2, 3.

Kyun: B mein, har frame pehle apna child call poora karta hai, aur tabhi print(n) chalata hai. Sabse gehri frame (n = 0) pehle unwind hoti hai, isliye 0 pehle print hota hai, phir 1, aur aisa upar wapas jaate hue. Same recursion, mirror-image output.

Exercise 3.3

Kya ye crash karta hai ya return karta hai? Agar return karta hai, toh f(10) kya deta hai?

def f(n):
    if n == 0: return 0
    return f(n - 2)

Recall Solution 3.3

10 se shuru karke aur 2 subtract karke: $10, 8, 6, 4, 2, 0$ → base case n == 0 hit hoti hai, $0$ return karta hai, aur har frame wo $0$ bina badlaav ke wapas pass karta hai → returns 0. Danger: agar odd number se call kiya jaaye jaise f(9), toh ye $9, 7, 5, 3, 1, - 1, - 3, \dots$ step karta aur 0 ko hamesha ke liye jump past kar deta → crash. Base case step size se reachable honi chahiye, sirf "chhota" nahi.

Level 4 — Synthesis

Goal: self-similarity insight se apni recursions design karo.

Exercise 4.1

Ek recursive length(L) likho jo bataye ki list mein kitne items hain, len() use kiye bina. Phir length([9, 9, 9]) do.

Recall Solution 4.1

Self-similarity: list ki length = $1$ (head ke liye) plus tail ki length. Base case: empty list ki length $0$ hoti hai.

def length(L):
    if not L:               # base case
        return 0
    return 1 + length(L[1:])  # recursive case

length([9,9,9]) → $1 + (1 + (1 + 0)) = 3$ .

Exercise 4.2

Ek recursive reverse(s) likho jo string ko reverse kare. reverse("cat") trace karo.

Recall Solution 4.2

Self-similarity: string ko reverse karna = uski tail ka reverse, aur head ko end par lagao. Base case: empty string reversed "" hoti hai.

def reverse(s):
    if s == "":                 # base case
        return ""
    return reverse(s[1:]) + s[0]  # tail reversed, phir head peeche

Trace reverse("cat"):

reverse("at") + "c"
(reverse("t") + "a") + "c"
((reverse("") + "t") + "a") + "c"
((("" + "t") + "a") + "c") = "t" + "a" + "c" = "tac" ✅

Exercise 4.3

Euclid ke rule $g cd (a, b) = g cd (b, a mod b)$ se ek recursive gcd(a, b) (greatest common divisor) likho, base case $g cd (a, 0) = a$ ke saath. gcd(48, 18) compute karo.

Recall Solution 4.3

Ye recursion kyun: Euclid ne notice kiya ki do numbers ka gcd chhote number aur remainder ke gcd ke barabar hota hai — har step mein ek strictly chhota pair, jo guarantee karta hai ki hum b == 0 tak pahunchenge.

def gcd(a, b):
    if b == 0:            # base case
        return a
    return gcd(b, a % b)  # recursive case, remainder shrinks

Trace gcd(48, 18):

gcd(48, 18) → gcd(18, 48 % 18 = 12)
gcd(18, 12) → gcd(12, 18 % 12 = 6)
gcd(12, 6) → gcd(6, 12 % 6 = 0)
gcd(6, 0) → base case → returns 6.

Level 5 — Mastery

Goal: recursion ko tree-shaped ya overlapping structure ke saath combine karo.

Exercise 5.1

fib Fibonacci compute karta hai $fib (0) = 0, fib (1) = 1, fib (n) = fib (n - 1) + fib (n - 2)$ se. Ye do recursive calls per frame hai — ek line nahi, ek tree. fib(4) ke call tree ko draw/reason karo aur iski value aur fib(1) kitni baar evaluate hoti hai, do.

Recall Solution 5.1

Tree har step par do baar branch karta hai (figure dekho). Values: $fib (4) = 3$ .

Figure — Recursion — call stack visualization, base case, recursive case

fib(1) wale leaves count karo: poori tarah expand karne par, fib(1) 3 baar reach hoti hai aur fib(0) 2 baar. Wo repeated work exactly "overlapping subproblems" problem hai — dekho Fibonacci and overlapping subproblems aur uska ilaaj, Memoization and Dynamic Programming. $fib (4) = fib (3) + fib (2) = (2) + (1) = 3$

Exercise 5.2

Ek recursive count_nodes(tree) likho jo ek nested list jaise [1, [2, 3], [4, [5, 6]]] mein har number count kare (har element ya toh ek number hai ya doosri list). Us example ke liye count do.

Recall Solution 5.2

Self-similarity: nested list ka count = uske elements ke counts ka sum; ek number $1$ count hota hai; ek list ko same function count karta hai (loop ke andar recursion). Ye Tree and Graph Traversal ki shape hai.

def count_nodes(x):
    if not isinstance(x, list):   # base case: ek plain number
        return 1
    total = 0
    for elem in x:                # recursive case: children ka sum
        total += count_nodes(elem)
    return total

[1, [2, 3], [4, [5, 6]]] ke liye numbers hain $1, 2, 3, 4, 5, 6$ → 6.

Exercise 5.3

fib(20) ke liye, plain recursion aur ek memoized version ke banaye gaye function calls ki sankhya compare karo jo har answer ek baar store karta hai. (Tumhe exact plain count ki zarurat nahi — shape ke baare mein reason karo.)

Recall Solution 5.3

Memoized: $k = 0 \dots 20$ ke liye har distinct fib(k) ek baar compute hota hai → lagbhag 21 stored results (har aage ka lookup instant hota hai). Ye Memoization and Dynamic Programming hai jo tree ko line mein badal deta hai.
Plain recursion: call tree kabhi kabhi har level par double hoti hai; fib(20) compute karne ke liye total calls ki exact sankhya $2 \cdot fib (21) - 1 = 2 \cdot 10946 - 1 = 21891$ calls hai.

Toh memoization ~21891 calls ko ~21 computations mein badal deta hai — payoff n ke saath explosively badhta hai. Plain Iteration — for and while loops se compare karo, jo bhi ~20 steps mein karta hai lekin bina stack ke.

Recall Final self-check

Answers cover karo aur har ek ko zor se bolo. fact(4) ke calls ka return order? ::: fact(0), fact(1), fact(2), fact(3), fact(4). power(2,3) ke deepest point par alive frames? ::: 4 (exp = 3,2,1,0). reverse("cat") = ? ::: "tac". gcd(48,18) = ? ::: 6. fib(4) = ? aur fib(1) ke kitne evaluations? ::: 3, aur fib(1) 3 baar evaluate hoti hai. f(n)=f(n-2) odd n par crash kyun karta hai lekin even par nahi? ::: Odd starts n==0 point ko skip kar jaate hain; reachable range ke liye n<=0 use karo.

Exercises — Recursion — call stack visualization, base case, recursive case

Level 1 — Recognition

Exercise 1.1

Exercise 1.2