javascript - 哪位大神可以用递归法写出来么，或者循环

Question

有一种幻想出来的生物叫幻想的物种（不会死亡），幼年时候叫小幻，成年的时候叫大幻，小幻经过一年才能变成大幻，大幻拥有繁殖能力每年能分裂出一个小幻。
请问：一开始只有1只小幻，经过年数为167年时 一共的多少只幻想的物种？

Answer 1

第一年：1大0小
第二年：1大1小
第三年：2大1小
第四年：3大2小
第五年：5大3小
第六年：8大5小
第七年：13大8小
...

大幻的增长呈斐波那契数列

function fibonacci(n) {
  if (n === 1 || n === 2) return 1;

  return fibonacci(n - 1) + fibonacci(n - 2);
}

经过年数为167年时 一共有fibonacci(167)只幻想的物种

Answer 2

我的理解是，小幻变成大幻后，当年就可以生小幻
这样就是一个指数序列，第一年有1个，第二年2个，第三年4个，……

总数就是：2^166

好吧，这样貌似也不需要递归了

Answer 3

这是典型的斐波那契数列问题。这里使用循环来解决：

function fib(year){

    if(year == 1 || year == 2){
        console.log("1");
    }else{
        var magicBeast = [1,1];
        for(var i = 2; i < year; i++){
            magicBeast.push(magicBeast[i-1]+magicBeast[i-2]);
        }
        console.log(magicBeast[magicBeast.length-1]);
    }
}

fib(167);

Answer 4

循环一下就得到了

var aa=function(x,y,z){//x是小,y是大,z是年份
    for(var i=0;i<z;i++){
        var m=x;
        x=y;
        y=m+y;
        //x=[y,y=y+x][0]
    }
    console.log(x,y,z)
}   
aa(1,0,6)

Answer 5

参见数据结构（大话数据结构有很清晰很通俗的讲解） 栈的应用一节；答案一楼加三楼正解哈～～斐波那契数列到了查找算法哪里还有重要应用，最后烂熟于心。。。。

Answer 6

@小俞 的递归算法，用js算不出来~

@TabWeng 的算法能得到结果，但超出了双精度数所表示的范围。

js太勉强，还是用python3 来算一个吧~

def fib_itr(n):
    if n<0: return None
    if n<=1: return (0,1)[n]
    a,b = 0,1
    for i in range(n-1):
        a, b = b, a+b
    return b

print(fib_itr(167))
35600075545958458963222876581316753

Answer 7

但是 js 可以尾递归啊，蛤蛤

function fib(n) {
  'use strict';
  if (n === 1 || n === 2) return 1;
  return tail(n, 1, 1, 3);

  function tail(n, b1, b2, begin) {
    if (n === begin) return b1 + b2;
    return tail(n, b2, b1 + b2, begin + 1);
  }
}
fib(167);