函数的尾递归

Question

我有一个作业问题，提供了递归功能，我必须使用尾递归来实现它。该功能是f（0）= 1 f（n）= 1 + 2 * f（n-1）

我不是最擅长的尾递归，我尝试查找示例，但是我发现的都是带有斐波那契数列的示例，它并没有太大帮助。

我真正拥有的是

def f(n,s=1):
    if n == 0:
        return s
    else:
        return f(n-1, "i dont know what to put here")

我知道尾递归基本上是通过每次调用来计算函数的，我只是不知道如何实现它。编辑：我做了错别字f（n）应该是1 + 2 * f（n-1）

Answer 1

对于尾部递归，您可以随时跟踪总和：

$ cat foo.py 
import sys

def f(n,s=1):
    if n == 0:
        return s
    return f(n-1, 1+2*s)

r = int(sys.argv[1])
print(f(r))

输出：

$ seq 0 10 | xargs -I% python foo.py %
1
3
7
15
31
63
127
255
511
1023
2047

Answer 2

尾递归只是一个递归函数，仅在函数末尾调用自身，因此根据函数的规格，它应该类似于：

def f(n):
    if n == 0:
        return 1
    return 1 + f(n - 1)

Answer 3

它可以很简单：

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