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

牌語備忘録 -pygo

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

牌語備忘録 -pygo

SICP 1.2.2 Tree Recursion を Pythonでやってみた

SICP Python

SICP 1.2.2 Tree Recursion (木階層再帰?)のFigure 1.5のあたりを Pythonでやってみた


視覚的にプロセスがわかるよう、有名どころのここを参考にtraceを使ってみた。(slibはMacportsで簡単にインスコロールできた)
Pythonでtraceみたいのできないのかな?

###再帰的(recursive)
scheme(recursive)
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)) 
                 (fib (- n 2))))))
Gausheでの実行結果(recursive)
gosh> fib
gosh> (use slib)
#<undef>
gosh> (require 'trace)
#t
gosh> (trace fib)
#<closure (debug:trace-procedure debug:trace-procedure)>
gosh> (fib 5)
CALL fib 5
 CALL fib 4
  CALL fib 3
   CALL fib 2
    CALL fib 1
    RETN fib 1
    CALL fib 0
    RETN fib 0
   RETN fib 1
   CALL fib 1
   RETN fib 1
  RETN fib 2
  CALL fib 2
   CALL fib 1
   RETN fib 1
   CALL fib 0
   RETN fib 0
  RETN fib 1
 RETN fib 3
 CALL fib 3
  CALL fib 2
   CALL fib 1
   RETN fib 1
   CALL fib 0
   RETN fib 0
  RETN fib 1
  CALL fib 1
  RETN fib 1
 RETN fib 2
RETN fib 5
5
Python(recursive)
def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)
print fib(5) #5
###反復的(recursive)
scheme(iterative)
(define (fib n)
  (fib-iter 1 0 n))
(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))
Gausheでの実行結果(iterative)
gosh> fib
gosh> fib-iter
gosh> (use slib)
#<undef>
gosh> (require 'trace)
#t
gosh> (trace fib-iter)
#<closure (debug:trace-procedure debug:trace-procedure)>
gosh> (trace fib)
#<closure (debug:trace-procedure debug:trace-procedure)>
gosh> (fib 5)
CALL fib 5
 CALL fib-iter 1 0 5
  CALL fib-iter 1 1 4
   CALL fib-iter 2 1 3
    CALL fib-iter 3 2 2
     CALL fib-iter 5 3 1
     RETN fib-iter 5
    RETN fib-iter 5
   RETN fib-iter 5
  RETN fib-iter 5
 RETN fib-iter 5
RETN fib 5
5
Python(iterative)
def fib(n):
    return fib_iter(1,0,n)
def fib_iter(a,b,count):
    if count == 0:
        return b
    return fib_iter(a + b, a, count - 1)
print fib(5)

う〜ん、反復はなんとなくわかったような…。再帰は理解できてないような気が…(´・ω・`)