플레이그라운드
(리스펙스)
ENRUKO

재귀

리스펙스에서 재귀 함수를 작성하고 전통적인 루프 없이 리스트를 순회하는 방법을 설명합니다.

이전 문서입니다. 리스트의 합을 구하는 과정을 따라가려면 현재 재귀 가이드를 읽으세요. 꼬리 호출 규칙은 올바른 꼬리 호출과 재귀에서 확인하세요.

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

재귀란 무엇인가?

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

함수가 영원히 자신을 호출하지 않으려면 재귀 함수에 두 가지 핵심 부분이 필요합니다.

  1. 기저 사례(Base Case): 함수에게 재귀를 멈출 시점을 알려주는 조건.
  2. 재귀 단계(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)을 호출하면 인터프리터는 다음과 같이 동작합니다.

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

최종 결과는 6입니다.

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

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

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

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

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

작동 방식

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

꼬리 재귀에 대한 참고

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

함수가 꼬리 재귀적인 경우는 재귀 호출이 함수가 수행하는 바로 마지막 작업일 때입니다. 이를 통해 리스펙스 인터프리터는 스택 오버플로우 오류를 피하기 위해 꼬리 호출 최적화를 수행할 수 있습니다. 이는 보통 누산기 변수를 사용해 만듭니다.

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

LISPEX
(define (factorial n)
  (letrec ((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라는 함수를 작성할 수 있을까요?