Recursive implementation using one recursive call
Given the following function: f (n) = f (n-1) + f (n-3) + f (n-4)
f(0) = 1 f(1) = 2 f(2) = 3 f(3) = 4
I know to implement it using recursion with three recursive calls inside one function. But I want to do it with only one recursion call inside the function. How can I do that?
For an implementation using 3 recursive calls, here's my code:
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
source to share
Your attempt is in the right direction, but it needs a little change:
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)
source to share
This answer in C # can give you a hint on how to do what you want.
Fibonacci with one recursive call in Python looks like this:
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)
source to share
At first glance, this looks like dynamic programming . I really like memoization for problems like this because it keeps the code nice and readable, but it also gives very good performance. Using python3.2+ you can do something like this (you can do the same with older versions of python, but you either need to implement your own lru_cache or install one of the many third-party developers who have similar tools):
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)
Note that the function is only called once per 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
source to share