【题集】计算斐波那契数列第n项的函数定义如下-若执行函数调用表达式fib(7),函数fib被调用的次数是多少？

计算斐波那契数列第n项的函数定义如下： 

  

   

    

     

    
    

     

      int fib(int n){ 
     
    
   

    

     

    
    

     
 if(n==0) 
     
    
   

    

     

    
    

     
 return 1; 
     
    
   

    

     

    
    

     
 else if(n==1) 
     
    
   

    

     

    
    

     
 return 2; 
     
    
   

    

     

    
    

     
 else 
     
    
   

    

     

    
    

     
 return fib(n-1)+fib(n-2);
     
    
   

    

     

    
    

     

      }
     
    
  
 

请问fib(1)-fib(9)各调用 多少次fib函数

解答：

对于小数据量的n来说

f(1) 调用1次

f(2) 调用3次

f(3) 调用5次

f(4) 调用9次

发现一个规律：从n=3开开始，调用次数为前两次和加1

即：f(3) =f(2) +f(1) +1=5

      f(4) =f(3) +f(4) +1=9

      f(5) =f(4) +f(3) +1=15

      f(6) =f(5) +f(4) +1=25

      f(7) =f(6) +f(5) +1=41

       f(8) =f(7) +f(6) +1=67

       f(9) =f(8) +f(7) +1=109

文章来源: kings.blog.csdn.net，作者：人工智能博士，版权归原作者所有，如需转载，请联系作者。

原文链接：kings.blog.csdn.net/article/details/94022417