Apple Interview Question
Write code for generating a factorial/fibonacci for a given number using both recursive and non-recursive methods. Advantages and disadvantages of each method.
Interview Answers
Anonymous
// Iterative saves stack space but is more complicated to write. Recursive is easier to write but will use more stack space. unsigned int fibIterative(unsigned int n) { int i, nMinusOne, nMinusTwo; unsigned int output; if(n == 0) return 0; if(n == 1) return 1; // f(n) = f(n-1) + f(n-2) nMinusOne = 1; nMinusTwo = 0; for(i = 2; i <= n; i++) { output = nMinusOne + nMinusTwo; nMinusTwo = nMinusOne; nMinusOne = output; } return output; } unsigned int fibRecursive(unsigned int n) { if(n == 0) return 0; if(n == 1) return 1; return fibRecursive(n - 1) + fibRecursive(n - 2); }