Recursion और Backtracking
Recursion Fundamentals
Recursive function खुद को problem के छोटे version के साथ call करता है जब तक base case न आ जाए जो chain रोक दे।
हर recursion को दो चीज़ें चाहिए:
- Base case - सबसे simple input जहाँ सीधे return करो।
- Recursive case - problem तोड़ो और खुद को call करो।
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case
Call Stack - Visualised
हर recursive call call stack पर एक frame push करती है। Base case return होने पर frames reverse order में pop होते हैं।
factorial(4)
→ factorial(3)
→ factorial(2)
→ factorial(1) → returns 1
← returns 2
← returns 6
← returns 24
Base case न हो तो stack overflow। Python की default recursion limit 1,000 frames है।
Fibonacci - Classic Trap
Naïve recursive Fibonacci O(2ⁿ) है क्योंकि same sub-problems बार-बार compute होते हैं। Memoisation इसे O(n) time और space में fix करता है।
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
Backtracking - सब Try करो, फिर Undo करो
Backtracking recursion है एक twist के साथ: choice बनाओ, recurse करो, फिर choice undo करो और next option try करो। सोचो जैसे maze explore कर रहे हो - आगे जाओ, dead end मिला, वापस आओ, दूसरा रास्ता try करो।
Backtracking Template
def backtrack(state, choices):
if is_solution(state):
result.append(state.copy())
return
for choice in choices:
if is_valid(choice):
state.add(choice) # choose
backtrack(state, ...) # explore
state.remove(choice) # un-choose
यह choose, explore, un-choose pattern लगभग हर backtracking problem की रीढ़ है।
Backtracking template में recursive call के बाद choice undo क्यों करते हैं?
Discussion
Sign in to join the discussion