函数的尾递归

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

Tail recursion for a function