스크립팅
기초
반복

단순 재귀

재귀는 원래 문제의 더 작은 하위 문제를 해결하기 위해 함수가 자신을 호출하는 Scheme의 강력한 개념입니다. 단순 재귀 패턴에는 재귀를 중지하는 기본 사례와 문제를 줄이기 위한 재귀 사례가 포함됩니다.

재귀 함수의 일반적인 구조는 다음과 같습니다.

(define (function-name args)
  (if (base-condition)
    base-result
    (recursive-call)))
  • 기본 조건: 재귀를 중지합니다.
  • 기본 결과: 기본 조건이 충족되었을 때 반환되는 값입니다.
  • 재귀 호출: 계산을 기본 사례에 더 가깝게 이동하는 수정된 인수를 사용하여 함수 자체에 대한 호출입니다.

예: 숫자의 합(1~n)

1부터 n까지의 숫자의 합을 계산하는 간단한 재귀 함수:

(define (sum-to-n n)
  (if (= n 0)                  ; Base case: stop when n is 0
    0                          ; Base result: sum is 0
    (+ n (sum-to-n (- n 1))))) ; Recursive call: sum current n with result of smaller problem

작동 방식: 분해 및 재조립

재귀는 원래 문제를 더 작은 조각으로 분해하여 작동합니다. 함수를 호출할 때마다 한 부분을 처리하고 나머지 부분을 전달합니다. 가장 간단한 사례에 도달하면 계산이 완료되면서 결과가 다시 조립됩니다.

합-n 3의 단계별 추적

  1. 초기 호출: sum-to-n 3 → (+ 3 (합계를 n 2))

  2. 두 번째 호출: n으로 합산 2 → (+ 2 (합계를 n으로 1))

  3. 세 번째 호출: 합계 n 1 → (+ 1 (합계를 n으로 0))

  4. 기본 사례: n에 대한 합계 0 → 0

최종 결과 재조립

가장 간단한 사례가 해결되면 계산의 각 계층이 완료됩니다.

  1. 합을 n으로 0하면 0이 됩니다.
  2. 합계 n 1은 (+ 1 0) = 1이 됩니다.
  3. 합계 n 2는 (+ 2 1) = 3이 됩니다.
  4. 합계 n 3은 (+ 3 3) = 6이 됩니다.

예: 목록의 각 요소 인쇄

다음은 목록의 모든 요소를 인쇄하는 간단한 재귀 함수입니다.

(define (print-elements lst)
  (if (null? lst)
    (lumi-message "done")
    (begin
      (lumi-message (number->string (car lst))) ; Print the first element
      (print-elements (cdr lst)))))             ; Process the rest of the list
  • 기본 사례: 목록이 비어 있으면(null? lst) 재귀를 중지합니다.
  • 재귀 사례: 첫 번째 요소(car lst)를 인쇄한 다음 목록의 나머지 부분(cdr lst)에서 함수를 호출합니다.

사용 예 

(print-elements (list 1 2 3))

출력:

  • “1”
  • “2”
  • “3”

결과: “완료”

작동 방식

  1. 함수는 car를 사용하여 목록의 첫 번째 요소를 검색하고 이를 처리합니다.
  2. 그런 다음 목록의 나머지 부분(cdr)을 사용하여 자신을 호출합니다.
  3. 이 프로세스는 목록이 비어 있을 때까지(null? lst) 반복됩니다.

요약

  • 단순 재귀는 다음으로 구성됩니다.
    1. 기본 사례: 재귀를 중지합니다.
    2. 재귀 사례: 기본 사례에 대한 문제를 줄입니다.
  • 각 재귀 호출은 완료를 향해 계산을 진행합니다.
  • 기본 사례에 도달하면 재귀가 완료되면서 결과가 결합됩니다.

재귀는 문제의 구조를 반영하고 명확하고 논리적인 흐름을 제공합니다. 무한 재귀를 방지하려면 항상 기본 사례를 보장하세요.

각각에 대해하다