Recursion

Inductive reasoning

def mult_iter(a, b):
  result = 0
  while b > 0:
    result += a
    b -= 1
  return result

def mult(a, b):
  if b == 1:
    return a
  else:
    return a + mult(a, b-1)

• How do we know that our recursive code will work?
• mult_iter terminates because b is initially positive, and decreases by 1 each time around loop; thus must eventually become less than 1.
• mult called with b=1 has no recursive call and stops
• mult called with b>1 makes a recursive call with a smaller version of b; must eventually reach call with b=1.

Mathematical Induction

• To prove a statement indexed on integers is true for all values of n:
  • Prove it is true when n is smallest value (e.g., n=0 or n=1).
  • Then prove that if is true for an arbitrary value of n, one can show that it must be true for n+1.

Example of Induction

• 0+1+2+...+n = (n(n+1))/2
• Proof:
  • If n=0, then LHS is 0 and RHS is 0*1/2=0, so true
  • Assume true for some k, then need to show that

    0+1+2+...+k+(k+1) = ((k+1)(k+2))/2
    

  • LHS is k(k+1)/2 + (k+1) by assumption that property holds for problem of size k.
  • This becomes, by algebra, ((k+1)(k+2))/2.
• Hence expression holds for all n >= 0

Relevance to code?

def mult(a, b):
  if b == 1:
    return a
  else:
    return a + mult(a, b-1)

• Base case, we can show that mult must return correct answer
• For recursive case, we can assume that mult correctly returns an answer for problems of size smaller than b, then by the addition step, it must also return a correct answer for problem of size b.
• Thus, by induction, code correctly returns answer

Towers of Hanoi. The story

• Three tall spikes
• Stack of 64 different sized disks -- start on one spike
• Need to move stack to second spike (at which point universe ends)
• Can only move one disc at a time, and a larger disc can never cover up a small disc

• Solve a smaller problem
• Solve a basic problem
• Solve a smaller problem

def printMove(fr, to):
  print('move from ' + str(fr) + ' to ' + str(to))

def Towers(n, fr, to, spare):
  if n == 1:
    printMove(fr, to)
  else:
    Towers(n-1, fr, spare, to)
    Towers(1, fr, to, spare)
    Towers(n-1, spare, to, fr)

Showed this on pythontutor.com for n=2 and n=3

Prove inductively that the number of moves of Towers(n, ...) is 2**n-1:

• At n=1, the number of moves is 1
• At n=2, the number of moves is 1+1+1=3
• At n=3, the number of moves is 3+1+3=7
• At n=4, the number of moves is 7+1+7=7
• In general, the number of moves for input n is 2**n-1 (show by induction)