Chapter 6DSA (Data Structures & Algorithms)~1 min read
Recursion
Function स्वतःला Call करतो
Recursion म्हणजे function स्वतःलाच call करणे. प्रत्येक recursive function मध्ये Base Case (कधी थांबायचं) आणि Recursive Case (स्वतःला call कसं करायचं) असतात.
Marathi Analogy
Recursion म्हणजे आरशांसमोर आरसा ठेवणे — image च्या आत image, त्याच्या आत image. पण कुठेतरी थांबतं (base case) — नाहीतर infinite recursion!
Factorial — classic recursion
python
def factorial(n):
# Base case — कधी थांबायचं
if n <= 1:
return 1
# Recursive case — स्वतःला call
return n * factorial(n - 1)
# factorial(4)
# = 4 * factorial(3)
# = 4 * 3 * factorial(2)
# = 4 * 3 * 2 * factorial(1)
# = 4 * 3 * 2 * 1 = 24
print(factorial(5)) # 120Fibonacci — recursion vs memoization
python
# Simple recursion — O(2^n) — SLOW
def fib_slow(n):
if n <= 1:
return n
return fib_slow(n-1) + fib_slow(n-2)
# Memoization — O(n) — FAST
def fib(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
print(fib(10)) # 55
print(fib(50)) # 12586269025 — instant!💡
Base case विसरलात तर Stack Overflow error येतो — function infinite loop मध्ये जातो आणि memory संपतो. नेहमी base case आधी लिहा!
✅ Key Points — लक्षात ठेवा
- ▸Base case — recursion थांबायची condition
- ▸Recursive case — problem reduce करा
- ▸Call stack मध्ये frames साठवतो
- ▸Memoization — repeated subproblems cache करा
- ▸Tree traversal, DFS — recursion वापरतात
0/10 chapters पूर्ण