【python算法学习1】用递归和循环分别写下 fibonacci 斐波拉契数列,比较差异

07-14 866阅读

问题: fibonacci 斐波拉契数列,用递归和循环的方法分别写,比较递归和循环的思路和写法的差别

最直接的思路,是写递归方法

循环方法的稍微有点绕,我觉得问题主要是出在,总结循环的通项公式更麻烦,难在数学上。

1 python写的递归如下

1.1 py代码

####------递归版fib--------------####
def fib1(x):
    if x==0:
        return 1
    if x==1:
        return 1
    else:
        return fib1(x-1)+fib1(x-2)
        
print(fib1(5))
print()
for i in range(6):
    print(fib1(i))
print()

【python算法学习1】用递归和循环分别写下 fibonacci 斐波拉契数列,比较差异

1.2 总结写这个fibo数列的递归的难点

  • 最核心的,先要总结递归规律
  • 这个fibo的递归规律很简单,就是 f(x)=f(x-1)+f(x-2), 这个也是通项公式
  • fibo的这个规律狠清晰,不难

    2 python写的循环版本

    2.1 py代码,循环版本

    ####------循环版fib--------------####
    def fib2(x):
        sum1=1
        sum2=1
        for i in range(x):
            if i==0:
                sum=1
            if i==1:
                sum=1
            elif i>1:
                sum=sum1+sum2
                sum1=sum2 
                sum2=sum 
        return sum   
        
    print(fib2(6))
    print()

    【python算法学习1】用递归和循环分别写下 fibonacci 斐波拉契数列,比较差异

    2.2 没解决的奇怪报错问题

    2.2.1 报错的代码

    ####------循环版fib--------------####
    def fib2(x):
        sum1=1
        sum2=1
        for i in range(x):
            if i==0:
                sum=1
            if i==1:
                sum=1
            elif i>1:
                sum=sum1+sum2
                sum1=sum2 
                sum2=sum 
        return sum   
        
    print(fib2(6))
    print()
    for i in range(6):
        print(fib2(i))
    print()
    

    2.2.2 导致报错的代码:报错的部分由于下面这部分引起

    开始我并没有发现

    后面发现删除这段代码就不报错

    for i in range(6):

        print(fib2(i))

    print()

    2.2.3 报错内容

    UnboundLocalError: cannot access local variable 'sum' where it is not associ

    报错解释:

    UnboundLocalError 指的是在函数内部尝试访问一个还没有赋值的局部变量。在 Python 中,如果你在函数内部给一个变量赋值了,它就会被视为一个局部变量,除非明确地声明它是全局变量。如果你在赋值之前就尝试访问它,就会引发 UnboundLocalError。

    报错原因可能是你在给变量 sum 赋值之前就尝试使用它,或者你的函数内部有一个 sum() 内置函数的调用,导致名称冲突。

    【python算法学习1】用递归和循环分别写下 fibonacci 斐波拉契数列,比较差异

    2.2.4 暂时没有找到好的解决办法

    3 关于 fibo的循环版本的详细说明

    3.1 对循环版fibo数列的 详细打点说明版本,可以清晰看到过程

    ####------循环版fib,详细打点--------------####
    def fib3(x):
        #sum=0  #为啥详细版的这里不设 sum=0 不报错呢?
        sum1=1
        sum2=1
        for i in range(x):
            print("for循环第", i+1 ,"轮开始")
            if i==0:
                sum=1
            if i==1:
                sum=1
            #sum3=sum1+sum2
            #sum4=sum3+sum2
            #sum5=sum4+sum3
            #从这些公式里抽象出循环的,变换规律,抽象出通用公式+(先)辅助的值变换公式
            elif i>1:   #直接用 esle居然不行,必须判断 elseif i>1
                print("sum1=",sum1)
                print("sum2=",sum2)
                sum=sum1+sum2
                print("sum=",sum)
                sum1=sum2  #和下面那句顺序不能反
                sum2=sum 
                print("sum1=",sum1)
                print("sum2=",sum2)
            print("sum=",sum)
            print("for循环第", i+1 ,"轮结束")
            print()
        return sum   
        
    print(fib3(6))
    print()
    

    【python算法学习1】用递归和循环分别写下 fibonacci 斐波拉契数列,比较差异

    3.2 最核心的,先要从表面的 递推关系上找到 通项公式组

            if i==0:

                 sum=1

            if i==1:

                sum=1

            sum3=sum1+sum2

            sum4=sum3+sum2

            sum5=sum4+sum3

    • 可以看到
    • S3=S2+S1
    • S4=S3+S2
    • ...
    • 通项公式 S(n) =  S(n-1)+ S(n-2)
    • 但是循环不能像递归那样调用 函数本身,那就要找到 通项公式里的循环规律
    • 除了S(n) =  S(n-1)+ S(n-2)
    • 仔细看
    • 还有S(n-1)=S(n)
    • 还有S(n-2)=S(n-1)

      因此,联立这3个方程就可以了

      • S(n) =  S(n-1)+ S(n-2)
      • S(n-1)=S(n)
      • S(n-2)=S(n-1)

        4 目的:总结  递归和循环思想的相同和区别

        4.1 区别

        • 递归是在函数内部,调用函数自身( 函数定义内部,函数的代码block里引用自己的函数名)
        • 不用直接写循环,写调用函数自身,没有直接的for while等循环形式
        • 但是其实内部已经是循环逻辑了
          • 循环是,除了处理一些特殊情况外,找到通项公式,以便进行循环
          • 肯定有循环的形式如for while等
          • 有可能是几个 通项公式方程组,反正要组成合理的,循环体,镶嵌在前面的循环形式for/while等之内

                for i in range(x):

                    if i==0:

                        sum=1

                    if i==1:

                        sum=1

                    elif i>1:

                        sum=sum1+sum2

                        sum1=sum2 

                        sum2=sum 

            4.2 相同

            • 本质都是循环逻辑
            • 都需要找出数列的通项公式,便于告诉计算机进行循环计算
            • 在fibo数列里,循环方式,找通项公式,更难

              5 比较网上别人写的 fibo的 递归和 循环的代码

VPS购买请点击我

文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。

目录[+]