SICP - 1.2.2 여러 갈래로 되도는 프로세스

여러 갈래로 되도는 프로세스의 예시로 피보나치 수열을 살펴보자.

(define (fib n)
	cond((= n 0) 0
		(= n 1) 1)
		(else (+ fib(- n 1) fib(- n 2)))))

• 피보나치 수열을 위와 같이 정의한다면, fib 5 만 구하더라도 같은 fib 2 값을 3번, fib 3 값을 2번 반복해서 구하는 과정을 거쳐야한다.

• n 이 커짐에 따라 이 프로세스가 펼쳐지는 단계(step) 는 지수 비례로 증가하게 된다.

• 반면, 메모리를 차지하는 부분은 n과 선형 비례한다. (계산이 펼쳐지더라도 계산하는 시점에서는 자신보다 위의 fib 값만 알면 되므로)

피보나치 수열을 반복 프로세스로 구현해보자.

(define (fib n)
	(define (fib-iter a b count)
		(if (= count 0)
			b
			(fib-iter (+ a b) a (- count 1))))
(fib-iter 1 0 n))

• 위 방식에서는 메모리와 계산 프로세스가 모두 n에 선형 비례함을 알 수 있다.

여러 갈래로 되도는 프로세스 vs 반복 프로세스

• 성능적으로 반복 프로세스가 우위에 있으므로 되도는 프로세스는 쓸모 없을까?

• 여러 갈래로 되도는 프로세스는 수가 아닌 계층 구조 데이터를 다루거나, 수를 다룬다 하더라도 계산 프로세스를 훨씬 이해하기 쉽게 작성할 수 있게 해준다.

연습문제

1.11

n<3 일때 f(n) = n 이고, n>=3 일때 f(n) = f(n-1) + f(n-2) + f(n-3) 인 프로세스를 되도는 프로세스와 반복 프로세스로 작성하라.

되도는 프로세스

(define (f n)
	((if (< n 3)
		n
		(+ (f (- n 1)) (f (- n 2)) (f (- n 3))))))

반복 프로세스

(define (f n)
	(iter 2 1 0 n))

(define (iter a b c count)
	(cond ((= count 0) c)
		((= count 1) b)
		((= count 2) a)
		(else (iter (+ a b c) a b (- count 1)))))

1.12

파스칼 삼각형을 만드는 프로시저를 되도는 프로세스가 나오도록 만들어라.

(define (pt h n)
	(cond ((= n 0) 1)
		((= n h) 1)
		(else (+ (pt (- h 1) (- n 1) (pt (- h 1) n)))))

1.13

블로그를 참고하자.

https://studyingeugene.github.io/sicp/chapter-1/exercise-1-13/