使用一个递归调用实现递归

Question

给出如下函数: f(n) = f(n-1) + f(n-3) + f(n-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

回答 in C#可能会给您提供一个如何做您想做的事情的提示。

在Python中使用一个递归调用的Fibbonacci如下所示：

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

乍一看，这似乎是一个动态规划问题。对于这样的问题，我非常喜欢回忆录，因为它保持了代码的良好可读性，但也提供了非常好的性能。使用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)

注意，该函数每n只被调用一次：

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