Recusive and Tail Recursive: factorial

Recursive

# Definiation of factorial
# 0! = 1
# n! = n * (n - 1)!
#
#|Call:1    │->│Call:2    │->│Call:3    │->│Call:4    │->│Call:5    │
#│n:4       │  │n:3       │  │n:2       │  │n:1       │  │n:0       │
#│value : 24│<-│value : 6 │<-│value : 2 │<-│value : 1 │<-│value : 1 │
#
#@profile
def fact(n):
    if n == 0: return 1
    return n * fact(n - 1)

fact(20)

Tail Recursive

# e.g
#fact(4, 1)
#  fact(3, 4)
#    fact(2, 12)
#      fact(1, 24)
#        fact(0, 24)
#        => return x: 24
#      => 24
#    => 24
#  => 24
#=> 24
#@profile
def fact(n, x=1):
    if n == 0: return x
    return fact(n - 1, n * x)

print(fact(4))

# it can be rewritten like this
# tail recursive optimization
def opt_fact(n):
    x = 1
    while n > 0:
        x *= n
        n -= 1
    return x

print(opt_fact(4))

再帰定義のなかで、最後に再帰呼び出しを行う場合を「末尾再帰 (tail recursion) 」といいます。

ref:
http://www.geocities.jp/m_hiroi/light/python03.html

tail recursive
http://melborne.github.io/2009/03/18/notitle/