再帰呼び出しの復習

python

院試の勉強をしていたら、ハノイの塔のアルゴリズムが出てきた。
そういえばやったなーと思い返しつつ、アルゴリズムを見て愕然とした。
自分が再帰というものを全く理解していなかったから。


もっとも単純な再帰は階乗の計算。

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

再帰＝繰り返し(＝while)だと思って↓↑↓という目線で追ってしまうが、そうではない。
名前の通り、関数の中で関数を何度も呼び出しているだけなので、動きとしてはずっと↓だ。


通常、関数内で定義した変数はローカル変数扱いになるので、スコープは関数内でのみ有効。
つまり、変数nはfact(n)が実行される度に更新されるのではなく、新に生成されたnに代入されている。


また、計算の途中経過を引数 a に記憶している。
fact()の実行例を見るとわかりやすい。

fact(4, 1)
  fact(3, 4)
    fact(2, 12)
      fact(1, 24)
        fact(0, 24)
        => a の値 24 を返す
      => 24
    => 24
  => 24
=> 24

効率という点では、繰り返しで書いた方が良いらしい。
再帰を用いる利点は「簡単に書ける」こと。
「簡単に書ける」というのは、プログラムを書くにあたって素晴らしい利点だと思う。
（もちろん、速度を気にしなければいけないときもある、いやむしろ多いけど。）

関数型言語の場合、while文 や for文 などの繰り返しがないプログラミング言語があります。また、論理型言語 Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。

お気楽 Python プログラミング入門：第３回再帰定義と高階関数

これはちょっと興味深いなー

ハノイの塔

#!/usr/bin/python
#-*- coding: utf-8 -*-
# Tower of Hanoi

# tFrom : 動かす円盤がある塔
# tDest : 動かす円盤を入れる塔
# tWork : 残りの塔

def hanoi(n, tFrom, tWork, tDest):
    if (n>=1):
        hanoi(n-1, tFrom, tDest, tWork)
        print "disc:%d  %s -> %s" % (n, tFrom, tDest)
        hanoi(n-1, tWork, tFrom, tDest)


hanoi(3, "A", "B", "C")

ちなみに、n枚の円盤をルール通りに中心に置き換えるステップをT(n)とすると、
T(n) = 2**n - 1

スペシャルサンクス