2016/02/03

SICP 問題 5.27

5.26と同じことを再帰的階乗計算で.

;;; EC-Eval input:
(define (factorial-recur n)
  (if (= n 1)
      1
      (* (factorial-recur (- n 1)) n)))

(total-pushes = 3 maximum-depth = 3)
;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial-recur 1)

(total-pushes = 16 maximum-depth = 8)
;;; EC-Eval value:
1

;;; EC-Eval input:
(factorial-recur 2)

(total-pushes = 48 maximum-depth = 13)
;;; EC-Eval value:
2

;;; EC-Eval input:
(factorial-recur 3)

(total-pushes = 80 maximum-depth = 18)
;;; EC-Eval value:
6

;;; EC-Eval input:
(factorial-recur 4)

(total-pushes = 112 maximum-depth = 23)
;;; EC-Eval value:
24

;;; EC-Eval input:
(factorial-recur 5)

(total-pushes = 144 maximum-depth = 28)
;;; EC-Eval value:
120

;;; EC-Eval input:
(factorial-recur 6)

(total-pushes = 176 maximum-depth = 33)
;;; EC-Eval value:
720

;;; EC-Eval input:
(factorial-recur 7)

(total-pushes = 208 maximum-depth = 38)
;;; EC-Eval value:
5040

;;; EC-Eval input:
(factorial-recur 8)

(total-pushes = 240 maximum-depth = 43)
;;; EC-Eval value:
40320

;;; EC-Eval input:
(factorial-recur 9)

(total-pushes = 272 maximum-depth = 48)
;;; EC-Eval value:
362880

;;; EC-Eval input:
(factorial-recur 10)

(total-pushes = 304 maximum-depth = 53)
;;; EC-Eval value:
3628800

プッシュ回数は32n-16, 最大深さは5n+3.
反復的階乗計算はプッシュ回数が35n+34, 最大深さ10だったので, プッシュ回数は再帰的階乗計算のほうが少なく,最大深さは反復的階乗計算のほうが少ない.
階乗計算は再帰的なほうが早く計算できるがその分メモリの消費量が大きくなり,
反復的計算のほうが時間は少しだけかかるがメモリの消費量は定数に抑えられる.


© 2022 wat-aro