Rekursive lineare Suche

Question

Der unten gezeigte Code funktioniert einwandfrei. Er gibt die Position des Elements aus, das sich in der if-Klausel befindet, und beendet das Element. Immer wenn das Element nicht gefunden wird, wird die Funktion auf max ausgeführt und gibt 0 an die aufrufende Funktion zurück, um anzuzeigen, dass keine Elemente gefunden wurden.

Allerdings habe ich darüber nachgedacht, die Position des gefundenen Elements an die aufrufende Funktion zurückzugeben, anstatt sie zu drucken. Da die Rückkehr der Position nur zu einer früheren Instanz der Funktion und nicht zu der aufrufenden Funktion zurückkehren würde, bin ich betroffen. Wie erreiche ich das?

#include <stdio.h> 
#include <stdlib.h> 

int RLinearSearch(int A[],int n,int key) 
{ 
    if(n<1) 
     return 0; 
    else 
    { 
     RLinearSearch(A,n-1,key); 
     if(A[n-1]==key) 
     { 
      printf("found %d at %d",key,n); 
      exit(0); 
     } 
    } 
    return 0; 
} 

int main(void) 
{ 
    int A[5]={23,41,22,15,32}; // Array Of 5 Elements 
    int pos,n=5; 

    pos=RLinearSearch(A,n,23); 

    if(pos==0) 
     printf("Not found"); 

    return 0; 
} 

Answer 1

Da die Position der Rückkehr zu früheren Instanz der Funktion nur zurückkommen würde und nicht an die aufrufende Funktion, ich geschlagen bin.

Sie können dieses Problem lösen, indem das Ergebnis der rekursiven Aufruf aus der rekursiven selbst nennen Rückkehr:

int RLinearSearch(int A[], int n, int key) { 
    if(n<0) { // Base case - not found 
     return -1; 
    } 
    if(A[n]==key) { // Base case - found 
     return n; 
    } 
    // Recursive case 
    return RLinearSearch(A, n-1, key); 
} 

Seit dieser Implementierung behandelt n als der Index des aktuellen Elements, sollte der Anrufer 4 passieren, nicht 5, in deinem Beispiel.

Demo 1.

Hinweis: Sie können weiterhin den Code vereinfachen, indem die Basis Fälle zusammen verbinden:

int RLinearSearch(int A[], int n, int key) { 
    return (n<0 || A[n]==key) ? n : RLinearSearch(A, n-1, key); 
} 

Demo 2.

Answer 2

Start mit Ihrem Problem: lineare Suche Zurückführen des Index von wo der Schlüssel gefunden wird, hat die Funktion drei Parameter, das Array, den Startindex der Suche n und den Suchschlüssel k.

so Sie haben:

int RLinearSearch(int[] A, int n, int k) 
{  
    if (n=>A.length()) return (-1);//base case(k not found in A) 
    else if (A[n]==k) return n; //found case 
    else return RLinearSearch(A, n+1, key); //continue case(keep looking through array) 
} 
int main(void){ 
    int A[5]={23,41,22,15,32}; // Array Of 5 Elements 
    int pos,n=0; 

    pos=RLinearSearch(A,n,23); 
    if (pos == -1) printf("Not Found"); 
    return 0; 
} 

Sie es auch so, dass Sie nur n-1 zurück ändern könnten, und Sie würden den richtigen Index haben.