Rekursive Funktion zurück bool

Question

Ich kann die folgende rekursive Funktion nicht verstehen, die eine bool zurückgibt.

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; 
} 

Es sollte wahr zurück, wenn alle Elemente in (inf, sup) positiv sind oder aber falsch, aber ich kann nicht sehen, wie die Elemente, die nicht an den beiden Extrema des Arrays sind, berücksichtigt, da Die getestete Bedingung ist, dass a[inf]>0 und inf nicht während der Rekursion für left geändert werden, während sie Werte nur im rechten Teil des Arrays für right erhält.

Also im Grunde, da es sich von leichteren Rekursionen unterscheidet (wie die faktorielle oder Fibonacci) kann ich nicht verstehen, wie Rekursion hier funktioniert: Ich habe versucht, vom Basisfall zu starten und gehe zum zweiten Schritt, aber es ist unklar wie geht es weiter?

Kann mir jemand vorschlagen, wie man der Rekursion in diesem Fall folgt, um zu verstehen, wie diese Funktion wahr zurückgibt, wenn alle Elemente in (inf, sup) positiv sind?

Answer 1

Es ist immer nützlich, den Code für kleine Arrays auszuführen und dann ein Muster zu bemerken.

Algorithmus funktioniert definitiv für sup = inf (Größe = 1) und sup = inf + 1 (Größe = 2);

Folglich funktioniert es für Größe = 3, weil Sie Ihr Array in zwei (Größen 2 und 1) teilen und wir haben bereits festgestellt, dass der Code für diese kleineren Größen funktioniert. Wenn Sie wissen, dass Algo (Größe = k) und Algo (Größe = k - 1) die richtigen Ergebnisse liefern, dann auch Algo (Größe = 2k = k + k) und Algo (Größe = 2k - 1 = 0) k + (k - 1)).

Und so funktioniert Algo (n) für jeden n.

Diese nah-mathematische Argumentation wird "mathematische Induktion" genannt.

Answer 2

• Wenn die Sammlung hat ein Element, geben Sie die Antwort für dieses Element. Es ist keine Wiederholung erforderlich, um das Problem weiter zu vereinfachen.
• Wenn die Sammlung hat mehr als ein Element, teilen Sie die Sammlung in zwei Hälften und recurse auf jeder Hälfte.

Jedes Element in der Sammlung wird schließlich als eine Ein-Element-Sammlung betrachtet.

Answer 3

Bedenkt man die folgende Matrix

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

der Anruf an P in 2 Anrufe als m = (0 + 4)/2 = 2 unterteilt:

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

und

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

Beachten Sie, dass das gleiche Array als Argument in den nachfolgenden Aufrufen und nur die Argumente inf und sup übergeben und geändert wird.

Da in beiden Fällen inf und sup sind noch nicht gleich berechnen wir rufen m:

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

2 neue Anrufe werden in jedem Zweige ausgegeben:

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

Wenn inf und sup gleich sind, Es gibt zurück, ob das Element im Array streng positiv ist. Wenn dies nicht der Fall, geht es Splitting:

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

Am Ende ist das Ergebnis eine boolean AND-Operation auf jedem von ihnen:

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

Ich hoffe, dass Sie diese folgen können.

Answer 4

aber ich kann nicht sehen, wie die Elemente, die nicht an den beiden Extrema das Array sind, berücksichtigt, ...

Eine Möglichkeit, um sich selbst davon zu überzeugen, ist durch den Code zu Schritt mit einem Debugger.

Ich widerst nicht gdb, aber manchmal bevorzuge ich den Code selbst zu melden.

Ich füge Berichte zu interessanten Orten hinzu.

#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(); 
} 

Die Ausgabe zeigt:

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 

Offensichtlich werden alle Werte besucht.