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

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

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

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

1 python写的递归如下

1.1 py代码

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

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

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

2 python写的循环版本

2.1 py代码，循环版本

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

2.2 没解决的奇怪报错问题

2.2.1 报错的代码

####------循环版fib--------------####def fib2(x):sum1=1sum2=1for i in range(x):if i==0:sum=1if i==1:sum=1elif i>1:sum=sum1+sum2sum1=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() 内置函数的调用，导致名称冲突。

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

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

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

####------循环版fib，详细打点--------------####
def fib3(x):#sum=0  #为啥详细版的这里不设 sum=0 不报错呢？sum1=1sum2=1for i in range(x):print("for循环第", i+1 ,"轮开始")if i==0:sum=1if i==1:sum=1#sum3=sum1+sum2#sum4=sum3+sum2#sum5=sum4+sum3#从这些公式里抽象出循环的，变换规律，抽象出通用公式+（先）辅助的值变换公式elif i>1:   #直接用 esle居然不行，必须判断 elseif i>1print("sum1=",sum1)print("sum2=",sum2)sum=sum1+sum2print("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()

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的 递归和 循环的代码