Recursion Practice Problems

Important! These are all exam-level problems. Do not attempt these problems without a solid foundation in the subject and use them for exam practice.

1. Fill in the lines below for the function subset_sum which takes in a list and a desired number and tries to find a subset of the list that adds to the desired number. If there exists such subset, return the first subset that does so, otherwise, return ‘NOPE’.

def subsetsum(array,num): 
    """Return the first subset of array that adds to num, or 'NOPE' if none exist. 
    >>>subsetsum([1,3,5,7], 9).sorted()
    [1,3,5]
    >>>subsetsum([1,3,5,7], 2)
    'NOPE'    
    """ 
    if num < 0: 
      return ‘NOPE’ 
    elif len(array) == 0: 
      return ‘NOPE’
    else: 
      if array[0] == num: 
        return [array[0]] 
      else: 
        with_v = subsetsum(array[1:],(num - array[0])) 
        if with_v != ‘NOPE’: 
          return [array[0]] + with_v 
        else: 
          return subsetsum(array[1:],num)

def subsetsum(array,num): 
    """Return the first subset of array that adds to num, or 'NOPE' if none exist. 
    >>>subsetsum([1,3,5,7], 9).sorted()
    [1,3,5]
    >>>subsetsum([1,3,5,7], 2)
    'NOPE'    
    """ 
    if _____ < 0: 
      return ______ 
    elif _______ == 0: 
      return ______
    else: 
      if array[0] == num: 
        return ________
      else: 
        with_v = ________________
        if with_v != _______: 
          return _____________ 
        else: 
          return __________

Toggle Solution

2. Mario needs to jump over a sequence of Piranha plants, represented as a string of dashes (no plant) and P's (plant!). He only moves forward, and he can either step (move forward one space) or jump (move forward two spaces) from each position. How many different ways can Mario traverse a level without stepping or jumping into a Piranha plant? Assume that every level begins with a dash (where Mario starts) and ends with a dash (where Mario must end up)

def mario_number(level):
    """Return the number of ways that Mario can perform a sequence of steps or jumps to reach the end of the level without ever landing in a Piranha plant. Assume that every level begins and ends with a dash.
    >>> mario_number('-P-P-')   # jump, jump
    1
    >>> mario_number('-P-P--')   # jump, jump, step
    1
    >>> mario_number('--P-P-')  # step, jump, jump
    1
    >>> mario_number('---P-P-') # step, step, jump, jump or jump, jump, jump
    2
    >>> mario_number('-P-PP-')  # Mario cannot jump two plants
    0
    >>> mario_number('----')    # step, jump ; jump, step ; step, step, step
    3
    >>> mario_number('----P----')
    9
    >>> mario_number('---P----P-P---P--P-P----P-----P-')
    180
    """
    if len(level) == 0 or level[0] == 'P':
        return 0
    elif len(level) <= 2:
        return 1
    else:
        return mario_number(level[1:]) + mario_number(level[2:])

def mario_number(level):
    """Return the number of ways that Mario can perform a sequence of steps or jumps to reach the end of the level without ever landing in a Piranha plant. Assume that every level begins and ends with a dash.
    >>> mario_number('-P-P-')   # jump, jump
    1
    >>> mario_number('-P-P--')   # jump, jump, step
    1
    >>> mario_number('--P-P-')  # step, jump, jump
    1
    >>> mario_number('---P-P-') # step, step, jump, jump or jump, jump, jump
    2
    >>> mario_number('-P-PP-')  # Mario cannot jump two plants
    0
    >>> mario_number('----')    # step, jump ; jump, step ; step, step, step
    3
    >>> mario_number('----P----')
    9
    >>> mario_number('---P----P-P---P--P-P----P-----P-')
    180
    """
    "YOUR CODE HERE"

Toggle Solution