## Recursion/Tree Recursion: Difficult **Solutions**

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):

**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:]))**

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