🪆 धडा 06 — Recursion: मुख्याध्यापक उपमुख्याध्यापकांना विचारतात

📍 तुम्ही इथे आहात: 12 पैकी धडा 06 · पुढे: lesson-07-sorting

📦 या ब्रँचमध्ये काय आहे

धडे 01–06. एखादा प्रश्न त्याचीच छोटी आवृत्ती विचारून सोडवणे, उत्तर न मिळालेले प्रश्न धरून ठेवणारा stack, आणि यात नेहमी होणारी क्लासिक चूक.

dsa/algorithms.py — factorial (depth नोंदवतो), fib_slow (calls मोजतो), fib_memo (धडा 11 चा फळा)
dsa/demo.py — recursion

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

5 विद्यार्थी किती प्रकारे रांगेत उभे राहू शकतात (5!) हे मुख्याध्यापिकेला जाणून घ्यायचे आहे. ती उपमुख्याध्यापिकेला विचारते: "मला 4! सांगा, मी त्याला 5 ने गुणेन." उपमुख्याध्यापिका एका शिक्षिकेला 3! विचारते, ती 2! विचारते, ती 1! विचारते — आणि सर्वात लहान शिक्षिकेला उत्तर माहीतच असते:

उत्तरे परत वर जातात. उत्तर न मिळालेला प्रत्येक प्रश्न वाट पाहत असताना एका ढिगावर बसलेला होता — तो ढीग म्हणजे call stack. ढीग हजार उंच झाला तर Python थांबा म्हणतो. आणि मुख्याध्यापिकेने तोच प्रश्न दोन वेगवेगळ्या उपमुख्याध्यापिकांमार्फत विचारला तर त्याचे उत्तर दोनदा काढले जाते — अशा प्रकारेच fib(25) चे 242,785 प्रश्न होतात.

🗺️ आकृती

flowchart TD
  F5["5! = 5 × 4!"] --> F4["4! = 4 × 3!"] --> F3["3! = 3 × 2!"] --> F2["2! = 2 × 1!"] --> F1["1! = 1 (base case)"]
  F1 -.->|"answers return"| F5

❓ काय

recursive function मध्ये एक base case (थेट उत्तर) आणि एक recursive case (त्याच प्रश्नाची छोटी आवृत्ती) असते.
call stack उत्तराची वाट पाहणारी प्रत्येक frame धरून ठेवतो: depth = memory. Python ची मर्यादा ~1,000 frames आहे; खोल कामासाठी loop किंवा स्वतःचा stack लागतो.
खर्च = calls ची संख्या × प्रत्येक call चे काम. factorial(n): n calls, O(n). fib_slow(n): ~1.6ⁿ calls, O(2ⁿ) — तेच उप-प्रश्न पुन्हा पुन्हा विचारले जातात. Memoisation (उत्तर मिळालेल्या प्रश्नांचा dict) हे O(n) करते.
trees (धडा 09), DFS (धडा 10), merge/quick sort (धडा 07), backtracking आणि DP (धडा 11) यांचा नैसर्गिक आकार recursion च आहे.

🤔 का

पुढचे निम्मे structures स्वभावानेच recursive आहेत; ते आधी iterative पद्धतीने लिहिणे त्रासदायक आहे. पण recursion मध्ये दोन सापळे आहेत — depth आणि पुन्हा पुन्हा होणारे काम — आणि हा धडा tree मध्ये भेटण्याआधीच दोन्ही तुम्हाला दाखवतो.

🔧 कसे (या repo मध्ये)

factorial एका element ची list घेतो आणि तो जिथपर्यंत पोहोचला ते सर्वात खोल n नोंदवतो; fib_slow प्रत्येक call ला counter वाढवतो; fib_memo आधी dict तपासतो. demo.py recursion depth आणि दोन्ही call counts print करतो.

🧪 करून पाहा

python3 dsa/demo.py recursion
python3 - <<'EOF'
import sys; sys.path.insert(0, "dsa"); from algorithms import fib_slow, fib_memo
for n in (10, 15, 20, 25):
    c = [0]; fib_slow(n, c); print(n, "naive calls:", c[0])        # watch it grow ~×11 per +5: exponential
def depth(n): return 1 + depth(n - 1) if n else 0
try: depth(5000)
except RecursionError as e: print("too deep:", e)
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

depth 5 सह 5! = 120; fib(25) साधे 242,785 calls, तर फळ्यासह फक्त 49. 10, 15, 20, 25 साठीचे call counts प्रत्येक पायरीला सुमारे ×11 ने वाढतात, आणि depth(5000) RecursionError देतो.

🏁 तुम्ही आत्ताच काय सिद्ध केले

तुम्ही base case आणि छोटा call लिहू शकता, तुम्ही stack ची मर्यादा पाहिली, आणि पुन्हा पुन्हा येणारे उप-प्रश्न exponential का असतात ते मोजले.

⚠️ नेहमीच्या चुका

base case नाही, किंवा असा base case जो कधीच गाठला जात नाही → अनंत recursion.
दहा लाख elements च्या list वर recursion करणे (loop वापरा).
program अडकेपर्यंत एकमेकांवर येणारे (overlapping) उप-प्रश्न लक्षात न येणे (धडा 11 हे सुधारतो).

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: JSON parsers, directory walkers, dependency resolvers आणि query planners recursive असतात; त्या प्रत्येकाला खऱ्या data वर एकदा तरी "maximum recursion depth exceeded" भेटलेला आहे.

⏭️ पुढे

धडा 07 — sorting: वर्गाला उंचीनुसार रांगेत लावणे, चार प्रकारे, वेळ मोजून.

🪆 Lesson 06 — Recursion: the head asks the deputy

📍 You are here: Lesson 06 of 12 · Next: lesson-07-sorting

📦 What's in this branch

Lessons 01–06. Solving a question by asking a smaller version of it, the stack that holds the unanswered ones, and the classic way it goes wrong.

dsa/algorithms.py — factorial (records depth), fib_slow (counts calls), fib_memo (lesson 11's board)
dsa/demo.py — recursion

🧒 Explain like I'm 5

The head wants to know how many ways 5 pupils can line up (5!). She asks the deputy: "tell me 4! and I'll multiply by 5." The deputy asks a teacher for 3!, who asks for 2!, who asks for 1! — and the youngest teacher just knows:

Answers pass back up. Every unanswered question sat on a pile while it waited — that pile is the call stack. If the pile gets a thousand high, Python says stop. And if the head asks the same question through two different deputies, it gets answered twice — which is how fib(25) turns into 242,785 questions.

🗺️ Diagram

flowchart TD
  F5["5! = 5 × 4!"] --> F4["4! = 4 × 3!"] --> F3["3! = 3 × 2!"] --> F2["2! = 2 × 1!"] --> F1["1! = 1 (base case)"]
  F1 -.->|"answers return"| F5

❓ What

A recursive function has a base case (answered directly) and a recursive case (a smaller instance of the same question).
The call stack holds every frame waiting for an answer: depth = memory. Python's limit is ~1,000 frames; deep work needs a loop or your own stack.
Cost = number of calls × work per call. factorial(n): n calls, O(n). fib_slow(n): ~1.6ⁿ calls, O(2ⁿ) — the same sub-questions asked again and again. Memoisation (a dict of answered questions) makes it O(n).
Recursion is the natural shape for trees (lesson 09), DFS (lesson 10), merge/quick sort (lesson 07), backtracking and DP (lesson 11).

🤔 Why

Half the structures ahead are recursive by nature; writing them iteratively first is painful. But recursion has two traps — depth and repeated work — and this lesson makes both visible before you meet them in a tree.

🔧 How (in this repo)

factorial takes a one-element list and records the deepest n it reached; fib_slow increments a counter on every call; fib_memo checks a dict first. demo.py recursion prints the depth and both call counts.

🧪 Try it

python3 dsa/demo.py recursion
python3 - <<'EOF'
import sys; sys.path.insert(0, "dsa"); from algorithms import fib_slow, fib_memo
for n in (10, 15, 20, 25):
    c = [0]; fib_slow(n, c); print(n, "naive calls:", c[0])        # watch it grow ~×11 per +5: exponential
def depth(n): return 1 + depth(n - 1) if n else 0
try: depth(5000)
except RecursionError as e: print("too deep:", e)
EOF

✅ Verify — what you should see

5! = 120 with depth 5; fib(25) 242,785 naive calls versus 49 with a board. The call counts for 10, 15, 20, 25 grow by about ×11 each step, and depth(5000) raises RecursionError.

🏁 What you just proved

You can write a base case and a smaller call, you saw the stack's limit, and you measured why repeated sub-questions are exponential.

⚠️ Common mistakes

No base case, or one that is never reached → infinite recursion.
Recursing over a million-element list (use a loop).
Not noticing overlapping sub-problems until the program hangs (lesson 11 fixes it).

🏭 Why this matters in production: JSON parsers, directory walkers, dependency resolvers and query planners are recursive; every one of them has met a "maximum recursion depth exceeded" on real data once.

⏭️ Next

Lesson 07 — sorting: lining the class up by height, four ways, timed.

← Previoushash maps Next →sorting

This page is the lesson's README from the lesson-06-recursion branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.