리스프(LISP) 재귀 함수 구현해보자

리스트(LISP)로 재귀 함수

이제 만들어볼 함수는 리스트의 합을 구하는 재귀 함수이다. 리스트는 재귀 함수와 궁합이 잘 맞는다.

 

재귀 함수가 작동하는 흐름

• 함수의 이름은 sum-of-list로 하고, 길이가 n인 리스트를 입력으로 받아 그 총합을 반환하는 함수를 작성한다.
• 구체적인 입력 인자로 [1, 2, 3]과 같이 세 개의 값으로 구성된 리스트를 생각해 보자.
• sum-of-list([1,2,3]) = 1 + sum-of-list[2, 3]이다.
• 위의 식을 일반화하면 다음과 같이 된다. sum-of-list = list의 첫 번째 요소 + sum-of-list(첫 번째 요소를 제외한 리스트)
• 종료 조건은 입력 인자가 빈 리스트일 때 0을 반환하면 된다.

해당 내용을 코드로 작성해 보자.

(defun sum-of-list (input-list) 
    (if (null input-list) 
        0 
        (+ (CAR input-list) (sum-of-list (CDR input-list)))))

>> (sum-of-list '(1 2 3 4 5))
15

 

함수의 정의를 살펴보면, 제일 먼저 null이라는 내장 함수로 인자로 전달된 리스트가 빈 리스트인지를 확인한다.

 

(if (null input-list)) 0

 

빈 리스트면 0이라는 값을 반환하고, 그렇지 않으면 현재 리스트의 첫 번째 값(CAR)과 나머지 리스트(CDR)를 인자로 재귀 호출하여 얻은 값을 더하여 리턴한다.

 

(+ (CAR input-list) (sum-of-list (CDR input-list)))

 

여기서 CAR과 CDR이 사용되는데, CAR은 리스트의 첫 번째 값을 반환하며, CDR은 리스트의 첫 번째 요소를 제외한 리스트를 반환한다.

 

>> (CAR '(1 2 3))
1
>> (CDR '(1 2 3))
(2 3)

 

리스트가 재귀 함수로 다루기가 쉬운 이유는 리스트의 모든 요소가 CAR(첫 번째 요소)과 CDR(나머지 리스트)로 구성되어 있기 때문이다. 따라서 재귀 함수의 종료 조건은 입력 리스트가 빈 리스트일 때로 하고, 재귀 호출을 할 때는 CDR을 인자로 넘기면 리스트를 쉽게 전부 탐방할 수 있다. 앞서 함수형 언어에서는 for문 대신에 재귀 함수를 사용한다고 했는데, for문처럼 리스트를 전부 출력하는 재귀 함수는 다음과 같다.

 

(defun print-all (input-list)
    (if (null input-list) 
        "finish"
        (progn
            (print (CAR input-list))
            (print-all (CDR input-list)))))

>> (print-all2 '(1 2 3 4 5))

1
2
3
4
5
"finish"

 

위 코드에서 확인할 수 있듯이, 재귀 함수로 리스트를 다룰 때는 다음 두 가지 규칙을 기억하면 된다.

 

첫째, 종료 조건은 입력 리스트가 빈 리스트일 때로 한다.

둘째, 입력 리스트의 CDR을 인자로 재귀 호출한다.

 

리스트의 최댓값 구하기

이번에는 주어진 리스트의 최댓값을 구하는 함수를 작성해 보자.

 

재귀 함수가 작동하는 흐름

• 함수의 이름은 max-of-list로 하고, 길이가 n인 리스트를 입력으로 받아 그 최댓값을 반환하는 함수를 작성할 것이다.
• 구체적인 입력 인자로 [1, 2, 3]과 같이 세 개의 값으로 구성된 리스트를 생각해 보자.
• max-of-list([1, 2, 3]) = max(1, max-of-list([2, 3]))다.
• 위의 식을 일반화하면 다음과 같이 된다. max-of-list(list) = max(list의 첫 번째 요소, max-of-list(리스트의 첫 번째 요소를 제외한 리스트))
• 종료 조건은 길이가 1인 리스트에 대해 하나 있는 그 요소를 반환하면 된다.

(defun max-of-list (input-list)
    (cond
        ((null input-list) "NON SENSE")
        ((= 1 (list-length input-list)) (CAR input-list)) 
        ((< 1 (list-length input-list)) 
            (max (CAR input-list) (max-of-list (CDR input-list))))))

>> (max-of-list '(7 5 3 1 6 9 4))
9

 

리스트에 임의의 숫자가 있는지 확인하는 재귀 함수

재귀 함수가 작동하는 흐름

• 함수의 이름은 is-exist로 하고, 길이가 n인 리스트와 숫자를 입력으로 받아서 해당 숫자가 리스트에 존재하는지 확인하는 함수를 작성할 것이다.
• 구체적인 입력 인자로 [1, 2, 3]과 같이 세 개의 값으로 구성된 리스트와 정수 3을 생각해 보자.
• is-exist([1, 2, 3] 3) = eq(3 CAR([1, 2, 3]))
• 위의 식을 일반화하면 다음과 같이 된다. is-exist(list num) = eq(num, list의 첫번째 요소) 아니면 is-exist(list의 첫 번째 요소를 제외한 리스트 num)
• 종료 조건은 리스트가 null 이 될 때이다.

(defun is-exist (input-list num)
  (cond
    ((null input-list) "no")                ; 리스트가 비어 있으면 "no"를 반환
    ((eq (car input-list) num) "yes")       ; 리스트의 첫 번째 요소가 num과 같으면 "yes"를 반환
    (t (is-exist (cdr input-list) num))))   ; 그렇지 않으면 리스트의 나머지 요소에 대해 재귀 호출

 

리스트를 반환하는 재귀 함수

지금까지 살펴본 재귀 함수의 반환값은 전부 숫자였다. 하지만 함수형 언어에서는 리스트를 인자로 받아서 새로운 리스트를 반환하는 재귀 함수 패턴도 많이 사용된다.

 

(defun add-one-to-list (input-list)
    (if (null input-list) 
        NIL
        (cons (+ 1 (CAR input-list)) (add-one-to-list(CDR input-list)))))

>> (add-one-to-list '(1 2 3 4 5))
(2 3 4 5 6)

 

이처럼 리스트에 재귀 함수를 적용해서 새로운 리스트를 반환하는 코드를 작성하는 요령은 다음과 같다.

• 종료 조건은 입력 리스트가 빈 리스트일 때로 한다.
• cons 함수를 사용해서 리스트의 첫 번째 요소를 가공한 값을 재귀 호출하여 얻은 리스트를 추가한다.