Reviewing Recursion

Recursive blue shirt

• We want to count the number of people in the room who are wearing a blue shirt
• We can't directly count (there are a lot of people in the room)
• But all of you can help
• You can ask questions of the person behind you and respond to the questions of the person in front of you

The first person looks behind them:

• If there is no one there, the person responds with 1 if he/she is wearing a blue shirt or 0 if he/she is not.
• If there is someone behind the person, ask them how many people behind them (including the answerer) are wearing a blue shirt (recursive call)
• Once the person receives a response, they add 1 if he/she is wearing a blue shirt, or 0 if he/she is not, and respond to the person in front of them.
• Now I (the instructor) needs to ask everyone in the front row --- much simpler!

Recursion and cases: Every recursive algorithm involves at least two cases:

• base case: A simple occurrence that can be answered directly.
• recursive case: A more complex occurrence of the problem that cannot be directly answered, but can be instead described in terms of smaller occurrences of the same problem

Key idea: In a recursive piece of code, you handle a small part of the overall task yourself (usually the work involves modifying the results of the smaller problems), then make a recursive call to handle the rest.

Ask yourself, "how is ths task self-similar?"

• "How can I describe this algorithm in terms of a smaller or simpler version of itself?"

Recursion Tips

• Look for self-similarity
• Find the minimum amount of work
• Make the problem simpler by doing the least amount of work possible.
• Trust the recursion
• Find a stopping point (base case)

Three rules of recursion

• Every (valid) input must have a case (either recursive or base)
• There must be a base case that makes not recursive calls, i.e., on some input(s), the code should not make any recursive calls
• The recursive case must make the problem simpler and make forward progress to the base case. e.g., if the person behind you asks the person in front of him/her, that is not going to make progress

Recursive Program structure

def recursiveFunc(...):
  if (test for simple case): # base case 
    # Compute the solution without recursion 
  else:  # recursive case
    # 1. Break the problem into  subproblems of the same form 
    # 2. Call  recursiveFunc() on each  self-similar  subproblem
    # 3. Reassamble the results of the subproblems

Recursion with multiple base cases

• Fibonacci numbers
  • Leonardo of Pisa (aka Fibonacci) modeled the following challenge
    • Newborn pair of rabbits (one female, one male) are put in a pen
    • Rabbits mate at age of one month
    • Rabbits have a one month gestation period
    • Assume rabbits never die, that female always produces one new pair (one male, one female) every month from its second month on.
    • How many female rabbits are there at the end of one year?

Let's work out the numbers:

• After one month (call it 0): 1 female
• After second month --- still one female (now pregnant)
• After third month --- two females, one pregnant, one not
• In general: females(n) = females(n-1)+females(n-2):
  • Every female alive at month n-2 will produce one female in month n.
  • These can be added to those alive in month n-1 to get total alive in month n.

Fibonacci

• Base cases:
  • females(0) = 1
  • females(1) = 1
• Recursive case:
  • females(n) = females(n-1) + females(n-2)

def fib(x):
  """assume x an int >= 0
     returns Fibonacci of x"""
  if x == 0 or x == 1:
    return 1
  else:
    return fib(x-1) + fib(x-2)

Recursion on Non-Numerics

• how to check if a string of characters is a palindrome, i.e., reads the same forwards and backwards
  • "Able was I, ere I saw Elba" --- attributed to Napoleon
  • "Are we not drawn onward, we few, drawn onward to new era? --- attributed to Anne Michaels

• First, convert the string to just characters, by stripping out punctuation, and converting upper case to lower case
• Then
  • Base case: a string of length 0 or 1 is a palindrome
  • Recursive case:
    • If first character matches last character, then is a palindrome if middle section is a palindrome

Example

• "Able was I, ere I saw Elba" --> "ablewasiereisawelba"
• isPalindrome("ablewasiereisawleba") is same as:
  • "a" == "a" and isPalindrome("blewasiereisawelb").

def isPalindrome(s):
  def toChars(s):
    s = s.lower()
    ans = ''
    for c in s:
      if c in 'abcdefghijklmnopqrstuvwxyz':
        ans = ans + c
    return ans

  def isPal(s):
    if len(s) <= 1:
      return True
    else:
      return s[0] == s[-1] and isPal(s[1:-1])

  return isPal(toChars(s))

• Solve a hard problem by breaking it into a set of subproblems such that:
  • subproblems are easier to solve than the original
  • solutions of the subproblems can be combined to solve the original

Exercise: Write a function power that accepts integer parameters for a base and exponent and computes base ^ exponent.

• First write code using for-loop
• Now write a recursive version of this function (one that calls itself)
• Solve the problem without using any loops.

Method:

• How is the problem self-similar? x^n = x * x^(n-1)
• What is the minimum amount of work? multiplication
• How can we make the problem simpler by doing the least amount of work?
• What is our stopping point (base case)? n = 0. Why not n=1?

//Assumes exp >= 0
def power(base, exp):
  if exp == 0:
    return 1
  else:
    return base * power(base, exp - 1)

Can we do better? Notice that x^18 = (x*x)^9; x^9=x*x^8

//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