Lispex — 생각의 원형을 담는 언어

리스펙스와 같은 함수형 언어에서는 반복과 루프가 일반적으로 재귀를 통해 이루어집니다. 이 가이드는 재귀가 무엇인지, 그리고 일반적인 문제를 해결하기 위해 자신만의 재귀 함수를 작성하는 방법을 알려줍니다.

재귀란 무엇인가?

재귀는 간단하지만 강력한 아이디어입니다: 자기 자신을 호출하는 함수.

함수가 영원히 자신을 호출하는 것을 방지하려면, 재귀 함수는 두 가지 핵심 부분을 가져야 합니다:

기저 사례(Base Case): 함수에게 재귀를 멈출 시점을 알려주는 조건.
재귀 단계(Recursive Step): 함수가 자기 자신을 호출하는 부분으로, 기저 사례에 더 가까워지도록 약간 다른 입력값을 사용합니다.

고전적인 예제를 통해 이것이 어떻게 작동하는지 살펴봅시다.

예제 1: 팩토리얼 계산하기

숫자 n의 팩토리얼( n!로 표기)은 n까지의 모든 양의 정수의 곱입니다. 예를 들어, 5! = 5 * 4 * 3 * 2 * 1 = 120입니다.

다음은 팩토리얼을 계산하는 Lispex 재귀 함수입니다:

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

(factorial 5)  ; ⇒ 120

작동 방식

(factorial 3)을 호출하면, 인터프리터는 다음과 같이 동작합니다:

3 <= 1인가요? 아니요. 따라서 (* 3 (factorial 2))를 계산합니다.
이를 위해 (factorial 2)를 계산해야 합니다. 2 <= 1인가요? 아니요. 따라서 (* 2 (factorial 1))을 계산합니다.
이를 위해 (factorial 1)을 계산해야 합니다. 1 <= 1인가요? 예. 기저 사례에 도달하여 1을 반환합니다.
이제 2단계를 해결할 수 있습니다: (* 2 1)은 2입니다.
이제 1단계를 해결할 수 있습니다: (* 3 2)은 6입니다.

최종 결과는 6입니다.

예제 2: 리스트에 대한 재귀

재귀는 리스펙스에서 리스트를 "순회"하는 주요 방법입니다. 일반적인 패턴은 첫 번째 요소를 처리한 다음 리스트의 나머지 부분에 대해 재귀를 수행하는 것입니다.

리스트에 있는 모든 숫자를 합산하는 함수를 작성해 봅시다.

(define (sum-list lst)
  (if (empty? lst)
      0
      (+ (list-first lst) (sum-list (list-rest lst)))))

(sum-list (list 10 20 30))  ; ⇒ 60

작동 방식

(list 10 20 30)으로 sum-list가 호출됩니다.
리스트가 비어 있지 않으므로, (+ 10 (sum-list (list 20 30)))을 계산합니다.
(list 20 30)으로 sum-list가 호출됩니다.
리스트가 비어 있지 않으므로, (+ 20 (sum-list (list 30)))을 계산합니다.
(list 30)으로 sum-list가 호출됩니다.
리스트가 비어 있지 않으므로, (+ 30 (sum-list (list)))을 계산합니다.
빈 리스트 ()로 sum-list가 호출됩니다. 기저 사례에 도달하여 0을 반환합니다.
결과가 "거슬러 올라옵니다": (+ 30 0)은 30, (+ 20 30)은 50, 그리고 마지막으로 (+ 10 50)은 60입니다.

꼬리 재귀에 대한 참고

매우 깊은 재귀(예: (factorial 10000))의 경우, 간단한 재귀 패턴은 때때로 "스택 오버플로우"라는 오류를 유발할 수 있습니다. 이를 해결하기 위해 꼬리 재귀라는 기법을 사용할 수 있습니다.

함수가 꼬리 재귀적인 경우는 재귀 호출이 함수가 수행하는 바로 마지막 작업일 때입니다. 이를 통해 Lispex 인터프리터는 스택 오버플로우 오류를 피하기 위해 최적화(꼬리 호출 최적화, Tail Call Optimization)를 수행할 수 있습니다. 이는 종종 "누산기(accumulator)" 변수를 사용하여 달성됩니다.

다음은 팩토리얼 함수의 꼬리 재귀 버전입니다:

(define (factorial n)
  (let ((factorial-helper (lambda (n acc)
                             (if (<= n 1)
                                 acc
                                 (factorial-helper (- n 1) (* acc n))))))
    (factorial-helper n 1)))

(factorial 5)  ; ⇒ 120 (tail-recursive)

결론

재귀는 리스펙스의 기본 개념입니다. 기저 사례와 재귀 단계를 이해함으로써, 어떤 종류의 반복이나 루프도 깨끗하고 함수적인 방식으로 수행할 수 있습니다.

이제 자신만의 재귀 함수를 작성해 보세요! 예를 들어, 리스트의 길이를 재귀적으로 계산하는 my-length라는 함수를 작성할 수 있을까요?