int fib(int n) { if (n == 0) return 0; if (n == 1) return 1; if (n == 2) return 1; return fib(n - 1) + fib(n - 2); } // 尾递归版本 int fib(int n) { int _fib(int n, int a, int b) { if (n == 0) return 0; if (n == 1) return 1; if (n == 2) return a; return _fib(n - 1, a + b, a); } return _fib(n, 1, 1); }
- 依照维基百科[^1]，
0是斐波那契的第0项，所以不要忘记它；
- 尾递归有编译器优化，不容易栈溢出，但不如一般的递归直观；