# SICP 1.2.4 ExponentiationをPythonでやってみた

SICPの1.2.4 ExponentiationあたりをPythonでやってみた

##### scheme
```(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))
(expt 2 4) ;16

;iterative
(define (expt b n)
(expt-iter b n 1))
(define (expt-iter b counter product)
(if (= counter 0)
product
(expt-iter b
(- counter 1)
(* b product))))
(expt 2 4) ;16

;fast exptiation
(define (square x)(* x x))
(define (even? n)
(= (remainder n 2) 0))
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
(fast-expt 2 4) ;16
```
##### python
```# recursive
def expt(b, n):
if n == 0:
return 1
return b * expt(b, (n - 1))
print expt(2,4) #16

# iterative
def expt(b,n):
return expt_iter(b,n,1)
def expt_iter(b, counter, product):
if counter == 0:
return product
return expt_iter(b, counter - 1, b * product)
print expt(2,4) #16

#fast exptiation
def square(x):
return x * x
def fast_expt(b, n):
if n == 0:
return 1
elif even(n):
return square(fast_expt(b, n / 2))
else:
return b * fast_expt(b, n - 1)
def even(n):
if n % 2 == 0:
return True

print fast_expt(2, 4) #16
print fast_expt(2, 5) #32
```