Fabonacci series : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584...
rule：The third number is equal to the sum of the first two Numbers
I once ran into an interview question: implementing the Fibonacci function.
- Implement with Recursion
- (NSInteger)recursionFibonacciWithIndex:(NSInteger)index{
while (index <= 1) {
return 1;
}
return ([self recursionFibonacciWithIndex:index - 2] + [self recursionFibonacciWithIndex:index - 1]);
}
When index == 47 ,I found the program will run a long time.
This arithmetic's Time Complexity is high(nest passage I will introduce Time Complexity), so I use another arithmetic.
- Implement with For
- (NSInteger)fibonacciWithIndex:(NSInteger)index{
NSInteger p = 1;
NSInteger q = 1;
if (index == 0 || index == 1) {
return 1;
}else{
for (NSInteger i = 2; i <= index; i++) {
NSInteger tmp = p;
p = q;
q = tmp + p;
}
return q;
}
}
Time Complexity is O(n).
Although recusion looks sample, but sometimes it will result Time Complexity higher
