## Recursion/Tree Recursion: Difficult

### Code Writing

Write a recursive function that takes in two numbers and counts the number of sets of some or all of the digits of the first number that can be added up to make the second number.

def digit_sum(num1, num2):

>>> digit_sum(4422, 8)

3

Write a recursive function that takes in a grid (a list of lists), **grid**, of numbers, an current x index, **x**, and a current y index **y**, and finds the maximum sum that can be attained by starting in position (**x**, **y**) and moving only down and right. Hint: Only attempt this problem if you have learned about lists.

def max_sum(grid, x, y):

>>> grid = [[1, 2, 3],

[4, 5, 6],

[7, 8, 9]]

>>> max_sum(grid, 0, 0)

29

Write a recursive function that takes in a list of numbers, **seq**, and returns the largest sum that can be made from numbers in the sequence where no two numbers selected for the sum are adjacent to each other. Hint: Only attempt this problem if you have learned about lists.

def largest_sum(seq):

>>> largest_sum([10, 1, 2, 3, 1, 4])

17

You are playing a card game with a friend, and of course, you want to win. In the game, you have an ordering of uniquely valued cards, represented by the list **cards**. Each turn, you have the option to pick the rightmost card or the leftmost card. Your friend is convinced that the best strategy is to pick the end card with the largest value each time. However, this is not actually the best strategy: think of the example [2, 1, 7, 3]. If you pick 3, the larger of the two end cards, your opponent can pick 7 and win the game, but if you pick 2, then they will pick either 3 or 1, which will allow you to pick 7 and win.

As a 61A student, you've learned recursion, and so you think that you can come up with a better strategy using recursion. Write a recursive function that figures out maximum score you can get by playing optimally, assuming that you know your friend is using the above strategy, and that you are going first.

Hint 1: Only do this question if you have learned about lists.

Hint 2: To solve this problem, I created multiple helper functions.

def game(cards):

>>> game([2, 1, 7, 3])

9