Converting Python iterative function to recursive function

user_12647630 0
Viewed 107

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.

python-3.x
2 Answers

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.

user_61013360

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.

user_44929320
Related