CODEWITHSUNDEEP
pythonrecursiontail-recursion
Jeremy Maldonado
Jeremy Maldonado

Reputation: 11

Tail recursion for a function

I have a homework problem that gives a recursive function and I have to implement it using tail-recursion. The function is
f(0) = 1
f(n) = 1+2*f(n-1)

I am not the best at tail-recursion and i tried to look up examples but all i find are examples witht the fibonacci sequence and it doesnt help much.

All i really have is

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

I understand that tail recursion basically computes the function every call through i just dont know how to implement it.
Edit: I made a typo f(n) is supposed to be 1 + 2*f(n-1)

Upvotes: 0

Views: 44

Answers (1)

richyen
richyen

Reputation: 9958

For tail recursion, you track the sum as you go:

$ 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))

Output:

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

Upvotes: 1

Related Questions