java - 我对这个递归的理解正确吗？

Question

有人可以帮助我完成我的递归代码吗？以下是我的理解方式(但我认为我没有正确地单步执行代码):

1. 如果(第一个 > 最后一个)返回 -1
2. 其他
3. if ( result == 0 ) 返回最后一个
4. 否则返回 SeqSearch (data,first,last-1,key)
5. 重新启动该方法，但将 last 设为 last-1 ("keller")
6. 重复步骤 1、2 和 3
7. 否则返回 SeqSearch(data,first,last-1,key)
8. 重新启动该方法，但将 last 设为 last-1(“6”)
9. 等等...

这是我的代码:

public static void main (String[] args)
{
    String[] data = new String[]{"help","jackson","six","keller","mean"};
    int first = 0;
    int last = data.length-1;
    String key ="help";
    System.out.println(SeqSearch(data,first,last,key));
}
public static int SeqSearch(String[] data,int first,int last,String key)
{
    if(first > last)
        return -1;
    else{
        int result = data[last].compareTo(key);
        if(result == 0)
            return last;
        else
            return SeqSearch(data,first,last-1,key);
    }
}

Answer 1

理解递归函数的一个好方法是将其分解为基本情况和递归情况。

这个SeqSearch有两个基本情况:

1。未找到

if (first > last)
    return -1;

2。发现值

if (data[last].compareTo(key) == 0)
    return last;

现在，只剩下递归情况了。在这里，我们只有一种递归情况，但也可能有多种。

现在，在设计递归函数时，您必须确保每个递归调用都比以前的调用减少，或者更简单，从某种意义上说，我们每次都更接近一个基本情况。这和Induction的数学概念有很大关系。 .

因此，对递归情况的每次调用都必须向答案靠近一步。^* 这里我们看到 last 的值通过减一而减少，每一步都使其接近于零。

反过来，这意味着该函数引用 data 数组的越来越小的子集；从概念上讲，这类似于将一个较小的数组传递给递归调用，该数组少了一个元素。

此时，基本情况开始有意义:

1. 当first大于last时，我们得到一个没有元素的数组:列表的tail已经超过了它的头。

2. 找到搜索键后，我们将其索引作为结果返回。

这个函数很奇特(在搜索函数中)，因为它从列表的末尾找到第一个匹配的索引；更常见的操作是从列表的开头中查找第一个匹配的索引。

这可以通过递增first而不是递减last来实现。这仍然算作减少——即使它是增加——因为递归步骤严格小于原始步骤。

<小时/>

^* 这意味着每个递归调用比前一个递归调用“简单”得多；因此，如果您可以随时理解问题，那么下一步应该会更简单；唯一的复杂之处在于它嵌套在原始步骤中。