Unit 5 · Lesson 5
Introduction to Recursion
Functions that call themselves.
Understand base vs recursive case
Trace recursive calls
Write recursive number functions
Know when recursion fits
What Is Recursion?
A function that calls itself. Needs a base case to stop:
def countdown(n):
if n <= 0: # BASE CASE
print("Liftoff!")
return
print(n)
countdown(n - 1) # RECURSIVE CASE
Two rules: 1) Always have a base case. 2) Each call must move toward the base case.
Practice Time
Challenges
Challenge 1: Countdown (Recursive)
Guided
Rewrite countdown with recursion.
Instructions:
countdown(n) prints n down to 1, then "Liftoff!". No loops!Hint: Base: if n<=0: print("Liftoff!"); return. Recursive: print(n); countdown(n-1)
Challenge 2: Factorial
Guided
Implement factorial(n) recursively.
Instructions:
factorial(n) returns n! Base: factorial(0)=1.Hint: Base: if n<=1: return 1. Recursive: return n * factorial(n-1)
Challenge 3: Sum of List
Solo
Recursively sum a list.
Instructions:
recursive_sum(lst). Base: empty list=0. Recursive: first + sum of rest.Hint: Base: if len(lst)==0: return 0. Recursive: return lst[0] + recursive_sum(lst[1:])
Challenge 4: Fibonacci
Stretch
Implement fibonacci(n).
Instructions: fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2).
Hint: Base: if n<=0: return 0. if n==1: return 1. Recursive: return fibonacci(n-1)+fibonacci(n-2)