Reviewing Recursion

Exercise: write a recursive function convertFromBinary that accepts an a string of that number's representation in binary (base 2) and returns the base 10 int equivalent. e.g.,

convertFromBinary("111") returns 7
convertFromBinary("1100") returns 12
convertFromBinary("101010") returns 42

# Returns the given int's binary representation. 
# Precondition: n >= 0 
def convertFromBinary(binary):
  length = len(binary)
  if length == 1:
    # base case: binary is same as base 10         
    return int(binary)
  # recursive case: break number apart 
  lastCharacter = binary[length - 1]
  beginning = binary[0:length - 1]
  return 2 * convertFromBinary(beginning) + convertFromBinary(lastCharacter)

Arm's length recursion or short-circuit recursion. Consider the following recursive implementation of power():

//Assumes exp >= 0
def power(base, exp):
  if exp == 0:
    return 1
  elif exp % 2 == 0:
    return power(base * base, exp/2) #recursive case 1
  elif:
    return base * power(base, exp - 1) #recursive case 2

Here is a short-circuit implementation of the same logic:

//Assumes exp >= 0
def power(base, exp):
  if exp == 0:
    return 1
  elif exp % 2 == 0:
    return power(base * base, exp/2) #recursive case 1
  elif:
    return base * power(base * base, (exp - 1)/2) #recursive case 2

Similarly, consider the following recursive implementation of fac():

def fac(n):
  if n <= 0:
    return 1
  else:
    return n*fac(n-1)

def facHelper(n):
  if n == 2:
    return 2
  else:
    return n*facHelper(n-1)

def fac(n):
  if n <= 1:
    return 1
  else:
    return facHelper(n)

Exhaustive search

• often implemented recursively
• sometimes called recursive enumeration

Applications

• producing all permutations of a set of values
• enumerating all possible names, passwords, etc.
• combinatorics and logic programming

Often the search space consists of many decisions, each of which has several available choices

• Example: when enumerating all 5-letter strings, each of the 5 letters is a decision and each of those decisions has 26 possible choices.

A general pseudo-code algorithm for exhaustive search:

Explore(decisions):
  -- if there are no more decisions to make: Stop

  -- else let's handle one decision ourselves, and the rest by recursion.
     For each available choice C for this decision:
     -- Choose C by modifying parameters
     -- Explore the remaining decisions that could follow C.
     -- Un-choose C by returning parameters to original state (if necessary)

Exhaustive search model.

• Choosing
  1. We generally iterate over decisions. What are we iterating over here? The iteration will be done by recursion.
  2. What are the choices for each decision? Do we need a for loop?
• Exploring
  1. How can we represent that choice? How should we modify the parameters?
     • Do we need to use a helper function due to extra parameters?
  2. Un-Choosing
     1. How do we un-modify the parameters from the "Exploring" step? Do we need to explicitly un-modify or are they copied? Are they un-modified at the same level as they were modified?
  3. Base Case
     1. What should we do in the base cases when we are out of decisions?

Exercise: printAllBinary

• Write a recursive function printAllBinary that accepts an integer number of digits and prints all binary numbers that have exactly that many digits, in ascending order, one per line.

  printAllBinary(2):
  00
  01
  10
  11
  
  printAllBinary(3):
  000
  001
  010
  011
  100
  101
  110
  111
  

• Choosing
  1. We generally iterate over decisions. What are we iterating over here? We are iterating over characters in the binary string
  2. What are the choices for each decision? Do we need a for loop? Choose 0 or 1
• Exploring
  1. How can we represent that choice? Should we modify the parameters and store our previous choices? Build up a string that will eventually print. Add the 0 or 1 (choice) to it. String tracks our previous choices.
  2. Do we need to use a helper due to extra parameters? Yes
• Un-Choosing
  1. How do we un-modify the parameters from the Exploring step? Do we need to un-modify, or are they copied? Are they un-modified at the same level as they were modified? If new strings for each call, we don't need to unchoose
• Base Case
  1. What should we do in the base case when we are out of decisions? Print the string

Solution:

def printAllBinary(numDigits):
  printAllBinaryHelper(numDigits, "")

def printAllBinaryHelper(digits, soFar):
  if digits == 0:
    print soFar
  else:
    printAllBinaryHelper(digits - 1, soFar + "0")
    printAllBinaryHelper(digits - 1, soFar + "1")

Show the balanced tree of calls for printAllBinary(2) of depth 3, showing the digits and soFar arguments for each call. This kind of diagram is called a call tree or decision tree. Think of each call as a choice or decision made by the algorithm:

• Should I choose 0 as the next digit?
• Should I choose 1 as the next digit?

printDecimal: Write a recursive function printDecimal that accepts an integer number of digits and prints all base-10 numbers that have exactly that many digits, in ascending order, one per line.

printDecimal(2):
00
01
02
03
..
..
98
99

printDecimal(3):
000
001
...
998
999

• Choosing
  1. We generally iterate over decisions. What are we iterating over here? We are iterating over characters in the binary string
  2. What are the choices for each decision? Do we need a for loop? Yes, we need a for loop
• Exploring
  1. How can we represent that choice? Should we modify the parameters and store our previous choices? Build up a string that will eventually print. Add the 0 or 1 (choice) to it. String tracks our previous choices.
  2. Do we need to use a helper due to extra parameters? Yes
• Un-Choosing
  1. How do we un-modify the parameters from the Exploring step? Do we need to un-modify, or are they copied? Are they un-modified at the same level as they were modified? If new strings for each call, we don't need to unchoose
• Base Case
  1. What should we do in the base case when we are out of decisions? Print the string

Solution:

def printDecimal(numDigits):
  printDecimalHelper(numDigits, "")

def printDecimalHelper(digits, soFar):
  if digits == 0:
    print soFar
  else:
    for i in range(10):
      printAllBinaryHelper(digits - 1, soFar + str(i))

All subsets

• Write a function allSubsets that accepts a list and prints all the subsets of the set represented by a list. Assume that the list has only unique elements.

  allSubsets([]):
  []
  
  allSubsets([1]):
  [1]
  
  allSubsets(["a", "hello"]):
  []
  ["a"]
  ["hello"]
  ["a", "hello"]
  

Solution:

def allSubsets(s):
  allSubsetsHelper(s, [])

def allSubsetsHelper(remaining, curChoices):
  if len(remaining) == 0:
    print curChoices
  else:
    remainingCopy = remaining[:]
    decisionOn = remainingCopy.pop()
    allSubsetsHelper(remainingCopy, curChoices)
    allSubsetsHelper(remainingCopy, [decisionOn] + curChoices)

allSubsets([1,2])

Why do we need to clone the list: remainingCopy = remaining[:]. Consider an implementation where we replace this cloning operation by a simple assignment that creates aliases: remainingCopy = remaining. Now consider the function activation allSubsetsHelper([1,2], []) which will in turn call allSubsetsHelper([1], []) which will in turn pop the list associated with remainingCopy. So, the second call from allSubsetsHelper([1,2], []) will now be to allSubsetsHelper([], [2]) (instead of the expected allSubsetsHelper([1], [2]). Thus, this program prints [0], [1], [2], instead of the desired [0], [1], [2], [1,2].

Instead of copying, we could alternatively, modify and unmodify the input parameter as follows:

def allSubsets(s):
  allSubsetsHelper(s, [])

def allSubsetsHelper(remaining, curChoices):
  if len(remaining) == 0:
    print curChoices
  else:
    decisionOn = remaining.pop()  #modify
    allSubsetsHelper(remaining, curChoices)
    allSubsetsHelper(remaining, [decisionOn] + curChoices)
    remaining.append(decisionOn)  #unmodify

allSubsets([1,2])