再帰


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

再帰プログラム、リカーシ

プログラムで高速に検索できる構造といえば、木構造。

世の中の関係をモデル化するといえば、グラフ構造。

とは言いすぎかもしれませんけど、

それらを扱うときに再帰というテクニックを利用することができます。


階乗を計算するプログラム

import math
math.factorial(10)

で終了ですが、ここはしばしお付き合いを。


階乗とはN!で計算できる例の計算です。

10!だったならば、

1*2*3*4*5*...*9*10

で計算できる値です。

素直に機械よりの脳みそでプログラミングするとこうです。

def fact(n):
  ans = 1
  for x in range(n):
    ans *= x
  return ans

もしかして今このドキュメントを読んでいる人からすると、

不自然に写っているかもしれませんが。

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

こんな感じに、10の階乗とは10 * (9の階乗)であらわせる、

9の階乗とは 9 * (8の階乗)で、

8の階乗とは 8 * (7の階乗)で・・・という具合に記述した代物です。

ただし、

1の階乗は必ず1ですので、最後これを書いてやります。



僕は再帰を理解したのはschemeという言語のおかげなので、

そっちの名著、SICPを一読してみるのをおすすめします。

プログラミングGaucheでもいいと思います。


末尾再帰。

再帰呼び出しの関数が終わった時、元の関数に戻っても行うことがない

という限られた状態のとき、末尾再帰という特殊な呼び方をします。

ちなみにさっきの計算は末尾再帰になっていません。あしからず。

ただし大体の関数は末尾再帰に書き換えることができます。

末尾再帰とはforループと処理としては等価なので、

これをマスターすれば再帰をforループに展開、

またはforループを再帰にするといったことを自由自在に行えるようになります。

だからなんだという話ですが。


factorialを末尾再帰にしてみます。

いろんな戦略はありますが、

一番単純な、答えを最後の関数にまで渡して見ることにしましょう。

def fact2(n,ans=1):
  if n==1:
    return ans
  else:
    return fact(n-1,ans * n)

こうすることで、今までは

元の関数にもどって"掛け算をする"という処理があったのですが、

それをなくすことができました。

第二引数にansが渡されるので、これは演算結果を逐次次の関数に渡しています。

バケツリレーですかね。え、違う?

で、一番最後,nが1になったときにreturn でその結果を返してやります。

元の関数に戻ってきても値をreturnするだけです。

これが末尾再帰というやつです。

末尾再帰では計算効率を上げるメモ化、漸化式が利用できない。

この形は再帰の関数が呼び出され、計算が進んでいくので、

元の再帰よりもスタックを食いつぶさなくてよいように見えますが、

計算を工夫しようとした際にネックになる部分もありますんでお気をつけてということでした。

ハノイの塔