通过递归生成元素列表

Question

我有以下递归关系 H(n) = 2*H(n-1) + 1, H(1) = 1。如果我要在 python 中创建一个递归函数，这看起来会怎样？我尝试了以下方法，但它似乎不起作用

def rec_func(N, n=0, H=[])
    if n == 1:
        return [1] + H
    else:

        return rec_fun(N-1, n+1, H)

我可能完全偏离了，但任何提示都将不胜感激。它应该是 return 元素列表 [H(1), H(2),...H(N)]

请注意，构造函数中的 n=0, H=[] 是必需的。这是我教科书中的练习 "Numerical Analysis"

Answer 1

试试这个：

# h(n) = 2 * h(n - 1) + 1
# h(1) = 1

def get_h_series(n):
    if n == 1:
        # h(1) = 1
        return [1]
    else:
        # ans = [h(0), h(1), ..., h(n - 1)]
        ans = get_h_series(n-1)
        # Append h(n) which is 2 * h(n - 1) + 1.
        ans.append(2 * ans[-1] + 1)
        # [h(0), h(1), ..., h(n - 1), h(n)]
        return ans

print(get_h_series(5))

输出：

[1, 3, 7, 15, 31]

Answer 2

如果你想做一个递归函数就这样做：

def H(n):
    if n == 1:
        return 1
    else:
        return 2*H(n-1)+1

如果你希望输出是一个列表，你必须做类似的事情：

def H_with_list(n, list_final):
    if n == 1:
        list_final.append(1)
        return list_final
    else:
        list_temp = H_with_list(n-1, list_final)
        list_final.append(2*list_temp[-1]+1)
        return list_final

小心递归函数很耗时，你应该计算H(n)并用一行代码让它工作

Answer 3

像这样：

def rec_func(n=1, H=[]):
    if not H:
        H = [None] * (n+1)

    if n == 1:
        H[n] = 1
    else:
        H =  rec_func(n-1, H)
        H[n] = 2 * H[n-1] + 1

    return H 

H = rec_func(3)

print(H) // prints -> [None, 1, 3, 7]

Answer 4

虽然其他答案会按照您的要求递归解决此问题，但值得一提的是，使用迭代解决此问题并不太难或很难看。如果您想使用较大的 n 值，您的代码可能会因 RuntimeError maximum recursion depth exceeded in comparison 或堆栈溢出 (heh) 而失败。您可以通过迭代实现它来解决这个问题，例如：

def list_h_results(n):
    h_results = []
    for i in range(1, n+1):
        h_results.append(2 * h_results[-1] + 1)
    return h_results

我并不是说你的练习一定要这样做，但如果在实际代码中实现这种功能，这是一个值得考虑的问题。此类问题通常选择递归，因为它优雅且更容易理解，但我认为在这种情况下，迭代解决方案同样易于理解，并且避免了与深度递归相关的潜在问题。

Answer 5

这是另一种不需要像 temp[-1] 这样的查找的方法，因为计算是运行

def main(n, a=1):
  if n<=1:
    return [a]
  else:
    return [a, *main(n-1, 2*a+1)]

print(main(10))
# [ 1, 3, 7, 15, 31, 63, 127, 511, 1023 ]

print(main(1))
# [1]

通过递归生成元素列表

Generate list of elements by recursion

python

python-3.x

recursion

recurrence