모든 재귀를 반복으로 전환 할 수 있습니까?

Question

ㅏ 레딧 스레드 분명히 흥미로운 질문을 제기했습니다.

꼬리 재귀 함수는 사소하게 반복 함수로 변환 될 수 있습니다. 다른 것들은 명시 적 스택을 사용하여 변환 할 수 있습니다. 할 수 있다 모든 재귀가 반복으로 변형됩니까?

게시물의 (카운터?) 예는 쌍입니다.

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))

Answer 1

항상 재귀 기능을 반복적 인 기능으로 바꿀 수 있습니까? 그렇습니다. 절대적으로, 그리고 교회-징후 논문은 기억이 봉사되면 그것을 증명합니다. 평범한 용어로, 재귀 함수로 계산할 수있는 것은 반복 모델 (예 : 튜링 머신)에 의해 계산 가능하며 그 반대도 마찬가지입니다. 이 논문은 전환을 수행하는 방법을 정확하게 말하지 않지만 확실히 가능하다고 말합니다.

대부분의 경우 재귀 기능을 변환하는 것은 쉽습니다. Knuth는 "컴퓨터 프로그래밍의 기술"에서 몇 가지 기술을 제공합니다. 그리고 종종, 재귀 적으로 계산 된 것은 시간과 공간이 줄어들면서 완전히 다른 접근법에 의해 계산 될 수 있습니다. 이것의 전형적인 예는 fibonacci 번호 또는 그 시퀀스입니다. 당신은 분명히 당신의 학위 계획 에서이 문제를 충족 시켰습니다.

이 동전의 반대로, 우리는 공식의 재귀 적 정의를 이전 결과를 메모 화하려는 초대로 취급 할 정도로 발전된 프로그래밍 시스템을 상상할 수 있습니다. 재귀 정의가있는 공식 계산을 따르십시오. Dijkstra는 거의 확실하게 그러한 시스템을 상상했습니다. 그는 구현을 프로그래밍 언어의 의미와 구현하는 데 오랜 시간을 보냈습니다. 그런 다음 그의 비 결정적 및 다중 프로세싱 프로그래밍 언어는 실무 전문 프로그래머보다 리그에 있습니다.

최종 분석에서 많은 기능은 재귀적인 형태로 이해, 읽기 및 쓰기가 더 쉽습니다. 강력한 이유가 없다면,이 기능을 명시 적으로 반복적 인 알고리즘으로 (수동으로) 변환해서는 안됩니다. 컴퓨터가 해당 작업을 올바르게 처리합니다.

나는 하나의 매력적인 이유를 볼 수 있습니다. [석면 속옷 착용] 계획, LISP, Haskell, Ocaml, Perl 또는 Pascal. C 또는 Java에서 구현이 필요한 조건이라고 가정합니다. (아마도 그것은 정치 일 것입니다.) 그러면 당신은 확실히 재귀 적으로 일부 기능을 작성할 수 있지만 문자 그대로 번역 된 런타임 시스템을 폭발시킬 것입니다. 예를 들어, 체계에서는 무한 꼬리 재귀가 가능하지만 동일한 관용구는 기존 C 환경에 문제가 발생합니다. 또 다른 예는 파스칼이 지원하지만 C는 어휘 중첩 함수와 정적 범위를 사용하는 것입니다.

이러한 상황에서는 원래 언어에 대한 정치적 저항을 극복하려고 노력할 수 있습니다. Greenspun의 (혀에 뺨) 10 차 법에서와 같이 LISP를 심하게 상환 할 수 있습니다. 또는 솔루션에 대한 완전히 다른 접근 방식을 찾을 수도 있습니다. 그러나 어쨌든 분명히 방법이 있습니다.

Answer 2

모든 재귀 기능에 대해 비수체 형태를 항상 작성할 수 있습니까?

예. 간단한 공식적인 증거는 둘 다를 보여주는 것입니다 µ 재귀 그리고 Goto와 같은 비수체 적 미적분학은 모두 튜링을 완료하고 있습니다. 모든 튜링 완전한 미적분학은 그들의 표현력이 엄격하게 동일하기 때문에, 모든 재귀 함수는 비수체 적 튜링-완성 미적분학에 의해 구현 될 수있다.

불행히도, 나는 Goto Online의 좋은 공식적인 정의를 찾을 수 없으므로 여기에 있습니다.

GOTO 프로그램은 일련의 명령입니다 피 a 기계를 등록하십시오 그렇게 피 다음 중 하나입니다.

• HALT, 실행을 중단합니다
• 아르 자형 = 아르 자형 + 1 어디 아르 자형 모든 레지스터입니다
• 아르 자형 = 아르 자형 – 1 어디 아르 자형 모든 레지스터입니다
• GOTO 엑스 어디 엑스 레이블입니다
• IF 아르 자형 ≠ 0 GOTO 엑스 어디 아르 자형 모든 레지스터와 엑스 레이블입니다
• 레이블, 위의 명령 중 하나가 뒤 따릅니다.

그러나 재귀 적 기능과 비수체 기능 사이의 전환이 항상 사소한 것은 아닙니다 (통화 스택의 무의미한 수동 재 구현을 제외하고).

자세한 내용은 참조하십시오 이 답변.

Answer 3

재귀는 실제 통역사 또는 컴파일러에서 스택 또는 유사한 구성으로 구현됩니다. 그래서 당신은 확실히 재귀 기능을 반복적 인 상대로 변환 할 수 있습니다. 그것이 항상 수행되는 방식이기 때문에 (자동으로). 컴파일러의 작업을 임시로, 아마도 매우 못 생겼고 비효율적 인 방식으로 복제 할 것입니다.

Answer 4

기본적으로, 본질적으로, 본질적으로 당신이해야 할 일은 메소드 호출 (암시 적으로 상태를 스택으로 밀어 넣음)을 명시 적 스택으로 바꾸는 것입니다. 대신에.

기본적으로 메소드 호출을 시뮬레이션함으로써 루프, 스택 및 상태 머신의 조합이 모든 시나리오에 사용될 수 있다고 생각합니다. 이것이 '더 나은'(어떤 의미에서 더 빠르거나 효율적)가 될지 여부는 일반적으로 말할 수 없습니다.

Answer 5

• 재귀 함수 실행 흐름은 트리로 표시 될 수 있습니다.

• 동일한 논리는 데이터 구조를 사용하여 트리를 통과하는 루프로 수행 할 수 있습니다.

• 깊이 우선 트래버살은 스택을 사용하여 수행 할 수 있으며, 폭이 먼저 횡선을 수행 할 수 있습니다.

따라서 대답은 다음과 같습니다. 예. 왜: https://stackoverflow.com/a/531721/2128327.

단일 루프로 재귀를 할 수 있습니까? 예, 왜냐하면

Turing Machine은 단일 루프를 실행하여 모든 작업을 수행합니다.

1. 지시를 가져 오십시오.
2. 그것을 평가하고,
3. goto 1.

Answer 6

그렇습니다. 항상 비수체 버전을 작성하는 것이 가능합니다. 사소한 솔루션은 스택 데이터 구조를 사용하고 재귀 실행을 시뮬레이션하는 것입니다.

Answer 7

그렇습니다. 명시 적으로 스택을 사용합니다 (그러나 재귀는 IMHO를 읽는 것이 훨씬 즐겁습니다).

Answer 8

원칙적으로 항상 재귀를 제거하고 데이터 구조와 통화 스택 모두에 무한 상태가있는 언어로 반복으로 바꿀 수 있습니다. 이것은 교회 타기 논문의 기본 결과입니다.

실제 프로그래밍 언어가 주어지면 대답은 분명하지 않습니다. 문제는 프로그램에 할당 할 수있는 메모리의 양이 제한되어 있지만 사용할 수있는 통화 스택의 양이 생겨나는 언어를 가질 수 있다는 것입니다 (스택 변수의 주소가있는 32 비트 C 는 접근 할 수 없습니다). 이 경우 재귀는 더 많은 메모리를 사용할 수 있기 때문에 더 강력합니다. 통화 스택을 모방하기에 충분히 할당할만한 메모리가 충분하지 않습니다. 이에 대한 자세한 내용은 참조하십시오 이 토론.

Answer 9

때로는 재귀를 교체하는 것이 그보다 훨씬 쉽습니다. 재귀는 1990 년대 CS에서 가르치는 세련된 일 이었으므로 그 당시 많은 평균 개발자들이 재귀로 무언가를 해결했다면 더 나은 솔루션이었습니다. 따라서 그들은 역순으로 뒤로 반복하는 대신 재귀를 사용하거나 그와 같은 바보 같은 것들을 사용합니다. 따라서 때때로 재귀를 제거하는 것은 간단한 "DUH, 즉 명백한 운동 유형"입니다.

패션이 다른 기술로 바뀌었기 때문에 지금은 문제가되지 않습니다.

Answer 10

모든 계산 기능은 튜링 머신에 의해 계산 될 수 있으므로 재귀 시스템 및 튜링 머신 (반복 시스템)은 동일합니다.

Answer 11

재귀를 제거하는 것은 복잡한 문제이며 잘 정의 된 상황에서는 가능합니다.

아래 사례는 쉬운 것 중 하나입니다.

• 꼬리 재귀
• 직접 선형 재귀

Answer 12

명시 적 스택의 Appart는 재귀를 반복으로 변환하기위한 또 다른 패턴은 트램폴린을 사용하는 것입니다.

여기서 기능은 최종 결과를 반환하거나 그렇지 않으면 수행 한 기능 호출의 폐쇄를 반환합니다. 그런 다음 시작 (트램폴린) 함수는 최종 결과에 도달 할 때까지 반환 된 클로저를 계속 호출합니다.

이 접근법은 상호 재귀 함수에 효과적이지만 테일 콜에만 작동합니다.

http://en.wikipedia.org/wiki/trampoline_(computers)

Answer 13

나는 예라고 말하고 있습니다 - 함수 호출은 단지 goto와 스택 조작 (대략 말하기) 일뿐입니다. 기능을 호출하는 동안 구축 된 스택을 모방하고 goto와 비슷한 일을하는 것입니다 (이 키워드를 명시 적으로 가지고 있지 않은 언어로 모방 할 수 있습니다).

Answer 14

Wikipedia의 다음 항목을 살펴보면 시작점으로 사용하여 질문에 대한 완전한 답변을 찾을 수 있습니다.

• 컴퓨터 과학의 재귀
• 재발 관계

시작 장소에 대한 힌트를 줄 수있는 단락을 따릅니다.

재발 관계를 해결한다는 것은 a를 얻는 것을 의미합니다 폐쇄 형식 솔루션: n의 비수체 기능.

또한 마지막 단락을 살펴보십시오 이 항목.

Answer 15

재귀 알고리즘을 비수체로 변환 할 수는 있지만 논리가 훨씬 더 복잡하기 때문에 스택을 사용해야합니다. 실제로 재귀 자체는 스택을 사용합니다 : 기능 스택.

자세한 내용은: https://developer.mozilla.org/en-us/docs/web/javaScript/guide/functions

Answer 16

Tazzego, 재귀는 기능이 당신이 좋아하든 아니든 스스로 호출한다는 것을 의미합니다. 사람들이 재귀없이 일을 할 수 있는지 여부에 대해 이야기 할 때, 그들은 이것을 의미하며, 당신은 "아니오, 그것은 사실이 아닙니다. 재귀 정의에 동의하지 않기 때문에"라고 말할 수 없습니다.

그 점을 염두에두고, 당신이 말하는 다른 모든 것은 말도 안됩니다. 말도 안되는 것이 아니라고 말하는 유일한 것은 콜 스택 없이는 프로그래밍을 상상할 수 없다는 생각입니다. 그것은 콜 스택을 사용하기 전까지 수십 년 동안 이루어진 일입니다. 오래된 버전의 Fortran에는 콜 스택이 부족했고 잘 작동했습니다.

그건 그렇고, 반복의 수단으로 재귀 (예 : SML) 만 구현하는 튜링-완성 언어가 존재합니다. 또한 반복을 반복하는 수단 (예 : Fortran IV)으로 만 구현하는 튜링-완성 언어도 존재합니다. 교회-타이어 논문은 재귀 전용 언어로 가능한 모든 것이 비수 언어로 이루어질 수 있으며, 둘 다 튜링-완성의 재산을 가지고 있다는 사실에 의해 Vica-Versa로 수행 될 수 있음을 증명합니다.

Answer 17

반복 알고리즘은 다음과 같습니다.

def howmany(x,y)
  a = {}
  for n in (0..x+y)
    for m in (0..n)
      a[[m,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
    end
  end
  return a[[x,y]]
end