nの階乗を求める - コード

仕様

uronti.hatenablog.com

実行・開発環境

ubuntu 14.0.4
python 2.7.6

コード1 線形再帰

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

n = raw_input("n = ")
ans = myfunc(int(n))
print(ans)

上記のコードで myfunc(3)を実行すると以下の計算がされる。
myfunc(3) = 3 x (myfunc(2))
= 3 x (2 x (myfunc(1)))
= 3 x (2 x (1 x (myfunc(0)))
= 3 x (2 x (1 x (1)))
= 6
このように、覚えておく演算がnに比例して増えるものを「線形再帰」という。

コード2 末尾再帰

def factiter(n, acc):
    if n == 0:
        return acc
    else:
        return factiter(n - 1, acc * n)

def myfunc(n):
    return factiter(n, 1)

n = raw_input("n = ")
ans = myfunc(int(n))
print(ans)

上記のコードで myfunc(3)を実行すると以下の計算がされる。
myfunc(3) = factiter(3, 1)
= factiter(2, 3 x 1)
= factiter(1, 3 x 2)
= factiter(0, 6 x 1)
= 6
このように、再帰呼び出しがその計算における最後のステップになっているよるものを「末尾再帰」という。
線形回帰と末尾回帰の処理の違いについては、私自身が理解していないため、ここでは書かない。

参考

プログラミング入門第4回「再帰と反復」二宮崇
http://aiweb.cs.ehime-u.ac.jp/~ninomiya/itp/itp-4.pdf
末尾再帰 - Wikipedia

メモ

• 関数「myfunc」はコードが長い時には使えない。
• コーディングに一貫性を持たせるためのルールは？
• 末尾回帰コードは最適化されているのか？

次回

7月12日(日)に投稿します。