Week 4 - Tree Recursion and Lists

class: list

# welcome to discussion 4!
Announcements:
- Project 2 is due next Thursday (2/27) @ 11:59pm.
  - Submit Phase 1 by Monday 2/24.
  - Bonus submission point if turned in one day early (Wednesday)!
- No homework next week!
- Sign in: **links.cs61a.org/addison-attendance**
- Feedback: **links.cs61a.org/addison-feedback**

Schedule:
- Tree recursion
  - Count Stairways
  - Count K
- Lists / List Comprehensions
  - WWPD
  - Even Weighted
  - (Max Prod)
- Quiz

---
class: title

# tree recursion

---
class: title

# let's think about fibonacci

$$f(n) = f(n-1) + f(n-2)$$

---
class: title

# let's think about fibonacci

$$f(n) = f(n-1) + f(n-2)$$
$$f(0) = 1$$
$$f(1) = 1$$

---
class: title

# let's think about fibonacci

$$f(n) = f(n-1) + f(n-2)$$
$$f(0) = 1$$
$$f(1) = 1$$
$$1,1,2,3,5,...$$

---
class: title

# let's think about fibonacci

#![fibonacci](/assets/cs61a/tree.png)

---
class: title

# now fibonacci, in code

```python
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)
```

---
class: title

# count stairways

```python
def count_stair_ways(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    return count_stair_ways(n-1) + count_stair_ways(n-2)
```

---
class: title

# count k

```python
def count_k(n, k):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    total = 0
    i = 1
    while i <= k:
        total += count_k(n - i, k)
        i += 1
    return total
```

---
class: title

# count k - broken

```python
def count_k(n, k):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    else:
        return count_k(n-k,k) + count(n, k-1)
```

(old code below:)

---
class: title

# lists

--
They look like this:

```python
my_list = ["Addison", True, 20, None, ["another list!"]]
```

--
← a small demo!

---
class: title
# list indexing/slicing
```python
>>> fantasy_team = ['aaron rodgers', 'desean jackson']
>>> print(fantasy_team)
['aaron rodgers', 'desean jackson']
>>> fantasy_team[0]
'aaron rodgers'
>>> fantasy_team[len(fantasy_team) - 1]
'desean jackson'
>>> fantasy_team[-1]
'desean jackson'
```

--
← another demo!

---
class: title

# WWPD

← let's go over it

---
class: title

# for loops and list comprehensions

---
class: title

# even weighted

```python
[i * s[i] for i in range(len(s)) if i % 2 == 0]
```

---
class: title

# quiz