【毎日python】再帰関数

ラーニングWebサイト:再帰関数かいきかんすう
注意点:
再帰関数の利点は定義が簡単で、論理がはっきりしていることです.理論的には,すべての再帰関数はループの方式と書くことができるが,ループの論理は再帰的にはっきりしていない.再帰関数を使用するには、スタックオーバーフローの防止に注意する必要があります.コンピュータでは、関数呼び出しはスタック(stack)というデータ構造によって実現され、1つの関数呼び出しに入るたびにスタックにスタックフレームが追加され、関数が戻るたびにスタックフレームが減少する.スタックのサイズは無限ではないため、再帰呼び出しの回数が多すぎると、スタックがオーバーフローします.再帰呼び出しスタックオーバーフローを解決する方法は,テール再帰最適化により,事実上テール再帰とループの効果は同じであるため,ループを特殊なテール再帰関数と見なすことも可能である.テール再帰とは、関数が返されると、自身が呼び出され、return文に式が含まれないことを意味します.これにより、コンパイラまたは解釈器は、再帰自体が何度呼び出されてもスタックフレームを1つだけ占有し、スタックオーバーフローが発生しないように、テール再帰を最適化することができる.最後の再帰呼び出しの場合、最適化を行った場合、スタックは増加しないため、何度呼び出してもスタックオーバーフローは発生しません.残念なことに、多くのプログラミング言語はテール再帰に対して最適化されておらず、Python解釈器も最適化されていない.
練習する
ハンノタワーの移動は再帰関数で非常に簡単に実現できる.
パラメータmove(n, a, b, c)を受け取り、3つの柱A、B、Cのうち1番目の柱Aの皿数を表すn関数を作成し、すべての皿をAからBを介してCに移動する方法を印刷してください.
問題を見終わった後、少し輪をかぶって、簡単に押すことができます.皿が1つしかない場合は、直接AをC(1ステップ)に移動し、2つある場合はAをBに移動し、AをCに移動し、BをC(3ステップ)に移動します.3回だと7歩かかります.すなわち3=2*1+1である.7=2*3+1. では、f(n)=f(n−1)*2+1である.皿数が増えるにつれて,移動回数が指数関数的に増加することは明らかである.
では、移動は具体的にどのように実現されるのでしょうか.ここに著者のコードを置いて、それぞれ理解します.

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

テスト:

>>> move(4,"A","B","C")
move A --> B
move A --> C
move B --> C
move A --> B
move C --> A
move C --> B
move A --> B
move A --> C
move B --> C
move B --> A
move C --> A
move B --> C
move A --> B
move A --> C
move B --> C