-2

下面显示的代码工作正常。它打印在 if 子句中找到的元素的位置并退出。每当找不到元素时，该函数就会运行到 max 并向调用函数返回 0 以指示未找到任何元素。

但是，我正在考虑将找到的元素的位置返回给调用函数而不是打印它。由于返回位置只会返回到函数的早期实例而不是调用函数，所以我很震惊。如何做到这一点？

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

4 回答 4

2

由于返回位置只会返回到函数的早期实例而不是调用函数，所以我很震惊。

您可以通过从递归调用本身返回递归调用的结果来解决此问题：

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

由于此实现将n其视为当前元素的索引，因此在您的示例中，调用者应传递 4，而不是 5。

演示 1。

注意：您可以通过将基本案例连接在一起来进一步简化代码：

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

演示 2。

于 2016-07-11T16:01:34.997 回答
1

从你的问题开始：线性搜索返回找到键的索引 该函数具有三个参数，数组，搜索 n 的起始索引和搜索键 k。

所以你有了：

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

您也可以更改它，以便您只返回 n-1 并且您将拥有正确的索引。

于 2016-07-11T16:17:02.120 回答
0

您可以使用尾递归：

int LSearch(int a[],int n,int key,int i)
 {
  if(n==0) return -1;
  if(a[0]==key) return i;
  LSearch(a+1,n-1,key,++i);
 }

调用时使用函数调用：

LSeacrh(a,n,key,0);
于 2019-04-02T05:00:56.257 回答
0 
public static int recursiveLinearSearch(int[] data, int index, int key){
    
    if(index==data.length)
        return -1;
    if(data[index]==key)
        return index;
    
    return recursiveLinearSearch(data, index+1, key);
    
}
于 2020-12-22T00:38:29.193 回答