python - 使用递归的最后一个索引

Question

我必须编写一个递归函数 lastIndex()，它接受一个列表和一个值作为参数，返回列表中最后一次出现的值的索引。如果在列表中找不到该值或列表为空，则该函数返回 -1。该函数必须是递归的，并且作为参数提供的列表不能被修改。例子：

>>>lastIndex([1,2,3,4,5,1],1)
5
>>>lastIndex([1,4,7,2,3,2],3)
4

我当前的代码：

def lastIndex(lst,n):
    if lst[0] ==n:
        return -1
    else:
        1 + lastIndex(lst[1:],n)

Answer 1

正如我对您之前的作业问题的回答中提到的，递归包括两件事：

• 一个基本案例
• 一种基于更接近基础问题的答案的问题答案的方法

在这种情况下，您可能正在寻找的基本情况是一个空列表。

将问题与较小问题联系起来的方法是将输入列表分成两部分：输入的最后一个元素和最后一个元素之前的元素列表。最后一个元素之前的元素列表是您的小问题；最后一个要素是您如何决定是否需要解决较小的问题。

---

考虑这组问题：

• 我输入的最后一个元素是我正在寻找的元素吗？如果是这样，它之前有多少个元素？
• 否则，如果我删除当前的最后一个元素并重试，上述问题的答案是什么？

在这种情况下，递归就是“重试”。

Answer 2

这个怎么样？它是尾递归的。

>>> def lastIndex(lst,n,c=None):
...     if c is None:
...        c = len(lst)-1
...     if c < 0:
...         return -1
...     elif lst[c] == n:
...         return c
...     else:
...         return lastIndex(lst, n, c-1)
... 
>>> lastIndex([1,2,3,4,5,1],1)
5
>>> lastIndex([1,4,7,2,3,2],3)
4

Answer 3

def lastindex(lst, what_to_find, start_length=None, depth=0):
    if not start_length:
        start_length=len(lst)-1
    if not lst:
        return -1
    elif lst[-1]==what_to_find:
        return start_length - depth
    else:
        return lastindex(lst[:-1], what_to_find, start_length, depth+1)

我认为这已经足够了。

>>> lastindex([0,0,0,0,0,2],3)
-1
>>> lastindex([1,2,3,4,5,6],3)
2
>>> lastindex([1,2,3,4,5,1],1)
5
>>>