...
This is a naive implementation of the Fibonacci function using exponential recursion (as well as exponential time). When tested on a Linux system, fib1(100) crashes with a segmentation fault.
| Code Block |
|---|
intunsigned long fib1(unsigned int n) { if (n == 0) return 0; else if (n == 1 || n == 2) return 1; else return fib1(n-1) + fib1(n-2); } |
...
This is a much more efficient solution, using constant space and linear time. Tested on a Linux system, fib2(100) is calculated almost instantly and with almost no chance of crashing due to a failed stack allocation.
| Code Block |
|---|
intunsigned long fib2(unsigned int n) { if (n == 0) return 0; else if (n == 1 || n == 2) return 1; unsigned intlong prev = 1; unsigned intlong cur = 1; unsigned int i; for (i = 3; i <= n; i++) { intunsigned long tmp = cur; cur = cur + prev; prev = tmp; } return cur; } |
...