Ch.2: Recursion

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/19

encourage image

There's no tags or description

Looks like no tags are added yet.

20 Terms

1
New cards
[Recursion] Recursive function
A function that calls itself, each time on a smaller version of the same problem, until the problem is small enough to answer directly.
2
New cards
[Recursion] Base case
The simplest input, answered directly with no further calls. It is what stops the recursion.
3
New cards
[Recursion] Recursive case
Every other input: do a small piece of work, then call the function on a smaller version of the problem.
4
New cards
[Recursion] The two things to check when a recursive function doesn't work
1) Does the base case actually stop the function? 2) Does each recursive call work on a smaller piece than the one before it?
5
New cards
[Recursion] Call stack
Python's record of all the paused function calls waiting for their recursive calls to finish.
```python
def countdown(n):
if n == 0:
print("base case")
return
print("calling", n)
countdown(n - 1)
print("returning", n)

countdown(2) # → calling 2, then calling 1, then base case, then returning 1, then returning 2
```
6
New cards
[Recursion] What happens if a recursive function has no reachable base case?
It calls itself until Python's recursion limit (about 1000 calls) is hit and raises a RecursionError.
```python
def forever(n):
return forever(n + 1) # no base case!

try:
forever(0)
except RecursionError:
print("RecursionError") # → RecursionError
```
7
New cards
[Recursion] factorial(5): what calls happen, step by step?
factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1), which hits the base case and returns 1. Then the paused calls finish back up: 2·1 = 2, 3·2 = 6, 4·6 = 24, 5·24 = 120.
8
New cards
[Recursion] list_sum(nums): what is the idea?
Base case: an empty list sums to 0. Otherwise: the first item plus the sum of the rest, `nums[0] + list_sum(nums[1:])`.
9
New cards
[Recursion] Predict: what does list_sum([5, 10, 15]) return, and what calls does it make?
30. Calls: list_sum([5, 10, 15]) → list_sum([10, 15]) → list_sum([15]) → list_sum([]) returns 0. Then 15 + 0, 10 + 15, 5 + 25 = 30.
10
New cards
[Recursion] Why does slicing like `nums[1:]` make recursion slower?
Each slice copies the rest of the list, O(n) per call. Over n calls that adds up to O(n²). Passing an index instead avoids the copying.
```python
def list_sum_fast(nums, i=0):
if i == len(nums): # base case: past the end
return 0
return nums[i] + list_sum_fast(nums, i + 1) # no copying

print(list_sum_fast([5, 10, 15])) # → 30
```
11
New cards
[Recursion] Recursion vs. iteration
Any recursive function can be rewritten as a loop. Recursion is the natural fit for self-similar structures like trees.
```python
def factorial_loop(n):
result = 1
for i in range(2, n + 1):
result *= i
return result

print(factorial_loop(5)) # → 120 ← same answer as the recursive version
```
12
New cards
[Recursion] Runtime of naive recursive Fibonacci
O(2ⁿ), because each call makes two more calls. (This is Recursive Pattern 3 in Chapter 3.)
```python
calls = 0

def fib(n):
global calls
calls += 1
return n if n < 2 else fib(n - 1) + fib(n - 2)

fib(20)
print(calls) # → 21891 ← over 21,000 calls for n = 20
```
13
New cards
[Recursion] Code: Write factorial(n) recursively.
```python
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case
```
14
New cards
[Recursion] Code: Write list_sum(nums) recursively.
```python
def list_sum(nums):
if len(nums) == 0: # base case: empty list sums to 0
return 0
return nums[0] + list_sum(nums[1:]) # first item + sum of the rest
```
15
New cards
[Recursion] Code: Write power(base, exp) recursively.
```python
def power(base, exp):
if exp == 0: # base case
return 1
return base * power(base, exp - 1)
```
16
New cards
[Recursion] Code: Write count_down(n) that prints n, n-1, ..., 1, then "liftoff!", recursively.
```python
def count_down(n):
if n == 0:
print("liftoff!")
return
print(n)
count_down(n - 1)
```
17
New cards
[Recursion] Code: Write reverse_string(s) recursively.
```python
def reverse_string(s):
if len(s) <= 1: # base case
return s
return reverse_string(s[1:]) + s[0]
```
18
New cards
[Recursion] Code: Write fibonacci(n) recursively.
```python
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
```
19
New cards
[Recursion] Code: Write count_matches(nums, target) recursively.
```python
def count_matches(nums, target):
if not nums: # base case: empty list
return 0
first = 1 if nums[0] == target else 0
return first + count_matches(nums[1:], target)
```
20
New cards
[Recursion] Recursion: what does "trust the recursion" mean?
Once the base case works and each call gets smaller, assume the recursive call returns the right answer for the smaller problem. You don't need to trace every call by ha