python学習031-----pythonの再帰(二):フィボナッチ数列の実現(再帰/非再帰方法効率比較)

フィボナッチ数列:1 2 3 4 5 6 8 9 10...1     1     2     3     5     8    13   21   34    55   ...
1.反復でフィボナッチ数列を実現する(非再帰的方法)

def fab(n):   
    n1 = 1      
    n2 = 1      
    n3 = 1     

    if n < 1:   
        print('    ！')
    
    while (n-2) > 0:    
        n3 = n2 + n1   #        
        n1 = n2            #   ，    ，         
        n2 = n3            
        n -= 1              

    return n3            

a = int(input('             ：'))
result = fab(a)
print(' %d       %d' % (a, result))

2.再帰方法原理:(木構造図)Fab(5)Fab(4)+Fab(3)Fab(3)+Fab(2)         +          Fab(2)    +      Fab(1)       Fab(2)+Fab(1)+Fab(1)+Fab(0)  +  Fab(1)+Fab(0)      Fab(1)+Fab(0)

def fab1(n):
    if n < 1:
        print('    ！')

    if n == 1 or n == 2:
        return 1               #            ，     1
    else:
        return fab1(n-1) + fab1(n-2)

a = int(input('             ：'))
result = fab(a)
print(' %d       %d' % (a, result))

比較した結果,再帰法は簡単で理解しやすいが,大量のCPUリソースを浪費し,計算時間も非再帰法よりかなり長い.非再帰的な方法は,コードが少し複雑であるにすぎないが,計算時間は短く,CPUリソースをあまり占有しない.これが再帰法の使用を提唱しない理由である.