Recursion - codenoteshub.com

► Understanding Recursion

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems. Each recursive call works on a simpler version of the original problem until reaching a base case.

► Real-World Analogy

Think of recursion like Russian nesting dolls (Matryoshka):
» You open a doll and find a smaller doll inside
» You open that smaller doll and find an even smaller one
» This continues until you reach the tiniest doll (base case)
» Then you start putting them back together from smallest to largest
» Each level solves a similar but smaller version of the same task

► Key Concepts

✓ Base case: The stopping condition that prevents infinite recursion
✓ Recursive case: The part where function calls itself
✓ Call stack: Memory structure storing function calls
✓ Stack overflow: Error when recursion goes too deep
✓ Divide and conquer: Breaking problems into smaller pieces

■ Code Examples

# Simple factorial using recursion
def factorial(n):
    # Base case
    if n == 0 or n == 1:
        return 1
    # Recursive case
    return n * factorial(n - 1)

print(factorial(5))
print(factorial(0))

# Fibonacci sequence
def fibonacci(n):
    if n &lt;= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(f"Fibonacci(6): {fibonacci(6)}")

# Countdown example
def countdown(n):
    if n &lt;= 0:
        print("Blastoff!")
    else:
        print(n)
        countdown(n - 1)

countdown(5)

# Simple factorial using recursion

def factorial(n):

# Base case

if n == 0 or n == 1:

return 1

# Recursive case

return n * factorial(n - 1)

print(factorial(5))

print(factorial(0))

# Fibonacci sequence

def fibonacci(n):

if n <= 1:

return n

return fibonacci(n-1) + fibonacci(n-2)

print(f"Fibonacci(6): {fibonacci(6)}")

# Countdown example

def countdown(n):

if n <= 0:

print("Blastoff!")

else:

print(n)

countdown(n - 1)

countdown(5)