Recursion

Base case + recursive case

हर recursion को चाहिए (1) base case जो बिना recurse किए लौटे, और (2) recursive case जो base की ओर प्रगति करे। Base case चूकें और stack overflow मिलता है।

Call stack खुलता है

factorial(3) factorial(2) की प्रतीक्षा करता है जो factorial(1) की। फिर परिणाम वापस गुणा होते हैं।

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

# factorial(3)
# = 3 * factorial(2)
# = 3 * (2 * factorial(1))
# = 3 * (2 * 1) = 6

रूसी गुड़िया

एक गुड़िया खोलें तो अंदर छोटी, जब तक छोटी ठोस (base case) न मिले। फिर उन्हें क्रम में बंद करें।

Recursion → iteration

किसी भी recursion को स्पष्ट stack से फिर से लिखा जा सकता है। Tail recursion और दोहराए उप-समस्याएँ (Fibonacci) memoise या bottom-up जाने के संकेत हैं।