Previous Lecture Lec16 Next Lecture

Lec16, Wed 02/26

Recursion is Recursion

Reading

Recursion

The simplest case is called the Base case: There is nothing to do.

Example: Doing dishes

Each recursive case should get you closer to the base case.

def doDishes(numDishes):
    if numDishes == 0:
        # return "You're done!"
    else:
        # wash one dish
        # remove it from the sink
        # return doDishes(numDishes - 1)

(* Assume numDishes is a non-negative integer)

See slides for additional examples of recursion (e.g., Droste Effect, Sierpinski triangle).

Solving recursion

When designing a recursive solution, we need to answer the following questions:

A skeleton of the recursive function

# Note, this is just a pseudocode skeleton structure
def recF(input): 
   if input ...
      print/return # base case / cases 
   else / elif
      print/return recF( input => base case ) 

# => stands for "that gets you closer to"
# so, the recursive case is supposed to use
# the input that gets you closer to the base case

The classic examples: Fibonacci and Factorials

Factorial

Factorial represents the number of permutations (combinations) of arranging a set of n items.

n n! Resulting combinations of n items
1 1  {1}
2 2  {1,2}, {2,1}
3 6  {1,2,3}, {1,3,2}, 
     {2,1,3}, {2,3,1},
     {3,1,2}, {3,2,1}

In other words…

• 0! = 1 # An empty set can only be ordered one way, so 0! = 1
• 1! = 1
• 2! = 2∙1=2
• 3! = 3∙2∙1=6
• 4! = 4∙3∙2∙1 = 24

Looks like we have a formula:
n! = n∙(n – 1)!

So, for any given n, to compute the factorial of n, we need to find the product of the successive numbers between 1 and n.

Let’s try expressing this in Python.

But first, we need to answer:

If we correctly answer these questions, we would have the pseudocode / algorithm for the solution:

Let’s check if the above logic works for the next recursive case, which is 3!.

And now in Python:

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

Now, the call of factorial(3) results in the following call stack (similar to the steps we traced above):

factorial(3)
  3 * factorial(3-1)
      2 * factorial(2-1)
          1 * factorial(1-1)
              1

Note: if we forget to include the return inside the recursive case, then the function will return nothing, which means the return value will be None.

Checking for invalid input

>>> factorial("two")
...
    return n * factorial(n-1)
TypeError: unsupported operand type(s) for -: 'str' and 'int'

The TypeError points at the fact that we cannot use a subtraction between str' and 'int'.

>>> factorial(2.1)
  ...
    return n * factorial(n-1)
  [Previous line repeated 1021 more times]
  File "/....py", line 2, in factorial
    if n==0:
RecursionError: maximum recursion depth exceeded in comparison

2.1 - (1 * any integer) will never equal 0. The base case will never be reached, so there will be an infinite recursion. Python cannot handle an infinite recursion, so it will produce an error: RecursionError: maximum recursion depth exceeded in comparison. This is the error that you’ll see if your function never reaches the base case.

Writing helper functions

However, we should not check if we got the correct input within the recursive function, because the code of the recursive function runs every time that function is called. Instead, we want to check the input once, to decide if it is safe call the recursive function. In this case, the recursive function will be the helper function.

Let’s create a new function getFactorial(n) that calls factorial(n) if and only if the user inputs a valid value of the valid type.

Below is one potential version with a very generic error.

# One potential version
def getFactorial(n):
    '''
    Check that n is >= 0
    and is an integer.
    If it is not, print an Error,
    Otherwise, return the value n!
    '''

    if type(n) == int and n >= 0:
      return factorial(n)
    else:
      print("Error")

Here’s another potential version with the two check separated using if / elif:

def getFactorial(n):
    '''
    check that n is an integer>=0
    return n!
    Otherwise, print an error
    '''
    if type(n) != int:
        print("Error: incorrect type")
    elif n < 0:
        print("Error: incorrect value", n)
    else:
        return factorial(n)

def getFactorial(n):
    '''
    check that n is an integer>=0
    return n!
    Otherwise, print an error
    '''
    if type(n) != int:
        print("Error: incorrect type")
        return
    if n < 0:
        print("Error: incorrect value", n)
        return
    else:
        return factorial(n)

Note: if we forget to include the return inside the recursive case, then the function will return nothing, which means the return value will be None.

>>> getFactorial(2)
>>> num = getFactorial(2)
>>> print(num)
None

Once we add the return, we can correctly check if the function correctly handles it if the user inputs -2.1.

>>> getFactorial(2)
2
>>> getFactorial(4)
24
>>> getFactorial(2.1)
Error: incorrect type
>>> getFactorial(-2)
Error: incorrect value -2
>>> getFactorial("two")
Error: incorrect type

We can also get very descriptive and output the incorrect type and the value of the provided input.

# new function
def getFactorial(n):
   '''
   check that n is an integer>=0
   return n!
   Otherwise, print an error
   '''
   if type(n) != int
      print ("Error: incorrect input type", type(m))
      return
   if n < 0:
      print("Error: incorrect input value", n)
      #return # see what happens if there's no return
   else: # n is a valid input
      return factorial(n)

Fibonacci numbers

A Fibonacci number is a number in a sequence of numbers (the Fibonacci sequence), such that each number is the sum of the two preceding ones. The Wikipedia article has a lot of fascinating information about the Fibonacci numbers (did you know that they are related to the golden ratio?). Sometimes, you see the Fibonacci sequence starting from 0 and 1. In lecture, we started them at 1 and 1.

def fibonacci(n):
    '''
    returns the nth fibonacci term
    '''
    if n == 1:
        return 1
    if n == 2:
        return 1
    if n == 3:
        return fibonacci(1) + fibonacci(2)
    if n == 4:
        return fibonacci(2) + fibonacci(3)
    if n == 5:
        return fibonacci(3) + fibonacci(4)

        ...

    # How do we generalize this?

We can generalize this like so:

def fibonacci(n):
    '''
    returns the nth fibonacci term
    '''
    if n == 1:
        return 1
    if n == 2:
        return 1
    else:
        return fibonacci(n - 2) + fibonacci(n - 1)

Recursion in CS 16 and beyond

If you continue taking CS classes, you’ll see recursion again in CS 16 and beyond: