bool을 되 돌리는 재귀 함수

Question

bool을 돌려주는 다음의 재귀 함수를 이해할 수 없다.

bool p(int a[], int inf, int sup) { 
    if(sup==inf) 
     if(a[inf]>0) 
      return true; 
     else 
      return false; 
    int m=(inf+sup)/2; 
    bool left=p(a,inf,m); 
    bool right=p(a,m+1,sup); 
    return left && right; 
} 

(INF, SUP)의 모든 요소가 false 다른 긍정적이거나있는 경우는 true를 반환해야하지만 배열의 두 극값에없는 요소를 고려하는 방법을 볼 수 없습니다, 이후 테스트 된 조건은 a[inf]>0이고 left에 대한 재귀 동안 inf는 변경되지 않지만 right에 대한 배열의 오른쪽 부분에서만 값을 가져옵니다.

근본적으로, 그것은 계승 (피보나치와 같은)보다 쉬운 재귀와는 다르기 때문에 여기에서 재귀가 어떻게 작동하는지 이해할 수 없습니다. 기본 경우부터 시작하여 두 번째 단계로 진행하려고했지만 명확하지 않습니다 진행 방법.

누구든지이 경우 재귀를 따르는 방법을 제안 할 수 있습니까?이 함수가 (inf, sup)의 모든 요소가 양수이면 true를 반환하는 방법을 이해할 수 있습니까?

Answer 1

작은 배열에 대해 코드를 실행 한 다음 패턴을 알아내는 것이 항상 유용합니다.

알고리즘은 확실히 sup = inf (size = 1) 및 sup = inf + 1 (size = 2)에 대해 작동합니다.

결과적으로 배열을 2 개 (크기 2와 1)로 분할했기 때문에 size = 3에서 작동하며이 작은 크기의 코드가 작동한다는 것을 이미 입증했습니다.

기본적으로 Algo (size = k) 및 Algo (size = k - 1)가 올바른 결과를 반환하는 경우 Algo (size = 2k = k + k) 및 Algo (size = 2k - 1 = k + (k-1)).

그래서 Algo (n)은 모든 n에 대해 작동합니다.

이 근사 수학 추론을 "수학적 유도"라고합니다.

Answer 2

• 컬렉션에 하나의 요소이 있으면 해당 요소에 대한 답을 반환하십시오. 문제를 더욱 단순화하기 위해 재귀가 필요하지 않습니다.
• 컬렉션에이 두 개 이상인 인 경우 컬렉션을 반으로 나누고 각 반마다 반복합니다.

컬렉션의 모든 요소는 결국 단일 요소 컬렉션으로 간주됩니다.

Answer 3

우리는 P에 대한 호출이 m = (0 + 4)/2 = 2으로이 전화로 나누어 져 있습니다

int a[5] = [2, 1, -3, 7, 4]; 
p(a, 0, 4) 

다음과 같은 배열을 고려하는 경우 :

bool left=p(a,inf,m); 전화 p(a, 0, 2)

및

bool right=p(a,m+1, sup);이 p(a, 3, 4)

트리거를 0

후속 호출에서 동일한 배열이 인수로 전달되고 inf 및 sup 인수 만 변경되고 변경되었습니다.

p(a, 0, 2)  ||| p(a, 3, 4) 
m = (0+2)/2 = 1 ||| m' = (3+4)/2 = 3 

2 개의 새로운 통화가 각 지점에서 발행 : 두 경우 모두 inf 및 sup에서 이후

여전히 우리가 m 계산 호출 동일하지

p(a, 0, 1) || p(a, 2, 2) ||| p(a, 3, 3) || p(a, 4, 4) 

inf 및 sup이 동일, 배열의 요소가 엄밀하게 양수인지를 반환합니다. 결국

p(a, 0, 0) | p(a, 1, 1) || false ||| true || true 
true  | true  || false ||| true || true 

, 결과는 그들 모두에 대해 부울 AND 연산입니다 : 그렇지 않을 때, 분할이 계속

true && true && false && true && true = false 

나는 당신이 따를 수 있기를 바랍니다.

Answer 4

하지만, 배열의 두 극값에없는 요소가 고려하는 방법을 볼 수 없습니다 ... 자기를 설득

한 가지 방법은 코드를 단계별하는 것입니다 디버거와 함께.

나는 gdb에 저항하지 않지만 때로는 코드 자체를보고하는 것을 선호합니다.

흥미로운 장소에 보고서를 추가합니다.

#include <iostream> 
#include <fstream> 
#include <iomanip> 
#include <sstream> 
#include <string> 
#include <cassert> 


class T547_t 
{ 
    int depth = 0; 

public: 

    int exec() 
     { 
     //   0 1 2 3 4 
     int a[5] = {2, 1, -3, 7, 4}; 

     std::cout << "\n " << (p(a,0,4) ? "\n true" : "\n false") 
        << "\n" << std::endl; 

     // repeat test with all positive values 

     int b[5] = {2, 1, 3, 7, 4}; 

     std::cout << "\n " << (p(b,0,4) ? "\n true" : "\n false") 
        << "\n" << std::endl; 

     return 0; 
     } 


private: // methods 

    std::string show(int a[], int inf, int sup) 
     { 
     std::stringstream ss; 
     depth += 1; 
     ss << "a[" << inf << "," << sup << "] " 
      << depth << std::setw(3+depth)<< " "; 
     for (int i = inf; i <= sup; ++i) 
      ss << a[i] << " "; 
     return ss.str(); 
     } 


    bool p(int a[], int inf, int sup) 
     { 
     std::cout << "\n " << show(a, inf, sup) << std::flush; 
     if(sup==inf) 
     { 
      if(a[inf]>0) { depth -= 1; return true; } 
      else   { depth -= 1; return false; } 
     } 
     int  m = (inf+sup)/2; 
     bool left = p (a, inf, m); 
     bool right = p (a, m+1, sup); 
     depth -= 1 ; 
     return (left && right); 
     } 
    // 1 line added to beginning of method p 

}; // class T547_t 


int main(int , char**) 
{ 
    T547_t t547; 
    return t547.exec(); 
} 

출력을 보여줍니다

a[0,4] 1 2 1 -3 7 4 
    a[0,2] 2  2 1 -3 
    a[0,1] 3  2 1 
    a[0,0] 4  2 
    a[1,1] 4  1 
    a[2,2] 3  -3 
    a[3,4] 2  7 4 
    a[3,3] 3  7 
    a[4,4] 3  4 

    false 


    a[0,4] 1 2 1 3 7 4 
    a[0,2] 2  2 1 3 
    a[0,1] 3  2 1 
    a[0,0] 4  2 
    a[1,1] 4  1 
    a[2,2] 3  3 
    a[3,4] 2  7 4 
    a[3,3] 3  7 
    a[4,4] 3  4 

    true 

는 분명히 모든 값이 방문하고 있습니다.