Implement Recursion Using One Recursive Call

Given a function as follow : 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 func

Solution 1:

Your attempt is in the right direction but it needs a slight change:

defmain():
  whileTrue:
    n = input("Enter number : ")
    recur(1,2,3,4,1,int(n))

defrecur(firstNum,secondNum,thirdNum,fourthNum,counter,n):  
  if counter==n:
     print (firstNum)
     returnelif counter < n:
      recur (secondNum,thirdNum,fourthNum,firstNum+secondNum+fourthNum,counter+1,n)

Solution 2:

This answer in C# may give you a hint how to do what you want.

Fibbonacci with one recursive call in Python is as follows:

defmain():
  whileTrue:
    n = input("Enter number : ")
    recur(0,1,1,int(n))

defrecur(firstNum,secondNum,counter,n):
  if counter==n :
     print (firstNum)
     returnelif counter < n
      recur (secondNum,secondNum+firstNum,counter+1,n)

Solution 3:

At first glance, this looks like a dynamic programming problem. I really like memoization for problems like this because it keeps the code nice and readable, but also gives very good performance. Using python3.2+ you could do something like this (you can do the same thing with older python versions but you'll need to either implement your own lru_cache or install one of the many 3rd party that have similar tools):

import functools

@functools.lru_cache(128)defrecur(n):
  print("computing recur for {}".format(n))
  if n == 0:
     return1elif n == 1:
     return2elif n == 2:
     return3elif n == 3:
     return4else:
     return recur(n-1) + recur(n-3) + recur(n-4)

Notice that the function only gets 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