SICP 1.2.2 Tree Recursion を 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)

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