CS 111 Lecture: More Fruitful Recursion

Table of Content

  1. Fruitful spiraling: spiralLength
  2. Exercise 1: spiralCount
  3. Exercise 2: spiralTuple
  4. Exercise 3: Fruitful trees - branchCount
  5. Fruitful Recursion with lists
  6. Generate countDownListPrintResults
  7. Exercise 4: countUpList
  8. Sublists
  9. The sublistSum function
  10. Alternative approach to sublistSum
  11. Exercise 5: sublists
  12. Extra: Fibonacci numbers
  13. Exercise 6: fibRec
  14. Exercise 7: fibLoop

1. Fruitful spiraling: spiralLength

First some housekeeping function to setup the turtle drawing:

The function spiralLength below modifies the function spiralBack that we covered in the previous lecture so that it returns the total length of lines in the spiral.

Invoke the function:

2. Exercise 1: spiralCount

Below we have copied spiralLength and modified it to be named spiralCount. The goal is to specify what should go in the return statements, so that the function returns the number of lines in the spiral.

Invoke the function:

Exercise 2: spiralTuple

Now, copy below your working version of spiralLength and modify it to be a function spiralTuple that returns a pair (i.e., a 2-tuple) of:

Invoke the function:

4. Exercise 3: Fruitful trees - branchCount

Similarly to the modifications that we did to functions that draw spirals, we can modify the function that draws trees to become a fruitful function, to count the number of branches that are drawn.

Below is the original tree function for drawing a tree:

Copy and modify the solution of tree so that it becomes branchCount, which in addition to drawing the tree also returns the number of all branches in the tree.

Note: Don't forget to change the function name in the recursive calls from tree to branchCount when you paste the solution in the cell below.

Let's draw a small tree with level 3:

Let's draw a bigger tree with level 7:

5. Recursion with lists

We have seen recursion in the context of printing and adding numbers with countUp and sumUp, respectively. Here is a function that creates a list of numbers from n to 1.

6. Exercice 4: countDownListPrintResults

Modify countDownList to be the function countDownListPrintResults that prints out the list returned by each recursive call. For example:

In[]: countDownListPrintResults(5)
[]
[1]
[2, 1]
[3, 2, 1]
[4, 3, 2, 1]
[5, 4, 3, 2, 1]
Out[]:
[5, 4, 3, 2, 1]

7. Exercise 5: countUpList

Write a new function countUpList, which returns a list of integers from 1 up to n. You will only need to change one thing in countDownList to get countUpList.

8. Sublists

For a given list L (possibly containing duplicates), we will use the term sublist of L to refer to any list that keeps some elements of L and omits others in their same relative order. E.g., the sublists of [5, 3, 8, 3] are:

[5, 3, 8, 3] # Keep all elements
[3, 8, 3] # Omit 5
[5, 8, 3] # Omit 1st 3
[5, 3, 3] # Omit 8
[5, 3, 8] # Omit 2nd 3
[8, 3] # Omit 5 and 1st 3
[3, 3] # Omit 5 and 8
[3, 8] # Omit 5 and 2nd 3
[5, 3] # Omit 8 and 1st 3
[5, 3] # Omit 8 and 2nd 3  # (Note duplication)
[5, 8] # Omit both 3s
[5] # Keep only 5
[3] # Keep only 1st 3
[8] # Keep only 8
[3] # Keep only 2nd 3      # (Note duplication)
[] # Omit all elements

In the following we will look at a few different examples using sublists. You will also write your own function to create all sublists of a list, recursively.

9. The sublistSum function

Given a list of numbers (possibly containing duplicates) and a target number, sublistSum returns a list of all sublists whose sum is the target number. For example:

sublistSum([2, 3, 5, 5, 11, 17], 23) --> [[2, 5, 5, 11]]  
sublistSum([2, 3, 5, 5, 11, 17], 30) --> [[2, 11, 17], [3, 5, 5, 17]] 
sublistSum([2, 3, 5, 5, 11, 17], 24) --> [[2, 5, 17], [2, 5, 17], [3, 5, 5, 11]] 
sublistSum([2, 3, 5, 5, 11, 17], 34) --> []

Note: More details about these results and how sublistSum works are given in the lecture slides.

To test the function, we will write a helper function:

Now we can call the testSublistSum many times to test sublistSum:

10. Alternative approach to sublistSum

Suppose we had a sublists function that returns all sublists of a list. E.g.:

sublists([5, 3, 5, 8]) 
-->  [[5, 3, 5, 8], [5, 3, 5], [5, 3, 8], [5, 3], 
      [5, 5, 8], [5, 5], [5, 8], [5], 
      [3, 5, 8], [3, 5], [3, 8], [3], 
      [5, 8], [5], [8], []]

Then we could define sublistSum as:

def sublistSum(nums, target):
    """Alternative implemenation of sublistSum using the recursive
    function sublists and list comprehension.
    """
    return [ns for ns in sublists(nums) if sum(ns) == target]

In the next exercise, you'll help complete the definition of sublists and then test this new solutions for sublistSum.

11. Exercise 5: sublists

You are given the almost complete body of the function sublists. Your task is to fill in the skeleton of the function that is provided in Slide 19 of today's lecture.

Let's invoke the function a couple of times with different lists:

We can now test the alternative sublistSum as well, but first let's put here its definition:

Here are some tests:

12. Fibonacci numbers

Fibonacci numbers model the number of pairs of rabbits in a given month, assuming:

  1. rabbits never die;
  2. sexually mature rabbits produce a new rabbit pair every month; and
  3. rabbits become sexually mature after one month.

This leads to the following recursive formula for the nth Fibonacci number fib(n):

fib(0) = 0 ; no pairs initially
fib(1) = 1 ; 1 pair introduced the first month
fib(n) = fib(n-1) ; pairs never die, so live to next month
         + fib(n-2) ; all sexually mature pairs produce a pair each month

Below you will first write a recursive implementation of the Fibonacci numbers and then an iterative one.

13. Exercise 6: fibRec

Turn into Python code the recursive formula provided above:

13.1 Inefficency of Fibonacci recursion

How long does it take to calculate fibRec(n)? Let's look at the time (in seconds) to calculate some values.

Let's test the function by trying to find the 5th, 10th, 15th, ..., up to the 35th number in the Fibonacci sequence:

Exercise 7: fibLoop

Here is an iterative way to view Fibonacci numbers: the Fibonacci sequence starts with 0 and 1, and each successive number is the sum of the previous two:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

The nth Fibonacci number is the value corresponding at the nth index. So fib(0) is 0, fib(1) is 1, fib(2) is 1, fib(3) is 2, etc.

Based on this perspective, Fibonacci numbers can be calculated efficiently via a loop!

Let's run some tests:

Did you notice how fast these function invocations were?

This is the end of the notebook!