Fibonacci Numbers - Iteratively and Recursively

Question

mohammadkotb · Accepted Answer

Also there is another solution using linear recurrences will compute f[n] in O(lg n) using matrix multiplication

      int[][] arr = {{1, 1},
		          {1, 2}};
	
	public int fib(int n) {
		n--;
		int[][] fib = matrixPow(arr, n/2);
		if (n % 2 == 0) {
			return fib[0][0] + fib[0][1];
		}
		else {
			return fib[1][0] + fib[1][1];
		}
	}
	
	public int[][] multiply(int[][] a1, int[][] a2) {
		int[][] ret = new int[2][2];
		for (int i = 0; i < ret.length; i++) {
			for (int j = 0; j < ret.length; j++) {
				for (int k = 0; k < ret.length; k++) {
					ret[i][j] += a1[i][k] * a2[k][j];
				}
			}
		}
		return ret;
	}

	public int[][] matrixPow(int[][] a, int pow) {
		if (pow == 1) {
			return arr;
		}
		int[][] tmp = matrixPow(a, pow/2);
		
		if (pow % 2 == 0) {
			return multiply(tmp, tmp);
		}
		else {
			return multiply(tmp, multiply(tmp, arr));
		}
	}

Anonymous · Answer

Tail recursively:

f(a, b, 0) = b
f(a, b, n) = f(a+b, a, n-1) for n>0

fibonacci(n) = f(1, 0, n)

mohammadkotb · Answer

recursively:
long fib(int i) {
   if (i == 0 || i == 1) return 1;
   return fib(i-1) + fib(i-2);
}

recursively using memoization:
long[] f; //initialized by -1
long fib(int i) {
    if (i == 0 || i == 1) return 1;
    if (f[i-1] == -1) f[i-1] = fib(i-1);
    if (f[i-2] == -1) f[i-2] = fib(i-2);
    return f[i-1] + f[i-2];
}

iteratively:
long fib(int i) {
   long f0 = 0, f1 = 1;
   for (int j = 1; j <= i ; j++) {
      long tmp = f0;
      f0 = f1;
      f1 += tmp;
   }
   return f0;
}

Meta

Meta interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches