If you need help reviewing Recursion, take a look at these resources:

Each question has a "Toggle Solution" button -- click it to reveal that question's solution.

## Code-Writing Questions

### Question 1

In game theory, a *subtraction game* is a simple game with two players,
player 0 and player 1. At the beginning, there is a pile of *n*
cookies. The players alternate turns; each turn, a player can take
anywhere from 1 to 3 cookies. The player who takes the last cookie
wins. Fill in the function `can_win`

, which returns `True`

if it is
possible to win starting at the given number of cookies. It uses the
following ideas:

- if the number of cookies is negative, it is impossible to win.
- otherwise, the current player can choose to take either 1, 2, or 3 cookies.
- evaluate each action: if that action forces the opponent to lose, then return True (since we can win)
if none of the actions can force a win, then we can't guarantee a win.

`def can_win(number): """Returns True if the current player is guaranteed a win starting from the given state. It is impossible to win a game from an invalid game state. >>> can_win (-1) # invalid game state False >>> can_win (3) # take all three ! True >>> can_win (4) False """ "*** YOUR CODE HERE ***"`

```
def can_win(number):
if number <= 0:
return False
action = 1
while action <= 3:
new_state = number - action
if not can_win ( new_state ):
return True
action += 1
return False
```

## Environment Diagrams

### Question 2

```
def factorial(n):
if n == 0:
return 1
return n * factorial(n-1)
ans = factorial(2)
```

### Question 3

```
def foo(n):
i = 0
if n == 0:
return 0
result = foo(n - 2)
i += 1
return i + result
result = foo(4)
```

### Question 4

```
def bar(f):
def g(x):
if x == 1:
return f(x)
else:
return f(x) + g(x - 1)
return g
f = 4
bar(lambda x: x + f)(2)
```