使用遞歸查找數組中第一個目標數字的出現

Question

該代碼可以返回目標數字的位置。但是，如果目標編號不在數組中，那麼程序應該返回-1。還需要我只使用遞歸。

下面是代碼：

#include <stdio.h> 

int rLookupAr(int ar[], int n, int target); 

int main() { 
    int a[80]; 
    int target, i, size; 

    printf("Enter array size: "); 
    scanf("%d", &size); 
    printf("Enter %d numbers: ", size); 
    for (i = 0; i < size; i++) 
     scanf("%d", &a[i]); 
    printf("Enter target number: "); 
    scanf("%d", &target); 
    printf("rLookupAr(): %d", rLookupAr(a, size, target)); 
    return 0; 
} 

int rLookupAr(int ar[], int n, int target) { 
    /* write your code here */ 
    if (ar[0] == target) { 
     if (n == 0) 
      return -1; 
     else 
      return 0; 
    } else 
     return 1 + rLookupAr(ar + 1, n - 1, target); 
} 

Answer 1

功能可以像

int rLookupAr(const int ar[], int n, int target) 
{ 
    if (n < 1) 
    {   
     return -1; 
    } 
    else if (ar[0] == target) 
    { 
     return 0; 
    }   
    else 
    {   
     int i = rLookupAr(ar + 1, n - 1, target); 
     return i == - 1 ? i : i + 1; 
    }   
} 

Answer 2

張貼您的遞歸函數不能工作：

如果目標數是不是數組中，返回的索引將爲-1，但除非數組爲空，則此返回值將被所有遞歸調用抵消，最終返回值將爲數組-1，錯誤地指向最後一個數組條目。

你應該修改你的代碼是這樣的：

int rLookupAr(int ar[], int n, int target) { 
    if (n <= 0) 
     return -1; 
    if (ar[0] == target) 
     return 0; 
    int res = rLookupAr(ar + 1, n - 1, target); 
    if (res < 0) 
     return res; 
    else 
     return res + 1; 
} 

注意，該遞歸效率非常低，將導致堆棧溢出，如果數組足夠大，目標足夠遠，或不存在。

仍然使用遞歸，但有限的深度將分成數組和遞歸每個半選擇：

int rLookupAr(int ar[], int n, int target) { 
    if (n <= 0) 
     return -1; 
    int m = n/2; 
    if (ar[m] == target) 
     return m; 
    int res = rLookupAr(ar, m, target); 
    if (res >= 0) 
     return res; 
    res = rLookupAr(ar + m + 1, n - m - 1, target); 
    if (res >= 0) 
     return res + m + 1; 
    else 
     return -1; 
} 

Answer 3

試試這個：

int rLookupAr(int *ar, int n, int target) 
{ 
    if (n == 0) return -1; 
    if (ar[0] == target) return 0; 

    int _ret = rLookupAr(ar + 1, n - 1, target); 

    if(_ret != -1) return ++_ret; 
    else   return -1; 
} 

我看到弗拉德已經建議它，所以... 看到它的行動：https://ideone.com/LhovTh

Answer 4

int targ_pos(const int *p, int n, int target) 
{ 
    if(*p == target){return 1;} 

    if(n == 1){return -1;} 

    return targ_pos(p+1, --n, target); 
}