Learning Notes

CS61B Disc2 Introduction to Java

The discussion part is skiped and this note is mainly for the record of two ways of forming Fibonacci number.

The First Fibonacci

Implement fib which takes in an integer n and returns the nth Fibonacci number.

The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, . . .. The first two numbers in the sequence are 0 and 1, and every number thereafter it is the sum of the two numbers in the sequence before it.

Considerations:
1.Recursive in the first thought;
2.Fibonacci pattern, fib(n) = fib(n - 1) + fib(n - 2);
3.Special consideration to fib(0) and fib(1), since they do not have something like fib(n - 2).

1
2
3
4
5
6
7
public static int fib(int n) {
    if (n > 1) {
        return fib(n - 1) + fib(n - 2);
    } else {
        return n;
    }
}

Another Fibonacci

Extra: Implement a more efficient version of fib in 5 lines or fewer. Here, efficiency might mean making less recursive calls or doing less overall computation. You don’t have to make use of the parameter k in your solution.

start with : 

1
2
public static int fib2(int n, int k, int f0, int f1) {
}

Considerations:
1.Recursive, but unlike the previous ocassion, we start from the smaller number;
2.We want nth Fibonacci number, k start from 0 and we recursivly find kth Fibonacci number, until k=n;
3.f0 represents the value of kth number, f1 represents (k+1)th number.
4.The recursive should be like:
fib2(n,0,0,1)
fib2(n,1,1,1)
fib2(n,2,1,2)
fib2(n,3,2,3)
fib2(n,4,3,5)
…

1
2
3
4
5
6
7
public static int fib2(int n, int k, int f0, int f1) {
    if (n == k) {
        return f0;
    } else {
        return fib2(int n, int k + 1, int f1, int f0 + f1);
    }
}