面试碰到求斐波那契数列第 n 项

[oncewosiwo]

前些天面试碰到一道用递归求斐波那契数列第 n 项的题目，写了个非标准答案，结果被认为做错了😓

function fb($a,$b,$n){
    $c = $a+$b;
    if($n>0){
        return fb($b,$c,--$n);
    }
    return $c;
}

$n = 10;
$ret = fb(1,1,$n-3);  //面试的时候只写了函数本身

[aheadlead]

这真的做错了… 你这其实和写个 for loop 没啥区别

其实可以用通项公式啊： https://www.jianshu.com/p/946eb441dce5

[rabbbit]

递归的话,面试官应该是想往下递归,搞个哈希表缓存计算结果
例如
f(10) = f(9) + 10 = f(8) + 9 + 10 ...

[lhx2008]

感觉比标准递归还慢，面试官可能想让你写动归的，通项公式的话，面试官可能会觉得，嗯，你背得很好。

[rabbbit]

这种才算冷门答案

var climbStairs = function (n) {
let sqrt5 = Math.sqrt(5);
let result = (Math.pow(((1 + sqrt5) / 2), n + 1) - Math.pow(((1 - sqrt5) / 2), n + 1)) / sqrt5;
return Number(result.toFixed());
};

[casparchen]

哪儿错了，我觉得没错啊

[lhx2008]

这样写复杂度突破天际啦，传个 1000 可以算好几年

[momocraft]

易知 2x2 矩阵对乘法构成一个幺半群, 然后开始讲快速幂算法, 把对面的时间用光就行了

[brainfxxk]

@lhx2008 复杂度有什么问题？虽然 lz 这代码确实挺烂的

[aheadlead]

@lhx2008 #3 现场给他啪通项公式

[aheadlead]

说错了，推到通项公式……（我刚在想什么 /w\..）

[rabbbit]

搞错了
f(10) = f(9) + 10 = f(8) + 9 + 10 ...
-->
应该是想要这种解法
f(0) = 0
f(1) = 1
f(2) = f(0) + f(1)
f(3) = f(1) + f(2)

f(n) = f(n - 2) + f(n - 1)

[oncewosiwo]

@rabbbit 这个办法不错，以前刷题的时候看到过😂

[oncewosiwo]

@aheadlead 是临时想了下把循环给翻译成递归了

[lhx2008]

@brainfxxk 看错了，这应该是类似一种尾递归的写法，复杂度没问题

[aheadlead]

@oncewosiwo #13 这没啥意义啊...

@lhx2008 #14 不知道他这是啥具体语言…如果是 php 的话，貌似都没有尾递归优化

[ppyybb]

n=1 和 n=2 答案就不对

[CatcherO]

const fb = n => (n===1 || n===2) ? 1 : fb(n-1)+fb(n-2)
我也练习一下

[katsusan]

你这个是尾递归的写法吧，php 编译器有优化的话不会爆栈，直接用 f(n)=f(n-1)+f(n-2)的话有爆栈风险并且有重复计算。可以用闭包把重复计算的部分缓存起来，用空间换时间，理论上应该相当于直接正向计算 f(1),f(2),..,f()。

[trait]

Dasgupta,Papadimitriou, Vazirani 版本 algorithm 前言讲的就是 fibonacci，从暴力递归到矩阵和楼上的(sqrt5+1)/2 方程式，推荐去看看，以算法思想分类讲述，比市面上大多数算法书千篇一律的排序之类起手不知高到哪里去了

[xml123]

通项公式要算无理数的精确幂，不适合计算机吧，还不如递推的方案，一般还是矩阵幂二分加速吧。