재귀

각 예제의 코드 전체를 플레이그라운드에서 실행하세요. 코드 아래에 결과를 함께 실었습니다.

숫자 네 개 더하기

(let loop ((xs (list 1 2 3 4)) (sum 0))
  (if (null? xs)
      sum
      (loop (cdr xs) (+ sum (car xs)))))

10

let 뒤에 붙인 이름 loop로 본문에서 자기 자신을 호출할 수 있습니다. 이 문법을 이름 있는 let이라고 합니다. 프로시저가 자기 자신을 호출하는 것을 재귀라고 합니다.

xs에는 아직 더하지 않은 항목이 들어 있습니다. 매개변수 sum은 지금까지 구한 합입니다. 이렇게 중간 결과를 다음 호출에 넘기는 매개변수를 누산기라고 합니다.

null?은 빈 리스트에 참을 반환합니다. xs가 비면 프로시저는 다시 호출하지 않고 sum을 반환합니다. 이처럼 재귀를 끝내는 경우를 기저 사례라고 합니다.

재귀 호출마다 첫 항목을 뺀 리스트인 (cdr xs)를 넘깁니다. 따라서 길이가 유한한 올바른 리스트는 기저 사례에 도달합니다. 처음부터 빈 리스트를 넣으면 합의 초깃값인 0을 반환합니다.

꼬리 호출 찾기

다음 loop 호출 전에 인자인 (cdr xs)와 (+ sum (car xs))를 계산합니다. 호출 결과를 그대로 현재 호출의 결과로 반환합니다. 돌아온 뒤에 할 덧셈이 없습니다.

이 자리에 있는 호출을 꼬리 호출이라고 합니다. 리스펙스는 현재 호출의 연속을 재사용합니다. 연속은 호출이 반환한 뒤 이어서 할 일입니다. 꼬리 호출을 반복해도 결과를 기다리는 호출의 깊이는 일정하게 유지됩니다.

각 항목을 처리하는 계산은 계속 필요합니다. 실행 시간과 데이터 메모리 사용량은 프로그램과 입력에 따라 달라지며 자원 한도도 계속 적용됩니다.

같은 반복을 do로 쓰기

(do ((rest (list 1 2 3 4) (cdr rest))
     (sum 0 (+ sum (car rest))))
    ((null? rest) sum))

10

각 변수에는 초깃값과 다음 값을 적습니다. do는 단계마다 현재 rest와 sum으로 두 변수의 다음 값을 계산합니다. rest가 비면 sum을 반환합니다.

리스펙스는 do를 꼬리 호출을 쓰는 재귀 반복으로 바꿉니다. 종료 조건 뒤의 결과 식을 생략하면 반환하는 값은 0개입니다. 전체 문법은 조건 쓰기에서 확인하세요.

입력 바꿔 보기

첫 예제의 입력 리스트에 5를 추가하면 결과는 무엇일까요? 재귀 호출은 여전히 꼬리 호출일까요?

재귀 호출 뒤의 계산을 누산기로 바꾸는 방법은 올바른 꼬리 호출에서 다룹니다. 두 프로시저가 서로를 호출하는 상호 재귀도 함께 설명합니다.

리스트를 처리할 기존 프로시저를 찾는다면 고차 프로시저 참조를 보세요.