← Back

Home › Hindi › Recursion Hindi में

Python Recursion — base case, call stack और RecursionError

🌐 यह page Hindi में है · Read the English functions guide →

Base case समझोFactorial + FibonacciRecursionError का कारणRecursion vs loop

Recursion क्या है — एक line में

Recursion = function खुद को call करता है, और हर call problem को थोड़ा छोटा कर देती है, जब तक एक ऐसा मामला न आ जाए जहाँ जवाब सीधे पता हो। उस सीधे जवाब वाले मामले को base case कहते हैं।

हर function में दो हिस्से होते हैं:

def countdown(n):
    if n <= 0:                 # base case — सबसे पहले check करो
        print("Go!")
        return
    print(n)
    countdown(n - 1)           # recursive case — input छोटा हुआ

countdown(3)                   # 3 2 1 Go!

Base case — सबसे ज़रूरी हिस्सा

Base case भूल गए तो function कभी नहीं रुकेगा:

def countdown(n):
    print(n)
    countdown(n - 1)      # रोकने वाला कुछ नहीं

countdown(3)
3
2
1
0
-1
...
Traceback (most recent call last):
  File "demo.py", line 6, in 
    countdown(3)
  File "demo.py", line 3, in countdown
    countdown(n - 1)
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Traceback में वह line ध्यान से पढ़ो — [Previous line repeated 996 more times]। यही बताता है कि कौन-सी call बार-बार दोहराई गई।

Call stack असल में क्या कर रहा है

हर function call का अपना frame stack पर बनता है — उसके arguments और local variables वहीं रहते हैं। Recursion में frames जमा होते जाते हैं, और base case पर पहुँचकर एक-एक करके वापस खाली होते हैं:

def factorial(n):
    if n <= 1:              # base case
        return 1
    return n * factorial(n - 1)

print(factorial(4))         # 24

# अंदर क्या हुआ:
# factorial(4) = 4 * factorial(3)
# factorial(3) = 3 * factorial(2)
# factorial(2) = 2 * factorial(1)
# factorial(1) = 1            <- base case, यहीं रुका
# वापस: 2*1 = 2, 3*2 = 6, 4*6 = 24

इसीलिए base case को recursive call से पहले लिखते हैं। अगर उसे नीचे लिखोगे तो वह कभी execute ही नहीं होगा, क्योंकि ऊपर वाली line खुद को call करती रहेगी।

Fibonacci — recursion का सबसे बड़ा जाल

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print([fib(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

कोड सुंदर है, पर fib(35) में भी सेकंड लगेंगे — क्योंकि वही value बार-बार दोबारा गिनी जाती है। fib(5) के लिए fib(3) दो बार, fib(2) तीन बार चलता है। calls exponential में बढ़ती हैं।

Fix आसान है — results याद रखो:

from functools import lru_cache

@lru_cache(maxsize=None)     # एक बार गिना, दोबारा नहीं
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(100))              # तुरंत — 354224848179261915075

इसे memoization कहते हैं, और यह interview का favourite सवाल है: recursion लिखो, फिर बताओ कि धीमा क्यों है और कैसे ठीक करोगे।

RecursionError क्यों आता है

Python की call stack की default limit 1000 है (sys.getrecursionlimit() से देखो)। उससे गहरी recursion पर Python program रोक देता है — यह safety net है, bug नहीं। असली bug यह है कि recursion रुक क्यों नहीं रही:

sys.setrecursionlimit(10000) limit बढ़ा देता है, पर यह असली fix नहीं — हर frame memory खाता है, और बहुत ज़्यादा बढ़ाने पर process सीधे crash (segfault) हो जाता है।

Recursion vs loop — कब क्या

# recursive
def total_r(items):
    if not items:
        return 0
    return items[0] + total_r(items[1:])

# loop — वही काम, कोई limit नहीं, तेज़ भी
def total_l(items):
    s = 0
    for x in items:
        s += x
    return s

print(total_r([1, 2, 3]), total_l([1, 2, 3]))   # 6 6

नियम: data खुद nested/tree जैसा हो (folder के अंदर folder, JSON के अंदर JSON, DOM, linked structure) तो recursion स्वाभाविक है। data सीधी line में हो (list, file की lines, counting) तो loop लिखो — तेज़, कम memory, और कोई recursion limit नहीं।

🛠️ Practice करो (free, browser में)

पढ़ना काफी नहीं — यही bug खुद fix करके देखो। नीचे के problems browser में ही चलते हैं, कोई install नहीं, कोई login नहीं।

सारे free problems देखो →

अक्सर पूछे जाने वाले सवाल

Recursion में base case क्यों ज़रूरी है?

क्योंकि वही recursion को रोकता है। Base case वह condition है जिस पर function बिना खुद को call किए सीधे return कर देता है। उसके बिना हर call नई call बनाती रहेगी और call stack भरकर RecursionError देगी।

Python की recursion limit कितनी है?

Default 1000 nested calls, जो sys.getrecursionlimit() से देख सकते हो। ध्यान रहे कि यह पूरे stack की गिनती है — अगर code पहले से 50 levels गहरा है तो बाकी 950 बचे हैं, 1000 नहीं।

RecursionError आ जाए तो क्या करें?

पहले देखो कि argument हर call पर छोटा हो रहा है या नहीं, और base case recursive call से पहले लिखा है या नहीं। Comparison में == की जगह <= लगाओ ताकि overshoot पर भी रुक जाए। sys.setrecursionlimit बढ़ाना अस्थायी ढक्कन है — बड़ा data हो तो loop में बदलो।

Fibonacci recursion इतना धीमा क्यों है?

क्योंकि वही subproblem बार-बार दोबारा गिना जाता है — fib(5) के लिए fib(3) दो बार और fib(2) तीन बार चलता है, और calls exponential में बढ़ती हैं। @functools.lru_cache लगा देने पर हर value एक बार ही गिनी जाती है और वही code तुरंत जवाब देता है।

आगे पढ़ो