Day 2 – Functions & Recursion (Python Problem-

Solving Sprint)
Goal for Today: Understand how to break problems into reusable pieces (functions) and how a function
can call itself (recursion) to solve problems defined in terms of smaller versions of the same problem.

Keep things simple. Think like this: If I can solve a tiny version, can I build the big answer
from it?

0. Quick Day 1 Wrap-Up (Self-Check)

Before starting Day 2, confirm you’re solid on loops & conditionals:

• ✅ Can you print numbers 1–100? Even numbers only? Reverse order?
• ✅ Can you loop through a string and apply logic (like counting vowels)?
• ✅ Can you scan a list and keep track of a running min/max?
• ✅ Did you complete at least 5 Python warmup problems on HackerRank (or similar)?

If any of these feel shaky, do 10-minute review now: rewrite one loop, one if-else, one list scan.

1. Why Functions?
Functions let you give a name to a chunk of work. You can reuse it. It makes big problems smaller.

Basic Syntax

def add(a, b):

return a + b

result = add(2, 3) # 5

Tips

• Use verbs for function names: count_vowels , max_in_list .

• Use return (don’t just print) when you want to reuse a result.
• Use docstrings to remind future-you what the function does.

def count_vowels(s: str) -> int:

"""Return number of vowels in string s."""
count = 0
for ch in s.lower():
if ch in "aeiou":

1
 count += 1
return count

2. What Is Recursion?
A function that calls itself.

Key idea: Each call handles a smaller piece until we hit a base case (the simplest input we already know
the answer for).

Recursion Mental Model (Ladder Story)

Imagine you want to climb n steps.

• If n == 0 , you’re already there. Done. (Base case.)

• Otherwise: take 1 step, then ask a helper (same problem, but n-1 ) to finish the rest. (Recursive
step.)

This “do a tiny bit → let recursion handle the smaller problem” pattern is everywhere.

3. The 3 Parts of Any Recursive Function

Part Question to Ask Example (Factorial)

Base Case When can I stop? if n == 0: return 1

Smaller Sub-Problem What’s the smaller input? fact(n-1)

Build Answer How do I use smaller result to solve big one? return n * fact(n-1)

If you can write those 3 lines, you can write most recursive functions.

4. Tracing Recursion (Very Important!)

Let’s trace fact(3) :

fact(3) → 3 * fact(2)
fact(2) → 2 * fact(1)
fact(1) → 1 * fact(0)
fact(0) → 1 (base)
Back up:
fact(1) = 1 * 1 = 1
fact(2) = 2 * 1 = 2
fact(3) = 3 * 2 = 6

2
Draw this on paper when stuck.

5. Core Practice Problems for Day 2

We’ll do: Factorial, Fibonacci, Power (x^n).

5.1 Factorial (n!)

Definition: n! = n * (n-1) * (n-2) * ... * 1 , and 0! = 1 .

Recursive version:

def factorial(n: int) -> int:

if n < 0:
raise ValueError("n must be >= 0")
if n == 0 or n == 1: # base
return 1
return n * factorial(n - 1)

Iterative check: Good to confirm your recursive result.

5.2 Fibonacci (recursive)

Sequence: 0, 1, 1, 2, 3, 5, 8, ...

Definition:

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n-1) + fib(n-2) for n ≥ 2

def fib(n: int) -> int:

if n < 0:
raise ValueError("n must be >= 0")
if n < 2: # when n is 0 or 1
return n
return fib(n-1) + fib(n-2)

⚠️ Very slow for big n . We'll fix this with memoization on Day 8 (DP).

5.3 Power of a Number (x^n)

We want pow(x, n) .

3
Naive idea: multiply x by itself n times. Recursive idea:

• Base: n == 0 → return 1
• Smaller: pow(x, n-1)
• Build: x * pow(x, n-1)

def power(x: float, n: int) -> float:

if n == 0:
return 1
if n < 0: # x^-n = 1 / (x^n)
return 1 / power(x, -n)
return x * power(x, n-1)

Fast Power (Optional Stretch): Divide-and-conquer.

• If n even: x^n = (x^(n//2))^2

• If n odd: x^n = x * x^(n-1)

def fast_power(x: float, n: int) -> float:

if n == 0:
return 1
if n < 0:
return 1 / fast_power(x, -n)
half = fast_power(x, n // 2)
if n % 2 == 0:
return half * half
else:
return x * half * half

6. Mini Recursion Drills (Short, Fun)

Do these on paper before coding:

1. Sum of digits of a number: sum_digits(1234) = 1+2+3+4 = 10 .

2. Reverse a string recursively.
3. Count how many times a target appears in a list recursively.

If you can say the 3 parts (base, smaller, build), you’re golden.

7. Debug Patterns for Recursion Bugs

Symptom Likely Cause Fix

Maximum recursion depth

Missing/incorrect base case Add/stop earlier
error

4
 Symptom Likely Cause Fix

Shrinking wrong: n-2 instead of

Wrong answer off by 1 Re-check smaller step
n-1

Ensure progress toward

Infinite recursion Argument never changes
base

Slow Recomputing same subproblems Use memoization (Day 8)

Add print tracing when stuck:

def factorial(n):
print("enter", n)
if n <= 1:
print("base", n)
return 1
ans = n * factorial(n-1)
print("return", n, ans)
return ans

8. Practice Block (Your Turn)

Complete these in order. Time-box each to stay focused.

Block A (Core – do these first)

Block B (Stretch)

Block C (Challenge)

9. Sample Tests You Can Use

Copy-paste into a scratch file to test your functions:

print("factorial tests")
for n in range(6):
print(n, factorial(n))

print("fib tests")

5
 for n in range(10):
print(n, fib(n))

print("power tests")
print(power(2, 10)) # 1024
print(power(2, -3)) # 0.125
print(power(5, 0)) # 1

print("fast_power tests")
print(fast_power(2, 10))
print(fast_power(2, -3))
print(fast_power(3, 5))

10. Suggested Timeline (Total \~2.5 hrs, adjust as needed)

Block Time Task

0 10m Review Day 1 mini drills

1 20m Learn & trace factorial, fib, power

2 40m Code Block A + self-tests

3 20m Stretch: fast power + one mini drill

4 15m Break (walk, water)

5 30m Debug & compare recursive vs loop versions

6 15m Quick quiz + notes summary

Adjust around your energy; shorter bursts are fine.

11. Reflection Questions (Write Short Answers)

1. What is a base case? Why do we need it?
2. How does fib(n-1) + fib(n-2) grow in calls? (Hint: Tree.)
3. When is recursion clearer than loops? When is it slower?
4. Can every recursion be rewritten as a loop? (Usually yes, but sometimes messy.)

12. Save Your Learning Snapshot

At end of Day 2, write 5 bullet points in your notebook:

• What recursion means to you in simple words.

• One bug you hit.
• One trick that helped you debug.
• Which problem felt easiest? Hardest?

6
 • One question for future-you (carry to Day 3: Backtracking!).

✅ End-of-Day-2 Checklist

If 3+ checks = move to Day 3 tomorrow. If not, repeat Block A tomorrow morning as warm-up.

Next Up (Day 3 Preview): Backtracking! We’ll use recursion to explore choices (like trying letters,
chessboard moves, or paths in a maze), and undo when things don’t work.

Let me know when you finish the Core Block or if you want live practice / code review. I’m here! 💪🐍