递归寻找元素来列表中的索引的几种方法

Python版：递归寻找元素来列表中的索引的几种方法

首先，最经典的肯定是：

def find_index(aList, value):
	if aList[0] == value:
		return 0
	return 1 + find_index(aList[1:], value)

其中，if 语句中是基础条件，即当 aList 第0个元素等于 value 的时候，会返回 0。而其他情况下，会不断递归地寻找。但可惜的是，如果要找的 value 不在 aList 中，则会报错。

一种解决方法是，在开头加上：

1 2	if value not in aList: return -1

但是这样做的话，效率会很低。当然，我们也可以用 try-except 语句获取错误。

def find_index(aList, value, index=0):
	try:
		if aList[index] == value:
			return index
	except IndexError:
		return -1

	return find_index(aList, value, index+1)

上述的方法比我们第一份代码效率要高，因为 aList[1:] 的开销会比直接aList[index]大。

最后一种方法挺巧妙的，如下：

def find_index(aList, value):
    if aList == []:
        return -1
    elif aList[0] == value:
        return 0
    rv = find_index(aList[1:], value)
    if rv < 0:
        return rv
    return rv + 1

我觉得最巧妙的在于第6行，这里算出了 rv 的值之后没有直接 return，而是先判断是否小于0，如果条件满足，说明了 rv = -1 即要么是空列表的情况，要么是 value 不在 aList 的情况。因为如果value不在aList，由于第6行的代码会一直递归调用下去，直到 aList[1:] = [ ] ，而此时会 return -1 。

而第9行的存在的意义在我看来是：由于这是个递归算法，对于这个 find_index 函数必须有返回值，而 return 不能只存在于 if 或者 elif 语句中（因为如果不进入这两个语句则不会 return，递归算法是必须要有返回值）

第9行代码的作用在我看来：假设一个列表有 n 个元素，且要找的 value 不在 aList 中时。每运行第6行的代码会再次调用 find_index 函数本身，可认为调用栈将 find_index 函数压入 (push) 到栈顶。第9行的代码则是为每次递归结束（栈顶压出）所得到的返回值。

整个函数可以用数学的方法来分析：

假设是一个空列表，返回值为 -1。
假设是一个大小为n的列表（n=1），且 value 在 aList 中。返回值为 0。
假设是一个大小为n的列表（n=1），且 value 不在 aList 中。由于不满足前面 1和2，所以需要计算 rv 的值。但是 aList[1:] = [ ] ，返回值为 -1。
假设是一个大小为n的列表（n>1），且 value 在 aList 中。函数运行到第6行会“卡住”，这个时候递归调用自身，而调用栈会将这个“卡住”的地方压到栈顶。在未找到value的时候，可以认为一直在执行 2～6行代码。直到我们找到 value，则会类似上述2，返回值为0 。然后将这时的栈顶出栈，继续执行7～9行代码，由于 rv = 0，所以 return 1。但注意，如果还有 find_index 函数在栈中，则需要一个个将它们压出栈，压出栈之后，还记得执行7～9行代码。
假设是一个大小为n的列表（n>1），且 value 不在 aList 中。这种情况与4类似，但是需要递归直到 aList = [ ] ，这个时候计算出来的 rv显然等于 -1，则直接 return -1，如果还有 find_index 函数在栈中，则需要一个个将它们压出栈，压出栈之后，还记得执行7～9行代码。

上述的就是今日跟大家分享的一道递归题目，写了点自己对代码的理解。欢迎大家一起交流，有错误欢迎在微信公众号留言或在文章处评论。（本文也曾在我的个人微信公众号里发过）

Vincent Huang