Lecture 8 — Recursion and Lambda#
🎯 Learning Objectives
By the end of this lecture, you will be able to:
- ✅ Understand recursion and identify base cases vs. recursive cases
- ✅ Implement classic recursive algorithms (Fibonacci, factorial)
- ✅ Write concise anonymous functions with
lambda - ✅ Use
map(),filter(), andsorted()with lambdas - ✅ Know when to prefer recursion vs. iteration
📝 Practice Exercises
- Factorial: Write a recursive function
factorial(n)that returnsn!. Test it withfactorial(5)(expected: 120). - Sum of digits: Write a recursive function
digit_sum(n)that returns the sum of digits of a positive integer. Example:digit_sum(1234)→ 10. - Power function: Write a recursive function
power(base, exp)that computesbaseexpwithout using**. Example:power(2, 10)→ 1024. - Lambda sorting: Given
words = ["banana", "pie", "Washington", "book"], usesorted()with alambdato sort by word length. - Lambda filter: Given
numbers = [1, 4, 9, 16, 25, 36, 49], usefilter()with alambdato keep only values greater than 20. - Challenge — Flatten a nested list: Write a recursive function
flatten(lst)that takes a nested list like[1, [2, [3, 4], 5], 6]and returns[1, 2, 3, 4, 5, 6].
# Exercise 1: Factorial
def factorial(n):
pass # Your code here
# Exercise 2: Sum of digits
def digit_sum(n):
pass # Your code here
# Exercise 3: Power function
def power(base, exp):
pass # Your code here
# Exercise 4: Sort by length
words = ["banana", "pie", "Washington", "book"]
# sorted_words = sorted(words, key=...)
# Exercise 5: Filter values > 20
numbers = [1, 4, 9, 16, 25, 36, 49]
# result = list(filter(...))
# Exercise 6 (Challenge): Flatten nested list
def flatten(lst):
pass # Your code here
Click to show solution
# Exercise 1: Factorial
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(f"factorial(5) = {factorial(5)}") # 120
# Exercise 2: Sum of digits
def digit_sum(n):
if n < 10:
return n
return n % 10 + digit_sum(n // 10)
print(f"digit_sum(1234) = {digit_sum(1234)}") # 10
# Exercise 3: Power function
def power(base, exp):
if exp == 0:
return 1
return base * power(base, exp - 1)
print(f"power(2, 10) = {power(2, 10)}") # 1024
# Exercise 4: Sort by length
words = ["banana", "pie", "Washington", "book"]
sorted_words = sorted(words, key=lambda w: len(w))
print(f"Sorted by length: {sorted_words}")
# Exercise 5: Filter values > 20
numbers = [1, 4, 9, 16, 25, 36, 49]
result = list(filter(lambda x: x > 20, numbers))
print(f"Values > 20: {result}")
# Exercise 6 (Challenge): Flatten nested list
def flatten(lst):
result = []
for item in lst:
if isinstance(item, list):
result.extend(flatten(item))
else:
result.append(item)
return result
print(flatten([1, [2, [3, 4], 5], 6])) # [1, 2, 3, 4, 5, 6]
📑 Table of Contents
🔗 Building on What You Know
In Lecture 7, you learned to define functions with def. Now we'll explore two special patterns: recursion (functions that call themselves) and lambda (tiny anonymous functions). Both are tools that, once understood, unlock elegant solutions to problems that would otherwise require complex loops.
🌍 Real-World Scenario
You are exploring a folder structure on your computer: each folder can contain files and more folders, which themselves contain files and more folders, and so on. To list every file, you need a function that opens a folder, processes its files, and then calls itself on each subfolder. This is recursion — a function that solves a problem by solving smaller versions of the same problem.
Meanwhile, when sorting a list, you might need a tiny throwaway function just to define the sorting key. Writing a full def for one line of logic feels heavy — that's where lambda functions shine.
Recursive function#
A function that calls itself to solve a problem by breaking it into smaller subproblems. It must have a base case to stop recursion.
def fact(n):
if n <= 1: # base case
return 1
return n * fact(n-1) # recursive step
def fact(n):
if n <= 1: # base case
return 1
return n * fact(n-1) # recursive step
fact(3)
6
def fibo(n):
if n <= 1:
return n
return fibo(n-1)+fibo(n-2)
fibo(10)
55
Here are two clean recursive sequence examples:
1) Fibonacci sequence#
Defined by
$\(F(0)=0,\; F(1)=1,\; F(n)=F(n-1)+F(n-2) for \quad n\ge2\)$.
from functools import lru_cache
@lru_cache(None)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
# first 10 terms
print([fib(i) for i in range(10)]) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
2) Geometric sequence#
Defined by
$\( a_0 = a0,\; a_n = r \cdot a_{n-1}.\)$
def geom(n, a0=3, r=2):
if n == 0:
return a0
return r * geom(n-1, a0, r)
# first 6 terms with a0=3, r=2: 3, 6, 12, 24, 48, 96
print([geom(i, a0=3, r=2) for i in range(6)])
Notes: Always include a base case (
n==0orn<=1). In Python, deep recursion can hit the recursion limit; for largen, prefer iterative versions.
lambda function#
A small, anonymous, single-expression function—handy when you need a quick function inline.
Notes: lambda can’t contain statements (only an expression). Great for short “throwaway” functions (e.g., sort keys, map, filter); for anything nontrivial, prefer def for clarity.
double = lambda x: x * 2
print(double(4)) # 8
8
That lambda x: x * 2 is just a tiny anonymous function that doubles its input.
square = lambda x: x**2
square(5) # 25
names = ["Ada", "grace", "turing"]
sorted_names = sorted(names, key=lambda s: s.lower())
sorted_names
['Ada', 'grace', 'turing']
double = lambda x: x * 2
val = double(5) # 10 ← this is the lambda’s return value
print(val)
10
def power(n):
return lambda x: x ** n # returns a function
square = power(2)
cube = power(3)
print(square(4)) # 16
print(cube(2)) # 8
16
8
# Pick the student with the highest average quiz score
students = [
{"name": "Alice", "quiz": [10, 8, 9]},
{"name": "Bob", "quiz": [7, 6, 9]},
{"name": "Cara", "quiz": [9, 10, 10]},
]
top_student = max(students, key=lambda d: sum(d["quiz"]) / len(d["quiz"]))
print(top_student["name"]) # Cara
Cara
lambda d: ... creates a tiny “on-the-fly” function that computes each student’s average; max(..., key=...) uses that to decide who’s best.
Recursive functions (why they matter)#
Natural fit for self-similar problems: trees/graphs, nested folders, divide-and-conquer (binary search, mergesort, quicksort).
Clear, math-like reasoning: mirrors inductive definitions; base case + recursive step make correctness easier to argue.
Compact code for backtracking/combinatorics (paths, permutations, subsets).
Trade-offs: extra call overhead, possible stack overflows; Python has no tail-call optimization, so prefer iterative versions for deep recursions or performance-critical paths.
lambda functions (why they matter)#
Pass behavior as data: tiny anonymous functions make higher-order patterns ergonomic (
sorted(key=...),min/max(key=...),map,filter, callbacks).Concise, one-off logic without polluting the namespace with throwaway function names.
Closures: can capture surrounding variables to parameterize behavior on the fly.
Trade-offs: single-expression only; overuse can hurt readability—use
defwhen logic grows or needs documentation/tests.
Rule of thumb: use recursion when the problem is naturally recursive and depth is bounded; use lambda for short, local transformations—otherwise write a named def for clarity.
🎯 Key Takeaways
- Recursive functions call themselves with a simpler input until reaching a base case.
- Every recursion must have a base case to prevent infinite loops.
- Classic examples: Fibonacci sequence, factorial, geometric sequences.
lambdafunctions are anonymous one-line functions:lambda x: x**2.- Use
lambdawithmap(),filter(), andsorted()for concise data transformations.
—
—