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

SICP 1.2.2 Tree Recursion （木階層再帰？）のFigure 1.5のあたりを Pythonでやってみた

Pythonでtraceみたいのできないのかな？

##### 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
```
##### 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)
```

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