Common Algorithms

Recursion Introduction

Many programming problems involve repeating the same operation on smaller pieces of data, like calculating compound interest or navigating folder structures. Recursion provides an elegant way to solve these problems by having a function call itself with progressively simpler inputs until reaching a trivial case.

Recursion is when a function calls itself to solve a problem by breaking it into smaller versions of the same problem.

Key Components

  1. Base case: condition where recursion stops
  2. Recursive case: function calls itself with simpler input
  3. Progress: each call moves toward base case
base_case.py
Replay: real traced execution (multi-file project)
# Importance of base case

import sys


def infinite_recursion(n):
    """Missing base case (don't run!)"""
    # No base case - will cause RecursionError
    return infinite_recursion(n - 1)


def countdown(n):
    """Correct with base case"""
    # Base case
    if n <= 0:
        print("Liftoff!")
        return 0

    # Recursive case
    print(n)
    return countdown(n - 1)


def bad_base_case(n):
    """Wrong base case"""
    # Base case never reached for negative input
    if n == 0:
        return 0
    return bad_base_case(n - 1)


# Test base cases
print("Countdown with proper base case:")
countdown(5)

print("\nTrying infinite recursion with small depth:")
# Set a smaller recursion limit for demonstration
old_limit = sys.getrecursionlimit()
sys.setrecursionlimit(20)

try:
    # This will overflow quickly
    infinite_recursion(10)
except RecursionError:
    print("RecursionError caught!")

# Restore original limit
sys.setrecursionlimit(old_limit)

print("\nWrong base case with positive input (safe):")
bad_base_case(3)
print("Completed successfully")

# Uncommenting this will cause RecursionError
# print("\nWrong base case with negative input:")
# bad_base_case(-5)

  1. print("Countdown with proper base case:")

    32# Test base cases33print("Countdown with proper base case:")34countdown(5)
    outputCountdown with proper base case:

  2. def countdown(n):

    pass 1 of 6
    12def countdown(n5):13    """Correct with base case"""14    # Base case15    if n <= 0:16        print("Liftoff!")17        return 01819    # Recursive case20    print(n5)21    return countdown(n5 - 1)
    output5
    All 6 passes — pass 1 is the card above
    passn
    15
    24
    33
    42
    51
    60

  3. if n <= 0:

    14# Base case15if n0 <= 0:16    print("Liftoff!")17    return 0
    outputLiftoff!

  4. old_limit ← 1000

    33print("Countdown with proper base case:")34countdown(5)3536print("\nTrying infinite recursion with small depth:")37# Set a smaller recursion limit for demonstration38old_limit→ 1000 = sys<module 'sys' (built-in)>.getrecursionlimit()39sys<module 'sys' (built-in)>.setrecursionlimit(20)
    output
Trying infinite recursion with small depth:

  5. def infinite_recursion(n):

    pass 1 of 18
    6def infinite_recursion(n10):7    """Missing base case (don't run!)"""8    # No base case - will cause RecursionError9    return infinite_recursion(n10 - 1)
    18 passes — pass 1 is the card above
    passn
    110
    29
    38
    47
    56
    65
    74
    83
    92
    ⋯ 7 more passes ⋯
    17-6
    18(empty)

  6. except RecursionError:

    43    infinite_recursion(10)44except RecursionError:45    print("RecursionError caught!")
    outputRecursionError caught!

  7. sys.setrecursionlimit(old_limit)

    47# Restore original limit48sys<module 'sys' (built-in)>.setrecursionlimit(old_limit1000)4950print("\nWrong base case with positive input (safe):")51bad_base_case(3)52print("Completed successfully")
    output
Wrong base case with positive input (safe):

  8. def bad_base_case(n):

    pass 1 of 4
    24def bad_base_case(n3):25    """Wrong base case"""26    # Base case never reached for negative input27    if n == 0:28        return 029    return bad_base_case(n3 - 1)
    All 4 passes — pass 1 is the card above
    passn
    13
    22
    31
    40

  9. if n == 0:

    26# Base case never reached for negative input27if n0 == 0:28    return 029return bad_base_case(n - 1)

  10. bad_base_case(3)

    50print("\nWrong base case with positive input (safe):")51bad_base_case(3)52print("Completed successfully")
    outputCompleted successfully
base_case The condition where recursion stops and returns a direct value without further recursive calls

Classic Example: Factorial

limit
factorial.py
Replay: real traced execution (multi-file project)
# Basic factorial recursion


def factorial(n):
    """Recursive factorial"""
    # Base case
    if n <= 1:
        return 1

    # Recursive case
    # n! = n × (n-1)!
    return n * factorial(n - 1)


# Test factorial
limit = 7
for i in range(limit):
    print(f"{i}! = {factorial(i)}")

print(f"\n10! = {factorial(10)}")


# Basic factorial recursion


def factorial(n):
    """Recursive factorial"""
    # Base case
    if n <= 1:
        return 1

    # Recursive case
    # n! = n × (n-1)!
    return n * factorial(n - 1)


# Test factorial
limit = 5
for i in range(limit):
    print(f"{i}! = {factorial(i)}")

print(f"\n10! = {factorial(10)}")


# Basic factorial recursion


def factorial(n):
    """Recursive factorial"""
    # Base case
    if n <= 1:
        return 1

    # Recursive case
    # n! = n × (n-1)!
    return n * factorial(n - 1)


# Test factorial
limit = 9
for i in range(limit):
    print(f"{i}! = {factorial(i)}")

print(f"\n10! = {factorial(10)}")

  1. limit ← 7

    15# Test factorial16limit→ 7 = 717#@limit=5, 9

  2. for i in range(limit):

    pass 1 of 7
    17#@limit=5, 918for i0 in range(limit7):19    print(f"{i0}! = {factorial(i)}")
    All 7 passes — pass 1 is the card above
    passi
    10
    21
    32
    43
    54
    65
    76

  3. def factorial(n):

    pass 1 of 32
    4def factorial(n0):5    """Recursive factorial"""6    # Base case
    32 passes — pass 1 is the card above
    passn
    10
    21
    32
    41
    53
    62
    71
    84
    93
    ⋯ 21 more passes ⋯
    312
    321

  4. if n <= 1:

    pass 1 of 8
    6# Base case7if n0 <= 1:8    return 1
    All 8 passes — pass 1 is the card above
    passn
    10
    21
    31
    41
    51
    61
    71
    81

  5. print(f"{i}! = {factorial(i)}")

    18for i in range(limit):19    print(f"{i0}! = {factorial(i)}")
    output0! = 1

  6. print(f"{i}! = {factorial(i)}")

    18for i in range(limit):19    print(f"{i1}! = {factorial(i)}")
    output1! = 1

  7. print(f"{i}! = {factorial(i)}")

    18for i in range(limit):19    print(f"{i2}! = {factorial(i)}")
    output2! = 2

  8. print(f"{i}! = {factorial(i)}")

    18for i in range(limit):19    print(f"{i3}! = {factorial(i)}")
    output3! = 6

  9. print(f"{i}! = {factorial(i)}")

    18for i in range(limit):19    print(f"{i4}! = {factorial(i)}")
    output4! = 24

  10. print(f"{i}! = {factorial(i)}")

    18for i in range(limit):19    print(f"{i5}! = {factorial(i)}")
    output5! = 120

  11. print(f"{i}! = {factorial(i)}")

    18for i in range(limit):19    print(f"{i6}! = {factorial(i)}")
    output6! = 720

  12. print(f" 10! = {factorial(10)}")

    21print(f"\n10! = {factorial(10)}")

  13. print(f" 10! = {factorial(10)}")

    21print(f"\n10! = {factorial(10)}")
    output
10! = 3628800

  1. limit ← 5

    15# Test factorial16limit→ 5 = 517for i in range(limit):

  2. for i in range(limit):

    pass 1 of 5
    16limit = 517for i0 in range(limit5):18    print(f"{i0}! = {factorial(i)}")
    All 5 passes — pass 1 is the card above
    passi
    10
    21
    32
    43
    54

  3. def factorial(n):

    pass 1 of 21
    4def factorial(n0):5    """Recursive factorial"""6    # Base case
    21 passes — pass 1 is the card above
    passn
    10
    21
    32
    41
    53
    62
    71
    84
    93
    ⋯ 10 more passes ⋯
    202
    211

  4. if n <= 1:

    pass 1 of 6
    6# Base case7if n0 <= 1:8    return 1
    All 6 passes — pass 1 is the card above
    passn
    10
    21
    31
    41
    51
    61

  5. print(f"{i}! = {factorial(i)}")

    17for i in range(limit):18    print(f"{i0}! = {factorial(i)}")
    output0! = 1

  6. print(f"{i}! = {factorial(i)}")

    17for i in range(limit):18    print(f"{i1}! = {factorial(i)}")
    output1! = 1

  7. print(f"{i}! = {factorial(i)}")

    17for i in range(limit):18    print(f"{i2}! = {factorial(i)}")
    output2! = 2

  8. print(f"{i}! = {factorial(i)}")

    17for i in range(limit):18    print(f"{i3}! = {factorial(i)}")
    output3! = 6

  9. print(f"{i}! = {factorial(i)}")

    17for i in range(limit):18    print(f"{i4}! = {factorial(i)}")
    output4! = 24

  10. print(f" 10! = {factorial(10)}")

    20print(f"\n10! = {factorial(10)}")

  11. print(f" 10! = {factorial(10)}")

    20print(f"\n10! = {factorial(10)}")
    output
10! = 3628800

  1. limit ← 9

    15# Test factorial16limit→ 9 = 917for i in range(limit):

  2. for i in range(limit):

    pass 1 of 9
    16limit = 917for i0 in range(limit9):18    print(f"{i0}! = {factorial(i)}")
    All 9 passes — pass 1 is the card above
    passi
    10
    21
    32
    43
    54
    65
    76
    87
    98

  3. def factorial(n):

    pass 1 of 47
    4def factorial(n0):5    """Recursive factorial"""6    # Base case
    47 passes — pass 1 is the card above
    passn
    10
    21
    32
    41
    53
    62
    71
    84
    93
    ⋯ 36 more passes ⋯
    462
    471

  4. if n <= 1:

    pass 1 of 10
    6# Base case7if n0 <= 1:8    return 1
    All 10 passes — pass 1 is the card above
    passn
    10
    21
    31
    41
    51
    61
    71
    81
    91
    101

  5. print(f"{i}! = {factorial(i)}")

    17for i in range(limit):18    print(f"{i0}! = {factorial(i)}")
    output0! = 1

  6. print(f"{i}! = {factorial(i)}")

    17for i in range(limit):18    print(f"{i1}! = {factorial(i)}")
    output1! = 1

  7. print(f"{i}! = {factorial(i)}")

    17for i in range(limit):18    print(f"{i2}! = {factorial(i)}")
    output2! = 2

  8. print(f"{i}! = {factorial(i)}")

    17for i in range(limit):18    print(f"{i3}! = {factorial(i)}")
    output3! = 6

  9. print(f"{i}! = {factorial(i)}")

    17for i in range(limit):18    print(f"{i4}! = {factorial(i)}")
    output4! = 24

  10. print(f"{i}! = {factorial(i)}")

    17for i in range(limit):18    print(f"{i5}! = {factorial(i)}")
    output5! = 120

  11. print(f"{i}! = {factorial(i)}")

    17for i in range(limit):18    print(f"{i6}! = {factorial(i)}")
    output6! = 720

  12. print(f"{i}! = {factorial(i)}")

    17for i in range(limit):18    print(f"{i7}! = {factorial(i)}")
    output7! = 5040

  13. print(f"{i}! = {factorial(i)}")

    17for i in range(limit):18    print(f"{i8}! = {factorial(i)}")
    output8! = 40320

  14. print(f" 10! = {factorial(10)}")

    20print(f"\n10! = {factorial(10)}")

  15. print(f" 10! = {factorial(10)}")

    20print(f"\n10! = {factorial(10)}")
    output
10! = 3628800
factorial A mathematical function where n! = n * (n-1) * ... * 1, naturally expressed recursively

How It Works

trace.py
Replay: real traced execution (multi-file project)
# Factorial with trace


depth = 0


def factorial(n):
    """Factorial with trace"""
    global depth

    # Indent based on depth
    indent = "  " * depth

    print(f"{indent}→ factorial({n})")
    depth += 1

    # Base and recursive cases
    if n <= 1:
        result = 1
        print(f"{indent}  Base case: return 1")
    else:
        result = n * factorial(n - 1)
        print(f"{indent}  Return {n} * factorial({n-1}) = {result}")

    depth -= 1
    print(f"{indent}← returning {result}")

    return result


# Test with trace
print("Computing factorial(5):\n")
result = factorial(5)
print(f"\nFinal result: {result}")

  1. depth ← 0

    4depth→ 0 = 0567def factorial(n):8    """Factorial with trace"""9    global depth1011    # Indent based on depth12    indent = "  " * depth1314    print(f"{indent}→ factorial({n})")15    depth += 11617    # Base and recursive cases18    if n <= 1:19        result = 120        print(f"{indent}  Base case: return 1")21    else:22        result = n * factorial(n - 1)23        print(f"{indent}  Return {n} * factorial({n-1}) = {result}")2425    depth -= 126    print(f"{indent}← returning {result}")2728    return result293031# Test with trace32print("Computing factorial(5):\n")33result = factorial(5)34print(f"\nFinal result: {result}")
    outputComputing factorial(5):

  2. indent ← (empty), depth ← 1

    pass 1 of 5
    7def factorial(n5):8    """Factorial with trace"""9    global depth1011    # Indent based on depth12    indent→ (empty) = "  " * depth01314    print(f"{indent(empty)}→ factorial({n5})")15    depth→ 1 += 1
    output→ factorial(5)
    All 5 passes — pass 1 is the card above
    passnindentdepthresult
    15(empty)0 → 1—
    24 1 → 2—
    33 2 → 3—
    42 3 → 4—
    51 4 → 51

  3. else:

    pass 1 of 4
    19    result = 120    print(f"{indent}  Base case: return 1")21else:22    result = n5 * factorial(n - 1)23    print(f"{indent}  Return {n} * factorial({n-1}) = {result}")
    All 4 passes — pass 1 is the card above
    passnindentresult
    15——
    24——
    33——
    42 1

  4. result ← 1

    17# Base and recursive cases18if n1 <= 1:19    result→ 1 = 120    print(f"{indent        }  Base case: return 1")21else:
    output          Base case: return 1

  5. depth ← 4

    25depth→ 4 -= 126print(f"{indent        }← returning {result1}")2728return result1
    output        ← returning 1

  6. result ← 2

    21else:22    result→ 2 = n2 * factorial(n - 1)23    print(f"{indent      }  Return {n2} * factorial({n-1}) = {result2}")
    output        Return 2 * factorial(1) = 2

  7. depth ← 3

    25depth→ 3 -= 126print(f"{indent      }← returning {result2}")2728return result2
    output      ← returning 2

  8. n ← 3, result ← 6

    21else:22    result→ 6 = n→ 3 * factorial(n - 1)23    print(f"{indent    }  Return {n3} * factorial({n-1}) = {result6}")
    output      Return 3 * factorial(2) = 6

  9. depth ← 2

    25depth→ 2 -= 126print(f"{indent    }← returning {result6}")2728return result6
    output    ← returning 6

  10. n ← 4, result ← 24

    21else:22    result→ 24 = n→ 4 * factorial(n - 1)23    print(f"{indent  }  Return {n4} * factorial({n-1}) = {result24}")
    output    Return 4 * factorial(3) = 24

  11. depth ← 1

    25depth→ 1 -= 126print(f"{indent  }← returning {result24}")2728return result24
    output  ← returning 24

  12. n ← 5, result ← 120

    21else:22    result→ 120 = n→ 5 * factorial(n - 1)23    print(f"{indent(empty)}  Return {n5} * factorial({n-1}) = {result120}")
    output  Return 5 * factorial(4) = 120

  13. depth ← 0

    25depth→ 0 -= 126print(f"{indent(empty)}← returning {result120}")2728return result120
    output← returning 120

  14. result ← 120

    32print("Computing factorial(5):\n")33result→ 120 = factorial(5)34print(f"\nFinal result: {result120}")
    output
Final result: 120

See the Call Stack

The trace above uses indentation to show which calls are waiting. These diagrams pin the same factorial(5) run: five frames open, factorial(1) returns 1, then the waiting multiplications finish in reverse order.

Stack growth for factorial(5)Stack growth for factorial(5)f(5)f(4)f(3)f(2)f(1)
The recursive calls open one frame at a time: f(5), f(4), f(3), f(2), then f(1). Each frame is waiting for the smaller call below it.
Waiting work stored in each frameWaiting work stored in each framen=5; 5*?n=4; 4*?n=3; 3*?n=2; 2*?n=1; return 1
Before the base case returns, each open frame keeps its own n and the multiplication it still has to finish.
The base case stops the chainThe base case stops the chainf(1)n <= 1return 1
At f(1), the test n <= 1 is true, so the function returns 1 instead of making another recursive call.
Returns unwind back to factorial(5)Returns unwind back to factorial(5)f(5)->120f(4)->24f(3)->6f(2)->2f(1)->1
After f(1) returns 1, the waiting multiplications finish upward: 2, 6, 24, and finally 120.

Recursion vs Iteration

vs_iteration.py
Replay: real traced execution (multi-file project)
# Recursion vs iteration

import time


def sum_recursive(n):
    """Recursive sum"""
    # Base case
    if n <= 0:
        return 0
    # Recursive case
    return n + sum_recursive(n - 1)


def sum_iterative(n):
    """Iterative sum"""
    # Loop approach
    total = 0
    for i in range(1, n + 1):
        total += i
    return total


def power_recursive(base, exp):
    """Recursive power"""
    # Base case
    if exp == 0:
        return 1
    # Recursive case
    return base * power_recursive(base, exp - 1)


def power_iterative(base, exp):
    """Iterative power"""
    # Loop approach
    result = 1
    for _ in range(exp):
        result *= base
    return result


# Compare both approaches
print("Sum 1 to 10:")
print(f"  Recursive: {sum_recursive(10)}")
print(f"  Iterative: {sum_iterative(10)}")

print("\n2^8:")
print(f"  Recursive: {power_recursive(2, 8)}")
print(f"  Iterative: {power_iterative(2, 8)}")

# Performance comparison kept small so trace replay stays readable.
n = 12

start = time.perf_counter()
r1 = sum_recursive(n)
time_recursive = time.perf_counter() - start

start = time.perf_counter()
r2 = sum_iterative(n)
time_iterative = time.perf_counter() - start

print(f"\nPerformance (sum to {n}):")
print(f"  Recursive: {time_recursive * 1000:.4f} ms")
print(f"  Iterative: {time_iterative * 1000:.4f} ms")
print(f"  Speedup:   {time_recursive / time_iterative:.2f}x")

  1. print("Sum 1 to 10:")

    42# Compare both approaches43print("Sum 1 to 10:")44print(f"  Recursive: {sum_recursive(10)}")45print(f"  Iterative: {sum_iterative(10)}")
    outputSum 1 to 10:

  2. def sum_recursive(n):

    pass 1 of 24
    6def sum_recursive(n10):7    """Recursive sum"""8    # Base case9    if n <= 0:10        return 011    # Recursive case12    return n10 + sum_recursive(n - 1)
    24 passes — pass 1 is the card above
    passn
    110
    29
    38
    47
    56
    65
    74
    83
    92
    ⋯ 13 more passes ⋯
    231
    240

  3. if n <= 0:

    pass 1 of 2
    8# Base case9if n0 <= 0:10    return 011# Recursive case

  4. print(f" Recursive: {sum_recursive(10)}")

    43print("Sum 1 to 10:")44print(f"  Recursive: {sum_recursive(10)}")45print(f"  Iterative: {sum_iterative(10)}")
    output  Recursive: 55

  5. total ← 0

    pass 1 of 2
    15def sum_iterative(n10):16    """Iterative sum"""17    # Loop approach18    total→ 0 = 019    for i in range(1, n + 1):

  6. total ← 1

    pass 1 of 22
    18total = 019for i1 in range(1, n10 + 1):20    total→ 1 += i121return total
    22 passes — pass 1 is the card above
    passintotal
    11100 → 1
    22101 → 3
    33103 → 6
    44106 → 10
    551010 → 15
    661015 → 21
    771021 → 28
    881028 → 36
    991036 → 45
    ⋯ 11 more passes ⋯
    21111255 → 66
    22121266 → 78

  7. return total

    20    total += i21return total55

  8. print(f" Iterative: {sum_iterative(10)}")

    44print(f"  Recursive: {sum_recursive(10)}")45print(f"  Iterative: {sum_iterative(10)}")4647print("\n2^8:")48print(f"  Recursive: {power_recursive(2, 8)}")49print(f"  Iterative: {power_iterative(2, 8)}")
    output  Iterative: 55

2^8:

  9. def power_recursive(base, exp):

    pass 1 of 9
    24def power_recursive(base2, exp8):25    """Recursive power"""26    # Base case27    if exp == 0:28        return 129    # Recursive case30    return base2 * power_recursive(base, exp8 - 1)
    All 9 passes — pass 1 is the card above
    passexp
    18
    27
    36
    45
    54
    63
    72
    81
    90

  10. if exp == 0:

    26# Base case27if exp0 == 0:28    return 129# Recursive case

  11. print(f" Recursive: {power_recursive(2, 8)}")

    47print("\n2^8:")48print(f"  Recursive: {power_recursive(2, 8)}")49print(f"  Iterative: {power_iterative(2, 8)}")
    output  Recursive: 256

  12. result ← 1

    33def power_iterative(base2, exp8):34    """Iterative power"""35    # Loop approach36    result→ 1 = 137    for _ in range(exp):

  13. result ← 2

    pass 1 of 8
    36result = 137for _0 in range(exp8):38    result→ 2 *= base239return result
    All 8 passes — pass 1 is the card above
    pass_result
    101 → 2
    212 → 4
    324 → 8
    438 → 16
    5416 → 32
    6532 → 64
    7664 → 128
    87128 → 256

  14. return result

    38    result *= base39return result256

  15. n ← 12, start ← 1010621.691784896

    48print(f"  Recursive: {power_recursive(2, 8)}")49print(f"  Iterative: {power_iterative(2, 8)}")5051# Performance comparison kept small so trace replay stays readable.52n→ 12 = 125354start→ 1010621.691784896 = time<module 'time' (built-in)>.perf_counter()55r1 = sum_recursive(n12)56time_recursive = time.perf_counter() - start
    output  Iterative: 256

  16. if n <= 0:

    pass 2 of 2
    8# Base case9if n0 <= 0:10    return 011# Recursive case

  17. r1 ← 78, time_recursive ← 6.685801781713963e-05, start ← 1010621.691859894

    54start = time.perf_counter()55r1→ 78 = sum_recursive(n12)56time_recursive→ 6.685801781713963e-05 = time<module 'time' (built-in)>.perf_counter() - start1010621.6917848965758start→ 1010621.691859894 = time<module 'time' (built-in)>.perf_counter()59r2 = sum_iterative(n12)60time_iterative = time.perf_counter() - start

  18. total ← 0

    pass 2 of 2
    15def sum_iterative(n12):16    """Iterative sum"""17    # Loop approach18    total→ 0 = 019    for i in range(1, n + 1):

  19. return total

    20    total += i21return total78

  20. r2 ← 78, time_iterative ← 6.138707976788282e-05

    58start = time.perf_counter()59r2→ 78 = sum_iterative(n12)60time_iterative→ 6.138707976788282e-05 = time<module 'time' (built-in)>.perf_counter() - start1010621.6918598946162print(f"\nPerformance (sum to {n12}):")63print(f"  Recursive: {time_recursive6.685801781713963e-05 * 1000:.4f} ms")64print(f"  Iterative: {time_iterative6.138707976788282e-05 * 1000:.4f} ms")65print(f"  Speedup:   {time_recursive6.685801781713963e-05 / time_iterative6.138707976788282e-05:.2f}x")
    output
Performance (sum to 12):
  Recursive: 0.0669 ms
  Iterative: 0.0614 ms
  Speedup:   1.09x

Characteristics

  • Elegant: solves complex problems with simple code
  • Memory: uses call stack
  • Performance: often slower than iteration
  • Natural fit: trees, graphs, divide-and-conquer

When to Use

  • Problem naturally recursive
  • Divide and conquer algorithms
  • Backtracking problems
  • Mathematical sequences

When to Avoid

  • Simple loops work better
  • Very deep recursion
  • Performance critical code
  • Python recursion limit concerns

Fibonacci Example

fibonacci.py
Replay: real traced execution (multi-file project)
# Fibonacci sequence


def fibonacci(n):
    """Recursive fibonacci"""
    # Base cases
    if n <= 1:
        return n

    # Recursive case
    # fib(n) = fib(n-1) + fib(n-2)
    return fibonacci(n - 1) + fibonacci(n - 2)


# Fibonacci with call counting
call_count = 0


def fibonacci_counted(n):
    """Fibonacci with call counting"""
    global call_count
    call_count += 1

    if n <= 1:
        return n

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


# Test fibonacci
print("Fibonacci sequence:")
for i in range(7):
    print(f"fib({i}) = {fibonacci(i)}")

# Count calls for fib(6)
call_count = 0
result = fibonacci_counted(6)
print(f"\nfib(6) = {result}, required {call_count} calls")

# Count calls for fib(8)
call_count = 0
result = fibonacci_counted(8)
print(f"fib(8) = {result}, required {call_count} calls")

  1. call_count ← 0

    15# Fibonacci with call counting16call_count→ 0 = 0171819def fibonacci_counted(n):20    """Fibonacci with call counting"""21    global call_count22    call_count += 12324    if n <= 1:25        return n2627    return fibonacci_counted(n - 1) + fibonacci_counted(n - 2)282930# Test fibonacci31print("Fibonacci sequence:")32for i in range(7):
    outputFibonacci sequence:

  2. for i in range(7):

    pass 1 of 7
    31print("Fibonacci sequence:")32for i0 in range(7):33    print(f"fib({i0}) = {fibonacci(i)}")
    All 7 passes — pass 1 is the card above
    passi
    10
    21
    32
    43
    54
    65
    76

  3. def fibonacci(n):

    pass 1 of 59
    4def fibonacci(n0):5    """Recursive fibonacci"""6    # Base cases
    59 passes — pass 1 is the card above
    passn
    10
    21
    32
    41
    50
    63
    72
    81
    90
    ⋯ 48 more passes ⋯
    581
    590

  4. if n <= 1:

    pass 1 of 33
    6# Base cases7if n0 <= 1:8    return n0
    33 passes — pass 1 is the card above
    passn
    10
    21
    31
    40
    51
    60
    71
    81
    90
    ⋯ 22 more passes ⋯
    321
    330

  5. print(f"fib({i}) = {fibonacci(i)}")

    32for i in range(7):33    print(f"fib({i0}) = {fibonacci(i)}")
    outputfib(0) = 0

  6. print(f"fib({i}) = {fibonacci(i)}")

    32for i in range(7):33    print(f"fib({i1}) = {fibonacci(i)}")
    outputfib(1) = 1

  7. print(f"fib({i}) = {fibonacci(i)}")

    32for i in range(7):33    print(f"fib({i2}) = {fibonacci(i)}")
    outputfib(2) = 1

  8. print(f"fib({i}) = {fibonacci(i)}")

    32for i in range(7):33    print(f"fib({i3}) = {fibonacci(i)}")
    outputfib(3) = 2

  9. print(f"fib({i}) = {fibonacci(i)}")

    32for i in range(7):33    print(f"fib({i4}) = {fibonacci(i)}")
    outputfib(4) = 3

  10. print(f"fib({i}) = {fibonacci(i)}")

    32for i in range(7):33    print(f"fib({i5}) = {fibonacci(i)}")
    outputfib(5) = 5

  11. print(f"fib({i}) = {fibonacci(i)}")

    32for i in range(7):33    print(f"fib({i6}) = {fibonacci(i)}")
    outputfib(6) = 8

  12. call_count ← 0

    35# Count calls for fib(6)36call_count→ 0 = 037result = fibonacci_counted(6)38print(f"\nfib(6) = {result}, required {call_count} calls")

  13. call_count ← 1

    pass 1 of 92
    19def fibonacci_counted(n6):20    """Fibonacci with call counting"""21    global call_count22    call_count→ 1 += 12324    if n <= 1:25        return n2627    return fibonacci_counted(n6 - 1) + fibonacci_counted(n - 2)
    92 passes — pass 1 is the card above
    passncall_count
    160 → 1
    251 → 2
    342 → 3
    433 → 4
    524 → 5
    615 → 6
    706 → 7
    817 → 8
    928 → 9
    ⋯ 81 more passes ⋯
    91165 → 66
    92066 → 67

  14. if n <= 1:

    pass 1 of 47
    24if n1 <= 1:25    return n1
    47 passes — pass 1 is the card above
    passn
    11
    20
    31
    41
    50
    61
    70
    81
    91
    ⋯ 36 more passes ⋯
    461
    470

  15. result ← 8, call_count ← 0

    36call_count = 037result→ 8 = fibonacci_counted(6)38print(f"\nfib(6) = {result8}, required {call_count25} calls")3940# Count calls for fib(8)41call_count→ 0 = 042result = fibonacci_counted(8)43print(f"fib(8) = {result}, required {call_count} calls")
    output
fib(6) = 8, required 25 calls

  16. result ← 21

    41call_count = 042result→ 21 = fibonacci_counted(8)43print(f"fib(8) = {result21}, required {call_count67} calls")
    outputfib(8) = 21, required 67 calls

Exercise: practical.py

Implement a recursive countdown function and a recursive sum of digits function