読者です 読者をやめる 読者になる 読者になる

牌語備忘録 -pygo

あくまでもメモです。なるべくオフィシャルの情報を参照してください。

牌語備忘録 -pygo

SICP 1.2.1 再帰と反復の練習問題1.9をPythonでやってみた

SICP Python

SICP 1.2 Procedures and the Processes They Generate(手続きと生成プロセス)

## 1.2.1  Linear Recursion and Iteration(線形の再帰と反復)
# 図 1.3:再帰の例
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)
print factorial(6) #720

# 図 1.4:反復の例
def factorial(n):
    return fact_iter(1, 1, n)
def fact_iter(product, counter, max_count):
    if counter > max_count:
        return product
    return fact_iter(counter * product,
                     counter + 1,
                     max_count)
print factorial(6) #720

schemeのコード見ながらpythonのコード書くと、return付け忘れがちになるから気をつけなければ...(´・ω・`)

# Exercise 1.9. (練習問題 1.9.)
# Are these processes iterative or recursive?(これらのコードは反復的か再帰的か?)
#
def inc(x):
    return x + 1
def dec(x):
    return x - 1

def plus_a(a, b):
    if a == 0:
        return b
    return inc(plus_a(dec(a), b))
print plus_a(4, 5)
"""
plus_a(4,5)
CALL -> inc(plus_a(dec(4), 5))
CALL -> inc(inc(plus_a(dec(3), 5)))
CALL -> inc(inc(inc(plus_a(dec(2), 5))))
CALL -> inc(inc(inc(inc(plus_a(dec(1), 5)))))
RETN -> inc(inc(inc(inc(5))))
RETN -> inc(inc(inc(6)))
RETN -> inc(inc(7))
RETN -> inc(8)
9

recursive
"""

def plus_b(a,b):
    if a == 0:
        return b
    return plus_b(dec(a), inc(b))
print plus_b(4, 5)
"""
plus_b(4,5)
plus_b(dec(4), inc(5))
plus_b(dec(3), inc(6))
plus_b(dec(2), inc(7))
plus_b(dec(1), inc(8))
9

iterative
"""

これでいいのかしらん?