Рекурсивный Фибоначчиев поиск
Очень нужна помощь, нужно реализовать рекурсивный Фибоначчиев поиск на C++. Вот изначальный вариант:
int fibonacci_search(int arr[], int size, int target) {
int fibm2 = 0;
int fibm1 = 1;
int fib = 1;
int shift = 0;
while (fibm1 + shift < size) {
if (arr[fib + shift - 1] == target) {
return fib + shift - 1;
}
if (arr[fib + shift - 1] < target) {
fibm2 = fibm1;
fibm1 = fib;
fib = (fibm1 + fibm2 + shift < size) ? fibm1 + fibm2 : size - shift;
} else if (arr[fib + shift - 1] > target) {
shift += fibm1;
fibm2 = 0;
fibm1 = 1;
fib = 1;
}
}
return -1;
}
Ответы (1 шт):
Автор решения: Wonderf
→ Ссылка
Если упростить ваш код, то получится так
int fibonacci_search(int arr[], int size, int target) {
for(int i=0;i<size;i++){
if(arr[i]==target)
return i;
}
return -1;
}
Для того чтобы написать рекурсию, нужно задать для нее базу с выражением return
return position;
и шаг рекурсии
return fibonacci_search_recoursion(arr,size,target,shift+1);
Все вместе выходит так
int fibonacci_search_recoursion(int arr[],int size,int target,int shift){
if (arr[shift] == target) {
return shift;
}else if(arr[shift]<target && shift<size){
return fibonacci_search_recoursion(arr,size,target,shift+1);
}else return -1;
}