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

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

---

레딧 스레드는 분명히 흥미로운 질문을 제기 :

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

게시물의 (카운터?) 예는 다음과 같습니다.

(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))

---

항상 재귀 함수를 반복 함수로 바꿀 수 있습니까? 물론 그렇습니다. 그리고 교회 튜링 논문은 기억이 도움이된다면 그것을 증명합니다. 즉, 재귀 함수로 계산할 수있는 것은 반복 모델 (예 : Turing machine)로 계산할 수 있으며 그 반대도 마찬가지입니다. 논문은 변환 방법을 정확하게 설명하지는 않지만 확실히 가능하다고 말합니다.

많은 경우 재귀 함수를 쉽게 변환 할 수 있습니다. Knuth는 "컴퓨터 프로그래밍 기술"에서 몇 가지 기술을 제공합니다. 그리고 종종 재귀 적으로 계산 된 것을 적은 시간과 공간에서 완전히 다른 접근법으로 계산할 수 있습니다. 이것의 전형적인 예는 피보나치 수 또는 이의 서열이다. 학위 과정에서 반드시이 문제를 해결했습니다.

이 코인의 반대 측면에서, 우리는 공식의 재귀 적 정의를 이전 결과를 기억하기위한 초대로 취급 할 정도로 진보 된 프로그래밍 시스템을 상상할 수 있으며, 따라서 컴퓨터가 정확히 어떤 단계를 지시해야하는 번거 로움없이 속도 이점을 제공합니다 재귀 적 정의를 가진 공식의 계산을 따르십시오. Dijkstra는 거의 확실히 그러한 시스템을 상상했습니다. 그는 구현을 프로그래밍 언어의 의미와 분리하려고 오랜 시간을 보냈습니다. 그런 다음 그의 비결정적이고 다중 처리 프로그래밍 언어는 실무 전문 프로그래머보다 우위에 있습니다.

최종 분석에서 많은 함수는 재귀적인 형태로 이해하고 읽고 쓰는 것이 더 쉬워졌습니다. 설득력있는 이유가 없다면,이 함수들을 명시 적으로 반복적 인 알고리즘으로 (수동으로) 변환해서는 안됩니다. 컴퓨터가 해당 작업을 올바르게 처리합니다.

한 가지 설득력있는 이유가 있습니다. [ 석면 속옷 착용 ] 구성표, Lisp, Haskell, OCaml, Perl 또는 Pascal 과 같은 최고급 언어로 프로토 타입 시스템을 구축했다고 가정합니다 . 조건이 C 또는 Java로 구현되어야한다고 가정하십시오. (아마도 정치 일 것입니다.) 그렇다면 어떤 함수는 재귀 적으로 작성되었지만 문자 그대로 번역되어 런타임 시스템을 폭발시킬 수 있습니다. 예를 들어, Scheme에서는 무한 꼬리 재귀가 가능하지만 동일한 관용구가 기존 C 환경에 문제를 일으 킵니다. 또 다른 예는 파스칼은 지원하지만 C는 지원하지 않는 어휘 중첩 함수와 정적 범위를 사용하는 것입니다.

이러한 상황에서는 원래 언어에 대한 정치적 저항을 극복하려고 시도 할 수 있습니다. Greenspun의 (뺨에 혀로) 10 번째 법칙에서와 같이 Lisp를 잘못 구현 한 것을 알게 될 것입니다. 또는 완전히 다른 솔루션 접근 방식을 찾을 수 있습니다. 그러나 어쨌든 확실한 방법이 있습니다.

---

모든 재귀 함수에 대해 비 재귀 양식을 항상 작성할 수 있습니까?

예. 간단한 공식 증거는 µ 재귀 와 GOTO와 같은 비 재귀 미적분이 모두 Turing을 완료 함을 보여줍니다. 모든 Turing 완전 미적분은 표현력이 완전히 동일하기 때문에 모든 재귀 함수는 비재 귀적 Turing- 미완 적 미적분에 의해 구현 될 수 있습니다.

불행히도 온라인에서 GOTO에 대한 좋은 공식 정의를 찾을 수 없으므로 다음과 같습니다.

GOTO 프로그램은 P 가 다음 중 하나가 되도록 레지스터 머신 에서 실행 되는 일련의 명령 P 입니다 .

• HALT실행이 중단되는
• r = r + 1r레지스터는 어디에 있습니까
• r = r – 1r레지스터는 어디에 있습니까
• GOTO xx라벨이 어디 있어요
• IF r ≠ 0 GOTO xr레지스터는 어디에 x있고 레이블입니다
• 위의 명령 뒤에 레이블이 붙습니다.

그러나 재귀 함수와 비 재귀 함수 간의 변환이 항상 사소한 것은 아닙니다 (호출 스택을 수동으로 다시 구현하는 경우 제외).

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

---

재귀는 실제 인터프리터 또는 컴파일러에서 스택 또는 유사한 구조로 구현됩니다. 따라서 재귀 함수를 반복 대응 함수로 변환 할 수 있습니다. 왜냐하면 그것이 항상 자동으로 수행되기 때문입니다 . 컴파일러의 작업을 임시로, 아마도 매우 추악하고 비효율적 인 방식으로 복제하게 될 것입니다.

---

기본적으로 그렇습니다. 결국 당신이해야 할 일은 메소드 호출 (암시 적으로 스택에 상태를 푸시하는)을 명시 적 스택 푸시로 바꾸어 '이전 호출'이 어디서 왔는지 기억하고 '호출 된 메소드'를 실행하는 것입니다 대신에.

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

---

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

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

• 깊이 우선 순회는 스택을 사용하여 수행 할 수 있으며, 너비 우선 순회는 대기열을 사용하여 수행 할 수 있습니다.

대답은 '그렇다'입니다. 이유 : https://stackoverflow.com/a/531721/2128327 .

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

튜링 머신은 단일 루프를 실행하여 모든 작업을 수행합니다.

1. 명령을 가져와
2. 그것을 평가
3. 고토 1.

---

Yes, it's always possible to write a non-recursive version. The trivial solution is to use a stack data structure and simulate the recursive execution.

---

Yes, using explicitly a stack (but recursion is far more pleasant to read, IMHO).

---

In principle it is always possible to remove recursion and replace it with iteration in a language that has infinite state both for data structures and for the call stack. This is a basic consequence of the Church-Turing thesis.

Given an actual programming language, the answer is not as obvious. The problem is that it is quite possible to have a language where the amount of memory that can be allocated in the program is limited but where the amount of call stack that can be used is unbounded (32-bit C where the address of stack variables is not accessible). In this case, recursion is more powerful simply because it has more memory it can use; there is not enough explicitly allocatable memory to emulate the call stack. For a detailed discussion on this, see this discussion.

---

Sometimes replacing recursion is much easier than that. Recursion used to be the fashionable thing taught in CS in the 1990's, and so a lot of average developers from that time figured if you solved something with recursion, it was a better solution. So they would use recursion instead of looping backwards to reverse order, or silly things like that. So sometimes removing recursion is a simple "duh, that was obvious" type of exercise.

This is less of a problem now, as the fashion has shifted towards other technologies.

---

All computable functions can be computed by Turing Machines and hence the recursive systems and Turing machines (iterative systems) are equivalent.

---

Removing recursion is a complex problem and is feasible under well defined circumstances.

The below cases are among the easy:

• tail recursion
• direct linear recursion

---

Appart from the explicit stack, another pattern for converting recursion into iteration is with the use of a trampoline.

Here, the functions either return the final result, or a closure of the function call that it would otherwise have performed. Then, the initiating (trampolining) function keep invoking the closures returned until the final result is reached.

This approach works for mutually recursive functions, but I'm afraid it only works for tail-calls.

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

---

I'd say yes - a function call is nothing but a goto and a stack operation (roughly speaking). All you need to do is imitate the stack that's built while invoking functions and do something similar as a goto (you may imitate gotos with languages that don't explicitly have this keyword too).

---

Have a look at the following entries on wikipedia, you can use them as a starting point to find a complete answer to your question.

• Recursion in computer science
• Recurrence relation

Follows a paragraph that may give you some hint on where to start:

Solving a recurrence relation means obtaining a closed-form solution: a non-recursive function of n.

Also have a look at the last paragraph of this entry.

---

It is possible to convert any recursive algorithm to a non-recursive one, but often the logic is much more complex and doing so requires the use of a stack. In fact, recursion itself uses a stack: the function stack.

More Details: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions

---

tazzego, recursion means that a function will call itself whether you like it or not. When people are talking about whether or not things can be done without recursion, they mean this and you cannot say "no, that is not true, because I do not agree with the definition of recursion" as a valid statement.

With that in mind, just about everything else you say is nonsense. The only other thing that you say that is not nonsense is the idea that you cannot imagine programming without a callstack. That is something that had been done for decades until using a callstack became popular. Old versions of FORTRAN lacked a callstack and they worked just fine.

By the way, there exist Turing-complete languages that only implement recursion (e.g. SML) as a means of looping. There also exist Turing-complete languages that only implement iteration as a means of looping (e.g. FORTRAN IV). The Church-Turing thesis proves that anything possible in a recursion-only languages can be done in a non-recursive language and vica-versa by the fact that they both have the property of turing-completeness.

---

Here is an iterative algorithm:

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

참고URL : https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration