Chapter 1.2.1)

되돌거나(recursion) 반복하는(iteration) 프로세스

---

먼저 다음처럼 사디리곱(factorial) 함수가 있다고 하자.

n! = n * (n-1) * (n-2) 

사다리곱을 계산하는 여러 방법 가운데 하나는, 0보다 큰 수 n이 있을 때 n!의 값이 n과 (n-1)!의 곱과 같다는 데서 비롯한 것이다. 

n! = n * [(n-1) * (n-2)] = n * (n-1)!

그러므로 (n-1)! 을 계산하는 값에 n을 곱하면 n! 값을 얻을 수 있다. 여기에 1!이 1이라는 사실만 보태서 계산 방법을 그대로 프로시저로 옮겨 쓰면, 다음과 같다.

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

이 프로시저로 6! 값을 구해 보면, 1.1.5절에 나온 맞바꿈 계산법(substitution)에 따라 아래 그림과 같은 프로세스를 그려낼 수 있다.

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1))))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

사다리곱을 달리 계산하는 방법이 없는지 살펴보자. n!은 1에 2를 곱한 값에 다시 3, 4를 차례로 곱하면서 n에 이를 때까지 같은 일을 되풀이하는 것이다. 다시 말해서, 지금까지 곱한 값을 product라 놓고 1부터 n까지 헤아리는 변수를 counter라 할 때, 한 단계를 거칠 때마다 counter와 product를 아래 규칙에 따라 바꾸는 것으로 볼 수 있다.

product ← counter * product
counter = counter + 1

이리 하면 counter 값이 n에 이르렀을 때 product 값은 n!이 된다. 이런 방법으로 사다리곱을 구하는 프로시저를 만들면 아래와 같다.

(define (factorial n)
     (fact-iter 1 1 n))
     
(define (fact-iter product counter max-count)
	(if (> counter max-count)
    	product
        (fact-iter (* counter product)
        		   (+ counter 1)
                    max-count)))

(factorial 6)
(fact-iter	1 1 6)
(fact-iter	1 2 6)
(fact-iter	2 3 6)
(fact-iter	6 4 6)
(fact-iter  24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

앞에서 했던 대로, 이 프로시저로 6! 값을 구한다고 할 때, 맞바꿈 계산법에 따라 위와같은 펼쳐지는 프로세스를 그릴 수 있다. 같은 일을 하는 두 프로세스를 견주어 보자. 둘 다 같은 수학 함수를 나타낸 프로시저고, n!을 계산하는 단계가 n에 비례하여 많아진다는 점에서 두 프로세스는 크게 다르지 않다. 두 프로세스에서 곱셈을 하는 차례마저 같다. 하지만, 두 프로세스의 '꼴(shape)'을 놓고 보면 펼쳐지는 방식이 서로 매우 다르다.

첫 번째 프로세스부터 살펴보자. 첫 번째에서는 맞바꿈 계산법에 따라 식이 옆으로 폋쳐진 다음에 다시 줄어드는 꼴을 볼 수 있다. 프로세스가 곧바로 연산을 하지 않고 자꾸 미루어 놓은(deffered operation)탓에 식이 옆으로 늘어나다가, 곱셈 연산을 하면서 줄어들기 시작한다. 이처럼 곧바로 셈하지 못하고 미루어 놓은 연산이 끈처럼 이어지는 게 되도는 프로세스(recursive process)의 특징이다. 이런 프로세스를 돌릴 때, 실행기는 미뤄둔 연산을 모두 쥐고 있다가 다시 되밟을 수 있도록 해야 한다. n! 값을 구하면서 미루어 둔 곱셈 끈의 길이, 곧 실행기가 쥐어야 할 정보의 크기는, 셈하는 데 거치는 단계 수와 마찬기지로 n에 비례하여 나란히(선형으로) 자라난다.  그래서 이런 프로세스를 두고 선형 재귀 프로세스(linear recursive process)라 한다.

 이와 달리 두번째 프로세스는 늘거나 줄지 않는다. n의 크기와 관게없이 product, counter, max-count 변수에 단게마다 구한 값만 넣어주면 그만이다. 이것을 반복하는 프로세스(iterative process)라 하는데, 보통 반복하는 프로세스에는 정해진 상태변수(state variable)가 있어서 반복할 때마다 바뀌는 계산 상태를 간추려서 기록해둘 수 있고, 계산 단계가 넘어갈 때마다 상태변수 값을 고쳐 쓰는 규칙이  있으며, 계산을 끝낼 조건을 따지는 마무리 검사 과정도 있다. 이 보기에서 보듯이, n!값을 구하는 데 거치는 단계 수가 n에 비례하여 나란히 자라날 때, 이런 프로세스를 선형 반복 프로세스(linear recursive process)라 한다. 

두 프로세스를 달리 견주어 보자. 반복하는 프로세스에서는 프로그램 변수가 프로세스 단계마다 어떤 상태에 있는지 정확하게 나타내기 때문에, 계산을 잠시 멈추더라도 세 변수 값을 알기만 하면, 실행기가 곧바로 계산을 이어갈 수 있다. 하지만, 되도는 프로세스는 그렇지 않다. 프로세스 안에 상태변수(state variable)도 없을뿐더러, 뒤로 미뤄 둔 연산의 끈을 이어가면서 '어디까지 계산했는지' 알아내려면, 실행기 속에 '숨은' 정보가 더 들어 있어야 한다. 끈이 길수록 그런 정보가 더 많아지는 것은 더 말할 나위가 없다.

반복과 되돌기를 견줄 때, 되도는 프로세스와 되도는 프로시저를 헷갈리지 않도록 조심하자. 프로시저가 되돌아간다는 말은 프로시저를 정의하는 글(식) 속에서 자신을 (곧바로든 에두르든) 불러 쓴다는 뜻이다. 하지만, 프로세스가 줄지어 되돌며 돌아간다는 말은 프로시저를 정의한 글(식)이 그렇다는 게 아니라, 진짜 계산이 그런 꼴로 펼쳐진다는 뜻이다. 앞 보기에서 fact-iter 프로시저는 된도는 프로시저지만 그 프로세스는 계산을 반복하고 있다. 되도는 프로시저가 반복하는 프로세스를 만들어 낸다는 게 헛갈릴지 모르나, 사실이 그렇다. fact-iter 프로시저가 만드는 프로세스는 계산 상태를 상태변수(state variable) 세 개로 잡아낼 수 있기 때문에, 실행기는 변수 세 개 만 들고 있어도 계산을 이어나가는데 모자람이 없다. 프로세스와 프로시저를 헛갈리는 까닭 중 하나는 보통 널리 쓰는 언어 번역기 내부에서 되도는 프로시저를 해석할 때, 그 프로세스가 반복하는 것인지 따져보지 않고 프로시저를 불러 쓰는 횟수에 비례하는 만큼 기억 공간을 쓰도록, 곧 되도는 프로세스만 내놓게끔 처리하기 때문이다. 그러므로 그런 언어에서는 do, repeat, until, for, while 따위 '반복하는 특별한 형태(special form)'를 써야만 반복 프로세스를 나타낼 수 있다. scheme 처리 기계에는 이런 흠이 없다.(자세한 내용은 5장에서 다룸) 
반복하는 프로세스를 (그 프로세스의 프로시저가 되도는 것이라 해도) 정해진 기억 공간만 써서 돌아가게 할 수 있다. 이를 두고, 꼬리에서 되돌아가도록(tail recursive) 실행기를 만들었다고 한다. 꼬리 되돌기(tail-recursive)라는 기법을 쓰면, 프로시저를 불러 쓰는 문법만으로도 반복할 일을 얼마든지 나타낼 수 있기 때문에, 특별한 형태가 굳이 필요 없고 따로 있다 하더라도 그저 달콤한 문법(syntactice sugar)으로 쓰일 뿐이다.

 

연습문제 1.9

다음 두 프로시저는 모두 0보다 큰 정수 두 개를 더하는 일을 하는데, 인자에 1을 더하는 inc 프로시저와 인자에서 1을 빼는 dec 프로시저를 가져다 쓴다.

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

맞바꿈 계산법에 따라 두 프로시저가 (+ 4 5)를 계산하는 프로세스(과정)를 밝혀라.
이 프로세스는 반복(iteractive)하는가? 아니면 되도는가(recursive)?

 

(+ 4 5)
(inc (+ 3 5))
(inc (inc + 2 5)))
(inc (inc (inc + 1 5))))
(inc (inc (inc inc + 0 5)))))
(inc (inc (inc (inc + 5))))
(inc (inc (inc  6)))
(inc (inc 7))
(inc 8)
9

첫번째 define은 recursive process이다.
recursive process의 특징인 곧바로 계산하는게 아닌 옆으로 늘어지게 된다.

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

두번째 define은 iteractive process이다.
곧바로 게산하는 iteractive process의 특징을 볼 수 있다.

언뜻보기엔 두개다 recursive call을 해서 recursive process처럼 보일수 있지만 
명백하게 차이가 존재한다 반복과 되돌기의 차이점을 알아두면 되겠다.