首页 > 代码库 > 递归求解斐波那契fib(10)一共调用了多少次fib()函数
递归求解斐波那契fib(10)一共调用了多少次fib()函数
定义fib()如下:
int fib(int n) { count ++; if (n==0) return 1; else if (n==1) return 1; else return fib(n-1) + fib(n-2); }
由原来fib的地推公式得出求解次数的地推公式。
那么Count(fib(10)) = count(fib(9)) + count(fib(8)) + 1;
求解count( fib(n) ) 的次数,就是计算fib(n)递归树(是一个二叉树),叶子结点的个数。
count( fib(0) ) = 1
count( fib(1) ) = 1
count( fib(2) ) = count ( fib(1) ) + count( fib(0) ) + 1 = 3
count( fib(3) ) = count ( fib(2) ) + count( fib(1) ) + 1 = 3+1+1 = 5
这个样子计算的还是很快的
fib(10),一共调用了 177次。
其实上面是360的一道面试题
递归求解斐波那契fib(10)一共调用了多少次fib()函数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。