2024-01-12 18:39

SICP - 1.2.1 되돌리거나(recursive) 반복하는(iterative) 프로세스

프로시저란

프로세스란

프로그램이란

N 펙토리얼을 구하는 과정을 생각해보자.

(define (factorial n)
	if (= n 1)
		1
		(* n (factorial (- n 1))))

인자를 먼저 계산하므로 6! 을 계산하기 위해서는 6! = 6x5! = 6x5x4! ... = 6x5x4x3x2x1 = 6x5x4x3x2 = ... = 720 의 과정을 거쳐 계산 값이 도출될 것이다.
프로세스가 바로 계산을 하지 않고 계산을 뒤로 미루어 한번에 계산하는데, 계산에 필요한 값들을 저장하고 있어야 한다. n 이 늘어날수록 저장할 정보가 선형으로 늘어나는데, 이 프로세스를 선형 재귀 프로세스라 한다.

(define (factorial n)
	(define (iter product counter)
		(if (> counter n)
			product
			(iter (* product counter) (+ counter 1))))
(iter 1 1))

위 계산은 product 에 값을 저장하며 계산하므로 factorial 6 = iter 1 1 = iter 1 2 = iter 2 3 ... = iter 720 7 6 = 720 으로 바로 값이 도출된다.
프로세스가 상태 변수를 두고 반복마다 바뀌는 계산 상태를 간추려 하나의 변수에 저장하고 있다. n 이 늘어날수록 거치는 단계 수가 선형으로 늘어나는데, 이 프로세스를 선형 반복 프로세스라 한다.

두 프로세스가 실행 도중에 멈출 경우 재귀 프로세스는 이전까지의 계산 정보들을 모두 알아야 지만, 반복 프로세스는 상태 변수만 알면 계산을 이어갈 수 있다.

재귀 프로세스 vs 재귀 프로시저

tail-recursive 기법

연습 문제

1.9 두 프로시저가 재귀 프로세스인지, 반복 프로세스인지 (+ 4 5) 의 계산 프로세스를 통해 밝혀라

a)
(define (+ a b)
	if (= a 0)
		b
		(inc (+ (dec a) b)))

b)
(define (+ a b)
	if (= a 0)
		b
		(+ (dec a) (inc b)))

답:

a의 계산 프로세스는 (+ 4 5) = (inc (+ 3 5)) = (inc (inc (+ 2 5)))... 처럼 계산을 뒤로 미루는 재귀 프로세스이다.

b의 계산 프로세스는 (+ 4 5) = (+ 3 6) = (+ 2 7) ... 처럼 계산을 상태변수에 저장하며 바로 하는 반복 프로세스이다.

1.10

다음은 애커만 함수를 나타낸 프로시저이다.

(define (A x y)
	(cond ((= y 0) 0)
			((= x 0) (* 2 y))
			((= y 1) 2)
			(else (A (- x 1) (A x (- y 1))))))

아래 식의 값은 무엇인가?

(A 1 10)

(A 2 4)

(A 3 3)

다음 프로시저는 수학적으로 어떤 의미를 갖는가?

a)
(define (f n) (A 0 n))
b)
(define (g n) (A 1 n))
c)
(define (h n) (A 2 n))

답:

(A 1 10) = (A 0 (A 1 9)) ... = (A 0 (A 0 ... (A 0 (A (1 1))))) = (A 0 (A 0 ... (A 0 2)) = 2^10

(A 2 4) = (A 1 (A 2 3)) = (A 1 (A 1 ... (A 1 (A(2 1))))) = (A 1 (A 1 ... (A 1 2))) = 2^16

(A 3 3) = (A 2 (A 3 2)) = (A 2 (A 2 (A 3 1))) = (A 2 (A 2 2)) = (A 2 4) = 2^16

a) (A 0 n) 의 경우 x = 0 이면 2*n 을 반환하므로 2n이다.

b) (A 1 n) 은 2 를 n번 곱하게 연산되므로 2^n이다.

c) (A 2 n) 은 (A 1 (A 2 n-1)) = (A 1 (A 1 ... (A 1 1))) 이므로 2^(2^(2^...)) 을 n번 반복한 식이 된다.

프로세스

재귀 프로세스