Courses‎ > ‎AP Computer Science 2‎ > ‎konstantinovich‎ > ‎

2018-02-02 HW01 Recursion

posted Feb 2, 2018, 9:56 AM by Konstantinovich Samuel   [ updated Feb 11, 2018, 6:32 PM ]
Goal: Basic Recursion + Getting stuff done!

Lab + Homework:
Deadline is Tuesday 6am.

Lab: Discussion and working on Recursion2 problems.

Make a new github repo for this semester's homework.  MKS22X 
You will make a new folder on the TOP LEVEL OF YOUR REPO* for each homework starting with a 2 digit homework number. *Do not make a folder and put all of your homework assignments into it. The repo IS your "folder".


Submit your repo here:  

Recursion with Helper Methods
The purpose of a helper method is to be able to add parameters and modify them as you make new recursive calls. Just a single parameter isn't enough to solve it in linear time.

Let us solve this recursively as a warmup:

public static int sumZeroToN(int n){


public static int sumAtoB(int a,int b){


LAB 01Recurison:

You are writing a class called Recursion for grading purposes this must be exact.
IMPORTANT NOTE: The methods will NOT be static. I will instantiate a Recursion object to test your code.  

1.1 You are solving several problems recursively and storing them ALL in one java file:

Note that All of the methods will throw an IllegalArgumentException when n < 0. 

1.1a: factorial [aka do you even recursion?]

public int fact(int n)

Hint; What is 0 factorial?

1.1b Fibonacci [Function should be O(n) ]

public int fib(int n)

fib(0) -> 0
fib(1) -> 1

1.1c: Square Root

public double sqrt(double n)

Now to think a little:

Newton's Square Root Approximation:

There is a formula to calculate square root
Guess any number for the sqrt of n. (like n/2, or even 1)
n = 100
guess = 1

Make a better guess this way: 
guess =  ( n / guess + guess) / 2

             = 50.5

(then do it again, then do it again)
guess = 26.24009900990099
guess = 15.025530119986813
guess = 10.840434673026925
guess = 10.032578510960604
guess = 10.000052895642693
Notice how fast this converges on the correct value (10).

Watch it converge on Sqrt(2)

** Again, you MUST make a helper function because you have to keep track of both n, and your guess in the recursion. This means that you need a function with two parameters, even though the sqrt function only takes 1 parameter.

2. Need to study longer? (You are doing it wrong)
Let me end with a link to a video about how to study for less time and get more out of it. Even if you only watch the first 5-10 minutes you will be much smarter.
You can watch as little or as much of this video as you want, I won't ever check... but you won't increase your GPA either.  If  this video helps you do better please let me know!
This pairs nicely with every article about sleeping more to remember things better...