2018-03-22 HW

posted Mar 21, 2018, 6:58 PM by Konstantinovich Samuel   [ updated Mar 21, 2018, 7:54 PM ]
Recursion Part III : 
Goal:  Writing a function using loops, and using recursion

Do Now:
1. How many fibs could you calculate in 5 seconds?
2. What was the largest you tried and completed?
3. Is your computer smarter than a 5th grader? Why/Why not?
4. What if we got more powerful computers? How much bigger could we calculate?


Today/tonight you will:
-Write the GCD function (use prior recursive solutions to help)
-Enhance your understanding of recursive functions by:
    Comparing the recursive and loop variants and see the similarities
    Comparing the recursive solution to prior recursive algorithms to see the similarities. 

Euclidean algorithm for Greatest Common Divisor 
[ I am not explaining why the method works or how, but it is a nice way to find the  GCD ]

This algorithm is based on the fact that G.C.D. of two numbers also divides their difference!

The math behind it is not part of the scope of the class, but the algorithm is:

Calculate the remainder of the greater divided by the smaller. 
This remainder becomes the new smaller number (as it is the smallest of all 3 numbers)
The original smaller number is now the "larger"
Repeat until the remainder is 0!

For example:
We want to find the G.C.D. of 54 and 24:
-We know there is a larger and smaller value. 
-We find the remainder when dividing the larger by the smaller
54 % 24. The remainder is 6
-We keep the smaller and consider that the new larger. (24 is now the larger)
We now use the remainder as the smaller (6 is now the smaller)
-Repeat the process using 24 and 6.

Since 24 % 6 is 0, we now know the answer is 6.  [We cannot divide by 0  so we couldn't continue anyway!]

Another Example:
Can you easily find the G.C.D. of 40 and 192 this way?
192,40    192%40 -> 32
40,32      40%32 ->  8
32,8    32%8 -> 0
8,0 STOP!
8 is the GCD.

gcd(54,24) results in 6
gcd(192,40) results in 8


Classwork + Complete at home:

0. Come up with at least 10 test cases that you know the answer to! 

1. Implement this algorithm using a loop.  gcdLoop(a,b)
Think:
-When should the loop stop?

1b. AFTER you tested your function, look at your neighbors' code. 
If it isn't working ask them to explain how it should work (be their rubber ducky) 
Offer suggestions if they are stuck but don't show your code. (They should call me over if they are really stuck)

2. Implement it again, using recursion: 

gcdR(a,b)  , make sure you call gcdR, and NOT gcdLoop in your function!!

Think of these two "rules" for recursion:
-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)


Comments