如何将for循环转换为递归方法？

Question

目前,我实现了一个for循环作为递归方法.

for i in range(len(list)):
   **implementation code goes here**

我如何实现这个作为递归方法？

我打算浏览一个列表,检查每个项目是否在另一个已接受的可能值列表中.如果是这样,我会采取某些行动.否则,我会采取其他行动.

Answer 1

标准的结构递归公式(以及你使用像Scheme这样的函数式语言时使用的公式)将是递归地解构列表:

func([]) => nothing
func([x, ...]) => do_stuff(x), func([...])

因此,执行此操作的"功能"方法是获取单个列表(而不是索引),并在较小的列表上递归:

def rec_list(l):
    if not l: return # empty list case
    # process l[0]
    return rec_list(l[1:])

请注意,这非常非常低效,因为l[1:]它是理解更复杂的递归构造(例如,在二叉树上递归)的基础.

我们可以用这种结构递归来做有趣的事情.例如,以下是您在函数式语言中反转列表的方法:

def rev_list(l):
    if not l: return []
    return rev_list(l[1:]) + [l[0]]

(当然,你可以l[::-1]用Python 做,但在这里我们试图展示如何以递归方式完成).