2018-03-20 HW

posted Mar 20, 2018, 6:05 AM by Konstantinovich Samuel   [ updated Mar 20, 2018, 6:11 AM ]
Goal: Recursion Part II:  Recursion

Let us start with the simplest examples:  (Single variable count up/down recursive problems)

note: many of these problems can be solved in other ways. We will focus on a recursive solution.

How to come up with a recursive solution:
- Find the simplest possible case for the problem (base case)
- Find a relationship that can express the answer as a smaller identical operation plus a small amount of extra work.
    hint: to do this, you can ask how can you get from the base case to the next most complicated case, how can you get from that case to the next...


What does 5! mean?

How can you write a definition of factorial that uses factorial?

Think of a base case and recursive case!
-If I can solve the problem now, without recursion, the function simply returns a value. (base case) 
-If I cannot solve the problem now without recursion, the function reduces the problem to something smaller and similar and calls itself to solve the problem. (recursive case)

Write a function that uses this definition!

hint: You need at least an if statement for recursive problems. Sometimes you need more
Usually you can start out with:
if ???:  
   #base case
   #recursive case

Consider the Fibonacci sequence:
0 1 1 2 3 5 8 13 21 34 55 . . .


n    nth term of the sequence
0    0
1    1
2    1
3    2
4    3
5    5

The first two terms are 0 and 1. Each subsequent term is the sum of the previous two.
0 + 1 -> 1
1 + 1 -> 2
1 + 2 -> 3
2 + 3 -> 5

QUESTIONS (Write complete answers in your notes before you write a function.)
Answer in your notebook in complete sentences or equations so you don't have to copy the question.

1. Describe in an expression: the relationship of fib(5) in terms of other fib() calls.  e.g.  fib(5) =  ???
2. Describe in an expression: the relationship of fib(n) in terms of other fib() calls.  e.g.  fib(n) = ???
3. What must the base case(s) be?
4. Draw a tree of function calls that shows how you would evaluate: fib(5)   similar to tracing from yesterday but with 2 arrows going down!
5. How many times do you need to call a fib() function for fib(5)?
6. What happens to this diagram if you want to evaluate fib(6) / how many calls does this require?
7. How fast is the number of calls growing compared to the n value in fib(n)?
Now start writing your fib function in python.

1. Refresh your memory of basic turtle movement commands, and NetLogo functions/procedures.
2. Complete your fib(n) function in python.  
3. What is the largest n you can calculate in fib(n) that completes in less than 5 seconds? (start with lower numbers and then try larger as you test)