Today when I am solving Fibonacci arrays, I meet with a very strange thing. Recursion only takes 16ms, but iteration takes 80ms. I have tried to optimize my iteration (such as I use a vector container to fulfill my stack) but iteration is still much slower than recursion. It doesn't make sense because recursion still builds a stack at OS level, which is more time-consuming than iteration. Here is my iteration code:
class Solution {
public:
int fib(int n) {
std::stack<int, std::vector<int>> st;
st.push(n);
int result = 0;
int temp = 0;
while(!st.empty()) {
temp = st.top(); st.pop();
if(temp == 1) result++;
else if(temp == 0) continue;
else {
st.push(temp - 1);
st.push(temp - 2);
}
}
return result;
}
};
Here is my recursion code
class Solution {
public:
int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
else return fib(n - 1) + fib(n - 2);
}
};
Well, I have searched for the reason. According to Is recursion ever faster than looping?, recursion is more time-consuming than iteration in an imperative language. But C++ is one of the imperative languages, it is not convincing.
I think I find the reason. You can help me check if there is any incorrect in my analysis?
The reason why recursion is faster than iteration is that if you use an STL container as a stack, it would be allocated in heap space.
When the PC pointer wants to access the stack, cache missing might happen, which is greatly expensive as for a small scale problem.
However, as for the Fibonacci solution, the code length is not very long. So the PC pointer can easily jump to the function's beginning. If you use a static int array, the result is satisfying.
Here is the code:
class Solution {
public:
int fib(int n) {
int arr[1000];
arr[0] = n;
int s = 1;
int result = 0;
int temp;
while (s) {
temp = arr[s-1];
s--;
switch (temp) {
case 1:
result++;
break;
case 0:
continue;
break;
default:
arr[s++] = temp - 1;
arr[s++] = temp - 2;
}
}
return result;
}
};
