[algorithm] 꼬리 재귀는 무엇입니까?

Lua의 Programming 책에서 발췌 한이 글 은 Lua에서 꼬리 꼬리 재귀를 올바르게 만드는 방법 과 Lisp에도 적용되어야하는 이유를 보여줍니다.

꼬리를 호출 [꼬리 재귀] 전화로 옷을 입고 고토의 일종이다. 테일 호출은 함수가 마지막 동작으로 다른 것을 호출 할 때 발생하므로 다른 작업이 없습니다. 예를 들어 다음 코드에서 호출 g은 테일 호출입니다.

function f (x)
  return g(x)
end

f호출 후 g할 일이 없습니다. 이러한 상황에서는 호출 된 기능이 종료 될 때 프로그램이 호출 기능으로 돌아갈 필요가 없습니다. 따라서 꼬리 호출 후 프로그램은 호출 함수에 대한 정보를 스택에 보관할 필요가 없습니다. …

적절한 테일 콜은 스택 공간을 사용하지 않기 때문에 프로그램이 수행 할 수있는 “중첩 된”테일 콜의 수에는 제한이 없습니다. 예를 들어, 임의의 숫자를 인수로하여 다음 함수를 호출 할 수 있습니다. 스택을 오버플로하지 않습니다.

function foo (n)
  if n > 0 then return foo(n - 1) end
end

… 앞에서 말했듯이 테일 콜은 일종의 고토입니다. 따라서 Lua에서 적절한 테일 콜을 적용하는 것은 상태 머신을 프로그래밍하는 데 유용합니다. 이러한 응용 프로그램은 함수로 각 상태를 나타낼 수 있습니다. 상태를 변경하는 것은 특정 기능으로 이동하거나 호출하는 것입니다. 예를 들어 간단한 미로 게임을 생각해 봅시다. 미로는 북쪽, 남쪽, 동쪽 및 서쪽으로 최대 4 개의 문이있는 방이 여러 개 있습니다. 각 단계에서 사용자는 이동 방향으로 들어갑니다. 해당 방향으로 문이 있으면 사용자는 해당 방으로갑니다. 그렇지 않으면 프로그램이 경고를 인쇄합니다. 목표는 초기 방에서 마지막 방으로가는 것입니다.

이 게임은 현재 상태가 상태 인 일반적인 상태 머신입니다. 우리는 각 방마다 하나의 기능으로 그러한 미로를 구현할 수 있습니다. 우리는 꼬리 호출을 사용하여 한 방에서 다른 방으로 이동합니다. 4 개의 방이있는 작은 미로는 다음과 같습니다.

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

따라서 다음과 같이 재귀 호출을 할 때 알 수 있습니다.

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

재귀 호출이 수행 된 후에도 해당 함수에서 수행 할 작업 (1을 추가)이 있기 때문에 꼬리 재귀가 아닙니다. 매우 높은 숫자를 입력하면 스택 오버플로가 발생할 수 있습니다.

답변

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))