递归线性搜索

Question

下面显示的代码工作正常。它打印在 if 子句中找到的元素的位置并退出。每当找不到元素时，函数运行到 max 并且 returns 0 调用函数以指示没有找到元素。

但是，我在考虑 return 将找到的元素的位置发送到调用函数而不是打印它。由于 returning 位置只会 return 到函数的早期实例而不是调用函数，我很震惊。如何实现？

#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

Since returning the position would just return to earlier instance of the function and not to the calling function, I am struck.

你可以通过递归调用本身返回递归调用的结果来解决这个问题：

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。

Demo 1.

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

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

Demo 2.

Answer 2

从你的问题开始：线性搜索返回找到键所在位置的索引该函数具有三个参数，数组，搜索起始索引 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 并且您将拥有正确的索引。

Answer 3

你可以使用尾递归：

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

Answer 4

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

递归线性搜索

Recursive Linear Search

algorithm

recursion

return

linear-search