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
    if num1 < num2:
        return 0
    elif num1 == 0:
        return 1
    else:
        return digit_sum(num1 // 10, num2 - num1 % 10) + digit_sum(num1 // 10, num2)

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
    if x >= len(grid) or y >= len(grid):
        return 0
    else:
        return grid[x][y] + max(max_sum(grid, x + 1, y), max_sum(grid, x, y + 1))

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
    if len(seq) == 1:
        return seq[0]
    else:
        return max(seq[0] + largest_sum(seq[2:]), largest_sum(seq[1:]))

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
    def game_helper(cards, score, opponent_score):
        if len(cards) == 0:
            return score
        elif len(cards) == 1:
            return score + cards[0]
        else:
            choose_left = game_helper(opponent_choice(cards[1:]), score + cards[0], opponent_score + max(cards[1], cards[len(cards) - 1]))
            choose_right = game_helper(opponent_choice(cards[:len(cards) - 1]), score + cards[len(cards) - 1], opponent_score + max(cards[0], cards[len(cards) - 2]))
            return max(choose_left, choose_right)
    def opponent_choice(cards):
        if cards[0] > cards[len(cards) - 1]:
            return cards[1:]
        else:
            return cards[:len(cards) - 1]
    return game_helper(cards, 0, 0)
If you didn't get this, don't feel bad, I designed this to be a really hard question, probably harder than any tree recursion problem you'll see in 61A. The trick to this question is recognizing that you have to do 2 turns each step: yours and your opponent's. You have to do both turns because your opponent is using a fixed strategy that is not looking at anything other than the two end cards, and if you do something like game_helper(cards[1:], opponent_score, score + cards[0]), where you flip opponent_score and score, you will be applying the recursive strategy to your opponent's score, and they may end up picking a card that is not the max of the two end cards. You know how your opponent is going to pick once you've chosen a card (max of the two ends once your card has been removed), so you can just run their turn after yours and before making the next recursive call.