Please consider 2 crossed suites:
U0 = 1
V0 = 2
Un = 2U(n-1) + 3 V(n-1)
Vn = U(n-1) + V(n-1)
I want to resolve it with this Python iterative function:
def myfunction(n=5):
u = 1
v = 2
for i in range(n):
w = u
u = 2*u + 3*v
v = w + v
return(u,v)
I would prefer a recursive function but I have no idea to convert my function. Do you have any idea? Thanks.
As simple as:
def u(n):
if n == 0:
return 1
else:
return 2*u(n-1) + 3*v(n-1)
def v(n):
if n == 0:
return 2
else:
return u(n-1) + v(n-1)
print((u(5), v(5))) # -> (905, 393)
This is possible due to the nature of Python being an interpreted dynamic programing language.
Edit:
def myfunction(n):
def u(n):
if n == 0:
return 1
else:
return 2*u(n-1) + 3*v(n-1)
def v(n):
if n == 0:
return 2
else:
return u(n-1) + v(n-1)
return u(n), v(n)
print(myfunction(5)) # -> (905, 393)
Just to conform with your exact problem/function.
The naive recursive implementation proposed by @moctarjallo is very slow because the same values have to be calculated over and over again. For example, calculating u(22) takes the ridiculous 0.8 sec:
from timeit import timeit
timeit('u(22)', globals=globals(), number=10)
# 8.138428802136332
Consider using an lru_cache decorator that saves the previously computed values in an invisible table and actually calls the functions only when they have not been called with the same parameters before:
from functools import lru_cache
@lru_cache(None) # decorate with a cache
def fast_u(n):
return 1 if not n else 2 * fast_u(n-1) + 3 * fast_v(n-1)
@lru_cache(None) # decorate with a cache
def fast_v(n):
return 2 if not n else fast_u(n-1) + fast_v(n-1)
timeit('fast_u(22)',globals=globals(), number=10)
#9.34056006371975e-05
I also made the functions code a little more idiomatic. Enjoy the difference!
P.S. If you are looking for a one-function implementation:
def uv(n):
if n == 0: return 1, 2
u, v = uv(n-1)
return 2 * u + 3 * v, u + v
uv(5)
#(905, 393)
Caching still improves its performance by orders of magnitude.