* 아주 간단한 재귀호출 팩토리얼 함수 구현 소스: facto-01.clj
;;;
;;; (fact n) : a factorial function using a plain recursive call
;;;
;;; This gives rise an integer overflow while calculating 20!.
;;;
;;; Execute: clj fact-01.clj
;;;
;;; Date: 2013. 2. 11.
;;; Author: pkim ((AT)) scripts ((DOT)) pe ((DOT)) kr
(defn fact [n]
(if (< n 2) 1 (* n (fact (- n 1))) ))
(printf "10! = %s\n" (fact 10))
(printf "20! = %s\n" (fact 20))
(printf "21! = %s\n" (fact 21)) ;; integer overflow
; (printf "22! = %s\n" (fact 22)) ;; integer overflow
#_"
10! = 3628800
20! = 2432902008176640000
Exception in thread \"main\" java.lang.ArithmeticException: integer overflow
at clojure.lang.Numbers.throwIntOverflow(Numbers.java:1388)
at clojure.lang.Numbers.multiply(Numbers.java:1752)
at clojure.lang.Numbers$LongOps.multiply(Numbers.java:442)
at clojure.lang.Numbers.multiply(Numbers.java:146)
at user$fact.invoke(facto-01.clj:9)
at user$fact.invoke(facto-01.clj:9)
at user$eval6.invoke(facto-01.clj:13)
at clojure.lang.Compiler.eval(Compiler.java:6511)
at clojure.lang.Compiler.load(Compiler.java:6952)
at clojure.lang.Compiler.loadFile(Compiler.java:6912)
at clojure.main$load_script.invoke(main.clj:283)
at clojure.main$script_opt.invoke(main.clj:343)
at clojure.main$main.doInvoke(main.clj:427)
at clojure.lang.RestFn.invoke(RestFn.java:421)
at clojure.lang.Var.invoke(Var.java:419)
at clojure.lang.AFn.applyToHelper(AFn.java:163)
at clojure.lang.Var.applyTo(Var.java:532)
at clojure.main.main(main.java:37)
"
위의 소스는 int 타입(Clojure 언어의 int 타입은 C 언어의 long long 타입에 해당)의 제역을 받는다. int 타입은 -(2**63) ~ +(2**63 - 1) 범위의 정수 만을 처리할 수 있다. 그런 이유로 20 팩토리얼은 계산했지만 21 팩토리얼은 integer overflow 예외상황에 걸려 계산하지 못했다. 그래서 int 타입 대신 bigint 타입을 이용하는 팩토리얼 함수로 다시 구현해 보았다.
* bigint 타입으로 계산하는 재귀호출 팩토리얼 함수 구현 소스: facto-02.clj
;;; Filename: fact-02.clj
;;;
;;; (fact n) : a factorial function using a plain recursive call
;;;
;;; This fails to calculate 39533!.
;;;
;;; Execute: clj fact-02.clj
;;;
;;; Date: 2013. 2. 11.
;;; Author: pkim ((AT)) scripts ((DOT)) pe ((DOT)) kr
(defn fact [n]
(if (< n 2) 1 (* n (fact (- n 1))) ))
(printf "The number of digits of 3953! is %d\n" (.length (str (fact (bigint 3953))))) ;; Success
; (printf "The number of digits of 3954! is %d\n" (.length (str (fact (bigint 3954))))) ;; Fail to calculate
#_"
Output:
The number of digits of 3953! is 12505
"
위의 소스도 3954 팩토리얼은 계산하지 못했다. 이유는 제귀호츨 함수를 반복 호풀하다가 스택이 넘쳤기 때문이다. (함수를 호출힐 때 니기 매개변수로 넘긴 값 들이 모두 스택에 쌓인다.) 이번에는 (유사) 꼬리 재귀호출하는 함수로 다시 구현해 보았다.
* (유사) 꼬리 재귀함수 호출로 구현한 팩토리얼 함수 소스: facto-03.clj
;;;
;;; (fact n) : a factorial function, which is not a tail recursion in Clojure labguage.
;;;
;;; TThis fails to calculate 39533!.
;;;
;;; Execute: clj facto-03.clj
;;;
;;; Date: 2013. 2. 11.
;;; Author: pkim ((AT)) scripts ((DOT)) pe ((DOT)) kr
(defn fact [n]
(defn fact-aux [k acc]
(if (< k 2) acc (fact-aux (dec k) (* k acc))) )
(fact-aux n (bigint 1)))
(printf "10! = %s\n" (fact (long 10)))
(printf "20! = %s\n" (fact (long 20)))
(printf "22! = %s\n" (fact 22))
(printf "100! = %s\n" (fact 100))
(printf "The number of digits of 1000! is %d\n" (.length (str (fact (bigint 1000))))) ;; Success
(printf "The number of digits of 2000! is %d\n" (.length (str (fact (bigint 2000))))) ;; Success
(printf "The number of digits of 3000! is %d\n" (.length (str (fact (bigint 3000))))) ;; Success
(printf "The number of digits of 3005! is %d\n" (.length (str (fact (bigint 3005))))) ;; Success
(printf "The number of digits of 3009! is %d\n" (.length (str (fact (bigint 3009))))) ;; Success
(printf "The number of digits of 3036! is %d\n" (.length (str (fact (bigint 3036))))) ;; Success
(printf "The number of digits of 3075! is %d\n" (.length (str (fact (bigint 3075))))) ;; Success
(printf "The number of digits of 3090! is %d\n" (.length (str (fact (bigint 3090))))) ;; Success
(printf "The number of digits of 3095! is %d\n" (.length (str (fact (bigint 3095))))) ;; Success
(printf "The number of digits of 3096! is %d\n" (.length (str (fact (bigint 3096))))) ;; Success
; (printf "The number of digits of 3097! is %d\n" (.length (str (fact (bigint 3097))))) ;; Fail
; (printf "The number of digits of 3113! is %d\n" (.length (str (fact (bigint 3113))))) ;; Fail
#_"
Output:
10! = 3628800
20! = 2432902008176640000
22! = 1124000727777607680000
100! = 9332621544394415268169923885626670049071596826438162146859296389521759999
32299156089414639761565182862536979208272237582511852109168640000000000000000000
00000
The number of digits of 1000! is 2568
The number of digits of 2000! is 5736
The number of digits of 3000! is 9131
The number of digits of 3005! is 9149
The number of digits of 3009! is 9162
The number of digits of 3036! is 9256
The number of digits of 3075! is 9392
The number of digits of 3090! is 9445
The number of digits of 3095! is 9462
The number of digits of 3096! is 9466
"
위에서 유사라고 한 것은 C. C++, Java 등의 보통의 캄파일러 들은 저런 꼬리 재귀 호출을 만나면 while { .... } 반복문 처럼 동작하도록 컴파일하기 때문에 함수를 반복해서 호출하느라 스택이 넘쳐나는 일이 없지만 Clojure 는 그렇지 못하여 (소스의 모양은 꼬리재귀호출이라 하더라도) 일반 함수 처럼 매개변수로 남기는 값들을 스택에 쌓기 때문에 이전 소스 facto-02.clj 의 팩토리얼 함수와 처리 능력은 비슷하다.
Clojure 언어에서 꼬리 재귀호출 함수를 구현하려면 loop 과 recur 예약어를 써야한다. (Haskell, OCaml, F#, Scheme 언어 들에서는 loop 이 예약어가 아니지만, Clojure 언어에서는 loop 이 예약어로 되어 있다.) 다음 소스가 최종적으로 완성된 Clojure 언어의 꼬리 재귀호출 함수로 구현된 책토리얼 함수이다.
* (최종) 꼬리 재귀호출 팩토리얼 함수 구현 소스: facto-04.cli
;;;
;;; (fact n) : a factorial function using a tail recursive call in Clojure language.
;;;
;;; TThis can calculate 50000!.
;;; TThis can calculate 100000!, but slow.
;;;
;;; Execute: clj fact-04.clj
;;;
;;; Date: 2013. 2. 11.
;;; Author: pkim ((AT)) scripts ((DOT)) pe ((DOT)) kr
(defn fact [n]
(loop [k n
acc (bigint 1)]
(if (< k 2) acc (recur (dec k) (* k acc))) ))
(printf "10! = %s\n" (fact (long 10)))
(printf "20! = %s\n" (fact (long 20)))
(printf "The number of digits of 3097! is %d\n" (.length (str (fact (bigint 3097))))) ;; Success
(printf "The number of digits of 10000! is %d\n" (.length (str (fact (bigint 10000))))) ;; Success
(printf "The number of digits of 20000! is %d\n" (.length (str (fact (bigint 20000))))) ;; Success
(printf "The number of digits of 30000! is %d\n" (.length (str (fact (bigint 30000))))) ;; Success
(printf "The number of digits of 40000! is %d\n" (.length (str (fact (bigint 40000))))) ;; Success
(printf "The number of digits of 50000! is %d\n" (.length (str (fact (bigint 50000))))) ;; Success
(printf "The number of digits of 100000! is %d\n" (.length (str (fact (bigint 100000))))) ;; Success
#_"
Output:
10! = 3628800
20! = 2432902008176640000
22! = 1124000727777607680000
The number of digits of 1000! is 2568
The number of digits of 3097! is 9469
The number of digits of 10000! is 35660
The number of digits of 20000! is 77338
The number of digits of 30000! is 121288
The number of digits of 40000! is 166714
The number of digits of 50000! is 213237
The number of digits of 100000! is 456574
"
'프로그래밍 > Clojure' 카테고리의 다른 글
| Clojure 스크립트 소스 실행하기 (0) | 2013.02.10 |
|---|
