有人可以帮助我完成我的递归代码吗?以下是我的理解方式(但我认为我没有正确地单步执行代码):
如果(第一个 > 最后一个)返回 -1
- 其他
if ( result == 0 ) 返回最后一个
否则返回 SeqSearch (data,first,last-1,key)
- 重新启动该方法,但将
last
设为last-1
("keller") - 重复步骤 1、2 和 3
否则返回 SeqSearch(data,first,last-1,key)
- 重新启动该方法,但将
last
设为last-1
(“6”) - 等等...
这是我的代码:
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);
}
}
最佳答案
理解递归函数的一个好方法是将其分解为基本情况和递归情况。
这个SeqSearch
有两个基本情况:
1。未找到
if (first > last)
return -1;
2。发现值
if (data[last].compareTo(key) == 0)
return last;
现在,只剩下递归情况了。在这里,我们只有一种递归情况,但也可能有多种。
现在,在设计递归函数时,您必须确保每个递归调用都比以前的调用减少,或者更简单,从某种意义上说,我们每次都更接近一个基本情况。这和Induction的数学概念有很大关系。 .
因此,对递归情况的每次调用都必须向答案靠近一步。* 这里我们看到 last
的值通过减一而减少,每一步都使其接近于零。
反过来,这意味着该函数引用 data
数组的越来越小的子集;从概念上讲,这类似于将一个较小的数组传递给递归调用,该数组少了一个元素。
此时,基本情况开始有意义:
当
first
大于last
时,我们得到一个没有元素的数组:列表的tail已经超过了它的头。找到搜索键后,我们将其索引作为结果返回。
这个函数很奇特(在搜索函数中),因为它从列表的末尾找到第一个匹配的索引;更常见的操作是从列表的开头中查找第一个匹配的索引。
这可以通过递增first
而不是递减last
来实现。这仍然算作减少——即使它是增加——因为递归步骤严格小于原始步骤。
* 这意味着每个递归调用比前一个递归调用“简单”得多;因此,如果您可以随时理解问题,那么下一步应该会更简单;唯一的复杂之处在于它嵌套在原始步骤中。
关于java - 我对这个递归的理解正确吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29995529/