SW 마에스트로 멘토님의 추천으로 SICP 를 공부중이다. 책에서 사용하는 언어는 Scheme이라고 하는 Lisp의 dialect인데, 지금까지 배운 언어들과는 꽤 다르지만 재밌는 언어다.
연습문제 1.9
scheme 에는 for, while 같은 반복문 문법이 따로 존재하지 않는다. 그럼 반복 프로세스를 어떻게 구현하는가?
꼬리 재귀 (tail recursion)를 통해 scheme 실행기가 반복 프로세스를 반들어낸다.
; 재귀 프로세스
(define (+ a b)
(if (= a 0)
b
(inc (+ (des a) b))))
; 반복 프로세스
(define (+ a b)
(if (= a 0)
b
(+ (des a) (inc b))))
아래의 프로세스는 재귀처럼 보이지만 반복 프로세스이다!
연습문제 1.10
애커만 함수 프로시저를 수학적으로 설명하는 문제이다.
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- 1 x)
(A x (- 1 y))))))
(define (f n) (A 0 n))
프로시저 f 는 f(n) = 2 * n 의 간단한 함수로 나타낼 수 있다.
(define (g n) (A 1 n))
프로시저 g 는 g(n) = 2 ^ n 의 함수이다.
(define (h n) (A 2 n))
프로시저 h 는 h(n) = 2 ^ h(n - 1) 의 점화식을 가지는 함수로, n = 4의 경우 2 ^ (2 ^ (2 ^ 2)) 의 값을 가지게 된다.