wyszukiwanie liniowe

Question

potrzebuje napisać funkcje wyszukiwania liniowego rekurencyjnie. funkcja ma zwrócić indeks 1 napotkanej liczby a gdy nie wystepuje to -1.

oto kod iteracyjny:

int SzukajLiniowe(int *t, int n, int liczba){
int i;
 for(i=0;i<n;i++)
    if ( t[i] == liczba)
      return i;
return -1;
}    

Nie mam pomysłu jak zamienić to na rekurencje.

Answer 1

Jeśli definiujesz funkcje rekurencyjna pierwsze co musisz określić to tak zwany warunek stopu. Czyli miejsce w którym funkcja zakończy swoje działanie. W tym wypadku są dwa warunki stopu. Jeden z nich to kiedy n będzie mniejsze od zera. Zaś drugi kiedy tablica dla indeksu n-1 będzie równa naszej szukanej liczbie. Oczywiście najlepiej jest iść od tyłu czyli elementu n-1 do początku czyli elementu o indeksie zero.

Kod realizujący tę koncepcie widoczny jest poniżej:

#include <iostream>
using namespace std;

int wyszuka_liniowo_rek(int t[],int n,int szukana)
{
	if(n<0)
	{
		return -1;
	}
	else if(t[n-1]==szukana)
	{
		return n-1;
	}
	else
	{
		return wyszuka_liniowo_rek(t,n-1,szukana);
	}
}

int main() {
	int tab[]={3,5,7,8,9};
	
	cout<<wyszuka_liniowo_rek(tab,5,10)<<endl;
	cout<<wyszuka_liniowo_rek(tab,5,3)<<endl;
	
	return 0;
}

 

Comments

dzięki wielkie

---

Proszę bardzo :)