LISP의 반복과 순환 ( Iteration and Recursion )

반복과 순환 (Iteration and Recursion)

 

반복 구조(Iteration Constructs)

 

# do 구조

형태 : 

(do (<var1 val1> <var-update1>) (<var2 val2> <var-update2>) …

(<test> <return-value>)

(<s-expressions>))

 

Val1 는 모두 평가되고 , 차례로 그에 대응한 변수 var1에 할당되는 초기값들이다 . 뒤에 오는 각 문들은 선택적 update문들인데 , 매번 반복될 때마다 var1가 어떻게 갱신되는가를 정의한다 .

반복되는 동안 변수들이 갱신된 후에 <test>가 평가되는데 , 만약 결과값이 non-nil 인 경우 return value가 평가되고 되돌려 진다 . 몸체를 형성하는 <s-expressions>들은 선택적이다 . 만약 상징문들이 있으면 탈출조건을 만날 때까지 각 반복마다 그것들이 수행된다 .

 

factorial예제를 통해서 이해해 보자 .

 

(defun factorial(n)

(do (count n (- count 1))

(product n (* product (- count 1)))

((equal 0 count) product)))

è  만약 n에 5가 들어온다고 가정해 보자 . 그러면 count값은 5로 초기 설정이 되며 ,product또한 5로 설정된다 . 마지막 라인의 equal 조건을 보면 nil이기 때문에 다시 do로 올라간다 . count는 -1의 update를 가지기 때문에 count값은 4로 할당되고 , product에는 전에 있었던 5에 곱하기 4가 된다 . 이 값은 update를 통해 product에 할당되고 , 마지막 라인의 조건과 부합하지 않기 때문에 다시 do로 올라간다 . 다시 count는 3이 되며 , product에는 5*4가 있는데 , count의 값 3이 다시 곱해지고 이 값이 다시 할당product에 할당된다 . … 이렇게 count가 0과 똑같아 질때까지 반복이 되다가 0이 되었을 때 product가 반환된다 . product의 값을 보면 5 * 4 * 3 * 2 * 1 을 확인할 수 있을 것이다 .

간략하게 정리를 해보자면 , do 의 구조는 초기인수값을 할당하고 , update문을 통해서 반복될 때 인수값이 어떻게 할당할지 정해주는 구조이다.

 

 

순환 ( Recursion )

 

많은 문제들을 위해 순환 ( recursion ) 이 하나의 자연스러운 문제해결 방법이 되고 있다. 특히 그러한 문제들은 수학 논리 문제에서 많이 발생하는데 , 순환의 사용은 종종 프로그램을 보다 우아하고 단순하게 해 준다 . 순환함수는 문제를 연속적으로 보다 단순한 과정으로 축소시키기 위해 그 자신을 호출하는 함수이다. 순환함수는 하나의 종결조건과 순환적 절차를 필요로 한다.

 

Factorial 순환의 예를 통해서 확인해보자.

 

팩토리얼 내의 순환절차는 n와 factorial(n-1)의 곱이다. 종결조건으로는 n = 0 이 되었을 때이다.

 

(defun factorial(n) (cond ((zerop n) 1) ( t (* (factorial(- n 1))))))

è  Zerop 가 종결조건이고 , t 라인이 순환절차이다.

 

또 다른 예를 보자 .

(defun newmember (el lst)

(cond ((null lst) nil) ((equal el (car lst)) lst)

(t (newmember(el (cdr lst)))))

 

만약 원소 c와 리스트(a b c d)가 newmember 함수를 호출할 때 인수로 주어진다면 , c는 el에 한정되고 , (a b c d)는 lst에 한정된다 . 이렇게 한정하고 나서 cond내의 첫번째 조건 체크를 하게 되는데 , 이 경우 lst가 null이 아니므로 수행문이 수행되지 않고 다음 문장으로 넘어가게 된다.

두번째 조건 체크가 이루어 지게 되는데 , 이것 역시 el에 저장된 c가 lst의 car인 a와 같지 않으므로 거짓으로 판명이 나게 된다. Cond 구조의 마지막 조건 체크는 무조건 참으로 판명되고 , 새로운 인수값 el에는 c가 , lst에는 lst의 cdr (b c d)가 새로 저장되어 newmember를 호출 하게 된다 . 앞에서와 마찬가지로 조건절에 다 걸리지 않으므로 el 에는 c가 , cdr의 ( c d ) 가 다시 newmember를 호출하게 된다 . 이 때 호출할 때 cond의 두번째 조건에 걸리게 되므로 lst를 반환 하게 되고 , (c d)가 되돌려 지게 되는 것이다.