రికర్షన్ మరియు బ్యాక్ట్రాకింగ్
Recursion పునాదులు
Recursive function base case చేరుకునే వరకు సమస్య యొక్క చిన్న రూపంతో తనను తాను call చేసుకుంటుంది.
ప్రతి recursion కి రెండు విషయాలు కావాలి:
- Base case - నేరుగా return చేసే సరళమైన input.
- Recursive case - సమస్యను విభజించి తనను తాను call చేసుకోవడం.
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case
Call Stack - దృశ్యీకరణ
ప్రతి recursive call call stack పైకి frame push చేస్తుంది. Base case return అయినప్పుడు, frames రివర్స్ క్రమంలో pop అవుతాయి.
factorial(4)
→ factorial(3)
→ factorial(2)
→ factorial(1) → 1 return చేస్తుంది
← 2 return చేస్తుంది
← 6 return చేస్తుంది
← 24 return చేస్తుంది
Base case లేకపోతే, stack overflow అవుతుంది. Python default recursion limit 1,000 frames.
Fibonacci - క్లాసిక్ ఉచ్చు
Naïve recursive Fibonacci O(2ⁿ) ఎందుకంటే ఇది అదే sub-problems ను మళ్ళీ మళ్ళీ compute చేస్తుంది. Memoisation దీన్ని O(n) time మరియు space లో పరిష్కరిస్తుంది.
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 - అన్నీ ప్రయత్నించు, తర్వాత రద్దు చేయి
Backtracking అనేది twist తో recursion: మీరు ఎంపిక చేసి, recurse చేసి, తదుపరి option ప్రయత్నించే ముందు ఎంపికను రద్దు చేస్తారు. Maze explore చేయడం అనుకోండి - ముందుకు నడవండి, dead end తగిలితే వెనక్కి, తదుపరి path ప్రయత్నించండి.
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) # ఎంచుకో
backtrack(state, ...) # explore చేయి
state.remove(choice) # రద్దు చేయి
ఈ మూడు-దశల pattern - ఎంచుకో, explore చేయి, రద్దు చేయి - దాదాపు ప్రతి backtracking సమస్య యొక్క వెన్నెముక.
Discussion
Sign in to join the discussion