for 루프가있는 재귀 함수를 반복 함수로 변경 하시겠습니까?

Question

그래서이 함수는 재귀 알고리즘을 반복 알고리즘으로 변환하려고합니다. 올바른 하위 문제가 있는지 확실하지 않지만 올바른 방법으로 필요한 것을 결정한 것 같습니다. 재귀를 사용할 수 없으므로 동적 프로그래밍을 사용해야하므로 반복적 인 상향식 또는 상향식으로 변경해야합니다. 다운 동적 프로그래밍.

기본 재귀 함수는 다음과 같습니다

Recursion(i,j) { 
    if(i > j) { 
     return 0; 
    } 
    else { 
     // This finds the maximum value for all possible 
     // subproblems and returns that for this problem 
     for(int x = i; x < j; x++) { 
      if(some subsection i to x plus recursion(x+1,j) is > current max) { 
       max = some subsection i to x plus recursion(x+1,j) 
      } 
     } 
    } 
} 

이것은 일반적인 생각이지만, 재귀는 일반적으로 그들 루프를 가지고 있지 않기 때문에 나는 반복이 변환하는 것과 방법을 잘 모르겠어요 . 누구든지 아이디어가 있습니까? 아직 포함되지 않은 논리에 문제가 없다면, 그것은 & 동안

괜찮을 아니라

Answer 1

는

당신이 발생할 수있는 모든 경우에 반환해야합니다 재귀의 확인이다

Answer 2

이 같이 요약 될 수있는 재귀 함수가 있습니다

recursive(i, j): 
    if stopping condition: 
     return value 

    loop: 
     if test current value involving recursive call passes: 
      set value based on recursive call 

    return value # this appears to be missing from your example 

(나는 의사 코드와 매우 느슨한 될 것입니다을 그 특정 구현보다는 코드의 구조를 강조하기 위해)

그리고 순전히 반복적 인 접근 방식으로 전개하려고합니다. 먼저, 일반적인 경우에 무엇이 포함되는지 정확히 설명하는 것이 좋을 것입니다. 그런 다음 위의 의사 코드를 평평하게 전개 할 수 있습니다.

이제 원시적 인 재귀 함수를 평평하게 만드는 것은 아주 간단합니다. 당신은 신속하게 i가 미리 정의 된 한계에 도달 할 때까지 재귀 호출이 계속 볼 수 있습니다

simple(i): 
    if i has reached the limit: # stopping condition 
     return value 

    # body of method here 

    return simple(i + 1) # recursive call 

: 당신이 코드를 부여하는 경우처럼입니다. 이 경우 value이 반환됩니다. 이것의 반복 형태는 다음과 같습니다

simple(1) 
    -> simple(2) 
    -> simple(3) 
     ... 
     -> simple(N): 
      return value 

내가 문자열의 조각으로 그 호출 트리를 기술 할 것 :

simple_iterative(start): 
    for (i = start; i < limit; i++): 
     # body here 

    return value 

이것은 재귀 호출은 다음 호출 트리를 형성하기 때문에 작동합니다. 그것은 시작, 중간, 끝이 있습니다. 서로 다른 호출은 문자열의 다른 지점에서 발생합니다.

이와 같은 호출 문자열은 for 루프와 매우 비슷합니다. 함수에 의해 수행 된 모든 작업은 다음 호출로 전달되고 재귀의 최종 결과는 방금 전달됩니다. for 루프 버전은 다른 호출로 전달되는 값을 취하여 해당 코드에서 본문 코드를 실행합니다.

지금까지 단순!

이제 방법은 두 가지 방법으로 더 복잡한은 다음과 같습니다

• 재귀 호출 자체가 루프

그래서 통화 트리에 대한 내에

그 진술을 여러 별도의 문이 있습니다 다음과 같습니다.

전혀 끈 같지는 않습니다. 대신에 실제로는 각각의 호출이 두 번 더 호출된다는 점에서 나무 (또는 덤불)와 같습니다. 이 시점에서 이것을 완전히 반복적 인 함수로 바꾸는 것은 실제로 매우 어렵습니다.

이것은 루프와 재귀 사이의 근본적인 관계 때문입니다. 모든 루프는 재귀 호출로 다시 지정할 수 있습니다. 그러나 모든 재귀 호출을 루프로 변환 할 수있는 것은 아닙니다.

루프로 변환 될 수있는 재귀 호출 클래스는 원시 재귀이라고합니다. 귀하의 기능은 처음에는 그것을 초월한 것으로 보입니다. 이 경우에는 순전히 반복적 인 함수로 변환 할 수 없습니다 (실제로 함수 내에서 호출 스택 및 유사 함수를 구현하지 않은 경우). 내가 당신의 상태 및 max에 할당 값이 동일하게 나타나는 추가 할

https://www.youtube.com/watch?v=i7sm9dzFtEI

:

이 동영상은 다음과 원시 재귀 근본적으로 재귀 유형의 차이를 설명합니다. 이 경우 재귀 호출 중 하나를 제거하여 함수가 루프에서 래핑 된 원시 재귀의 인스턴스가되도록 할 수 있습니다. 당신이 그렇게했다면 당신은 그것을 평평하게 할 수있을 것입니다.