python - 转换基于在 python 中的每个循环上更新的中间值的循环的功能方法

Question

我的标题可能不是很直接，但基本上，我想将以下使用 for 循环编写的代码更改为递归函数。

import numpy as np
irrel_pos = range(3, 11)
n_extra_pos = [2, 3]
extra_pos = []
rs = np.random.RandomState(1)
for i in range(len(n_extra_pos)):
    sample_i = rs.choice(list(irrel_pos), n_extra_pos[i], replace=False)
    extra_pos.append(set(sample_i))
    irrel_pos = set(irrel_pos) - set(extra_pos[i])

print(irrel_pos)
print(extra_pos)

输出:

{8, 9, 3}
[{10, 5}, {4, 6, 7}]

这里的代码在第一个循环中包含两个来自 irrel_pos 的样本项，在第二个循环中包含三个样本项，但是在进入第二个循环之前需要删除在第一个循环中采样的项目。

我试图理解这个问题的函数式方法，如何将其转换为递归函数？

Answer 1

不要纠结于为什么你想这样做，至少有两种不同的方法。这在很大程度上取决于您是否希望调用成为尾调用(这允许编译器优化许多严格的函数式语言中的函数调用——尽管不是 Python)，或者您是否想要更直接的递归函数。

直接的实现是

import numpy as np

def recursive(rs, n_extra_pos, irrel_pos):
    if n_extra_pos == []:
        return [], irrel_pos
    extra_pos, irrel_pos = recursive(rs, n_extra_pos[:-1], irrel_pos)
    sample = set(rs.choice(list(irrel_pos), n_extra_pos[-1], replace=False))
    return extra_pos + [sample], irrel_pos - sample

irrel_pos = set(range(3, 11))
n_extra_pos = [2, 3]
rs = np.random.RandomState(1)
extra_pos, irrel_pos = recursive(rs, n_extra_pos, irrel_pos)
print(extra_pos, irrel_pos)

在这个实现中，首先我们递归地调用自己，直到 n_extra_pos 的所有元素都被消耗，然后在通过调用堆栈返回时，我们进行所需的计算并更新结果。可以看出，递归调用不是这里发生的最后一件事，因此 TCO(尾调用优化)是不可能的。

为了创建一个允许 TCO 的函数，我们需要使用累加器，而不是首先到达调用堆栈的底部，我们将在向下的过程中进行计算，可以这么说，在这样做的同时，我们将添加结果到我们的累加器(extra_pos 和 irrel_pos)。然后，当到达底部时，我们所要做的就是归还累加器。一个实现是

import numpy as np

def tail_recursive(rs, n_extra_pos, extra_pos, irrel_pos):
    if n_extra_pos == []:
        return extra_pos, irrel_pos
    sample = set(rs.choice(list(irrel_pos), n_extra_pos[0], replace=False))
    return tail_recursive(rs, n_extra_pos[1:], 
                          extra_pos + [sample], irrel_pos - sample)

irrel_pos = set(range(3, 11))
n_extra_pos = [2, 3]
rs = np.random.RandomState(1)
extra_pos, irrel_pos = tail_recursive(rs, n_extra_pos, [], irrel_pos)
print(extra_pos, irrel_pos)

但是，如前所述，TCO 在 Python 中不可用，这使得递归函数不太有用，从而使 Python 不是函数式编程的最佳选择，除了使用内置的 map， reduce(在 functools 中可用)和 filter 函数，当然还有列表理解。