Преобразование итеративной функции Python в рекурсивную функцию

#python-3.x

Вопрос:

Пожалуйста, рассмотрите 2 пересекающихся люкса:

 U0 = 1
V0 = 2
Un = 2U(n-1)   3 V(n-1)
Vn = U(n-1)   V(n-1)

Я хочу решить эту проблему с помощью этой итеративной функции Python:

 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)

Я бы предпочел рекурсивную функцию, но я понятия не имею, как преобразовать мою функцию.
У тебя есть какие-нибудь идеи?
Спасибо.

Ответ №1:

Так же просто, как:

 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)

Это возможно из-за того, что Python является интерпретируемым динамическим языком программирования.

Редактировать:

 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)

Просто чтобы соответствовать вашей конкретной проблеме/функции.

1. О, ну, это всего лишь один крошечный шаг, который он мог бы понять. Или я все еще могу редактировать.

2. Спасибо. На самом деле это для иллюстрации алгоритмической проблемы, поэтому нет необходимости использовать Python. Python только помогает мне решить эту проблему. Так разве это невозможно только с ОДНОЙ функцией?

3. @Theo да, это было бы невозможно с *статическим языком программирования , таким как Java или C , потому что компилятор будет жаловаться на то, что v не определен при определении u (т. е. статическая проверка)

4. Внедрение одной функции возможно и на самом деле довольно элегантно. Смотрите мой обновленный ответ,

5. «Это было бы невозможно с помощью *статического языка программирования, такого как Java или C » — это неправда. Как Java, так и C допускают взаимно рекурсивные функции. Это не имеет ничего общего с динамичной и интерпретируемой природой языка.

Ответ №2:

Наивная рекурсивная реализация, предложенная @moctarjallo, очень медленная, потому что одни и те же значения приходится вычислять снова и снова. Например, вычисление u(22) занимает смехотворные 0,8 секунды:

 from timeit import timeit
timeit('u(22)', globals=globals(), number=10)
# 8.138428802136332

Рассмотрите возможность использования lru_cache декоратора, который сохраняет ранее вычисленные значения в невидимой таблице и фактически вызывает функции только в том случае, если они ранее не вызывались с теми же параметрами:

 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

Я также сделал код функций немного более идиоматичным. Наслаждайтесь этой разницей!

P.S. Если вы ищете реализацию одной функции:

 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)

Кэширование по-прежнему повышает его производительность на порядки.

1. Пожалуйста, добавьте это в качестве нового ответа, чтобы я мог его озвучить.

2. Кроме того, я не думаю, что производительность-это то, что имело значение для ОП во время постановки вопроса.