Реализация рекурсии с помощью одного рекурсивного вызова

Question

данной функции следующим образом: F (п) = е (п-1) + F (п-3) + F (п-4)

f(0) = 1 
f(1) = 2 
f(2) = 3 
f(3) = 4 

я знаю реализовать его с помощью рекурсии с тремя рекурсивными вызовами внутри одной функции. Но я хочу сделать это только с одним вызовом рекурсии внутри функции. Как это можно сделать?

Для реализации с использованием 3 рекурсивных вызовов вот мой код:

def recur(n): 
    if n == 0: 
    return 1 
    elif n == 1: 
    return 2 
    elif n == 2: 
    return 3 
    elif n == 3: 
    return 4 
    else: 
    return recur(n-1) + recur(n-3) + recur(n-4) #this breaks the rule because there are 3 calls to recur 

Answer 1

Ваша попытка в правильном направлении, но она нуждается в небольшое изменение:

def main(): 
    while True: 
    n = input("Enter number : ") 
    recur(1,2,3,4,1,int(n)) 

def recur(firstNum,secondNum,thirdNum,fourthNum,counter,n): 
    if counter==n: 
    print (firstNum) 
    return 
    elif counter < n: 
     recur (secondNum,thirdNum,fourthNum,firstNum+secondNum+fourthNum,counter+1,n) 

Answer 2

Это answer в C# может дать вам подсказку, как сделать то, что вы хотите.

Fibbonacci одним рекурсивного вызова в Python выглядит следующим образом:

def main(): 
    while True: 
    n = input("Enter number : ") 
    recur(0,1,1,int(n)) 

def recur(firstNum,secondNum,counter,n): 
    if counter==n : 
    print (firstNum) 
    return 
    elif counter < n 
     recur (secondNum,secondNum+firstNum,counter+1,n) 

Answer 3

На первый взгляд, это выглядит a dynamic programming проблема. Мне очень нравится memoization для таких проблем, потому что он сохраняет код приятным и читаемым, но также дает очень хорошую производительность. Используя python3.2 +, вы можете сделать что-то подобное (вы можете сделать то же самое со старыми версиями python, но вам нужно либо реализовать свой собственный lru_cache, либо установить один из многих сторонних разработчиков, у которых есть похожие инструменты):

import functools 

@functools.lru_cache(128) 
def recur(n): 
    print("computing recur for {}".format(n)) 
    if n == 0: 
    return 1 
    elif n == 1: 
    return 2 
    elif n == 2: 
    return 3 
    elif n == 3: 
    return 4 
    else: 
    return recur(n-1) + recur(n-3) + recur(n-4) 

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

recur(6) 
# computing recur for 6 
# computing recur for 5 
# computing recur for 4 
# computing recur for 3 
# computing recur for 1 
# computing recur for 0 
# computing recur for 2