Python 11:再帰関数

関数の内部で、他の関数を呼び出すことができます.関数が内部で自身を呼び出す場合、この関数は再帰関数です.例を挙げて階乗nを計算!=1 * 2 * 3 * 4... * n,fact(n)で表すと,fact(n)=n!=1 * 2 * 3 * 4... * n = (n-1)! * n=fact(n−1)*nであるため、fact(n)はn*fact(n−1)と表すことができ、n=1のみが特殊な処理が必要である.そこでfact(n)は再帰的に書きます.

def fact(n):
    if n == 1:
        return 1
    return n * fact(n - 1)

上は再帰関数です.

>>> fact(1)
1
>>> fact(5)
120

再帰関数の利点は定義が簡単で、論理がはっきりしていることです.理論的には,すべての再帰関数はループの方式で書くことができるが,論理は再帰よりも明確ではない.
練習:ハノータの移動は再帰関数で非常に簡単に実現できる.move(n,a,b,c)関数を作成してください.パラメータnを受け入れ、3つの柱A,B,Cのうち1番目の柱Aの皿の数を表し、すべての皿をAからBを借りてCに移動する方法を印刷します.

def move(n,a,b,c):
    if n == 1:
        print(a,'-->'c)    #a       
    else：
        move(n - 1,a,c,b)    # a n-1    b
        move(1,a,b,c)    # a        c
        move(n-1,b,a,c)    # b   n-1    c