Implement recursion using one recursive call

Question

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 function. But I want to do it with only one recursion call inside the function. How it can be done ?

To implement using 3 recursive calls here is 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

sgp · Accepted Answer · 2015-06-01 09:44:56Z

2

Your attempt is in the right direction but it needs a slight 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)

edited Jun 1, 2015 at 9:44

answered Jun 1, 2015 at 5:45

sgp

1,7787 gold badges17 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

ms8 Over a year ago

It only gives 1 as output..:/. Reason being 1 is always then then any n so it will always display 1

sgp Over a year ago

@python_slayer Oops. Check the edit. Is it fine now?

Community · Accepted Answer · 2017-05-23 11:53:27Z

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:

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)

edited May 23, 2017 at 11:53

CommunityBot

11 silver badge

answered Jun 1, 2015 at 4:41

George Hanna

3922 silver badges15 bronze badges

3 Comments

ms8 Over a year ago

I did something like that but getting 14 for n=5 . Here is my code :ideone.com/8zk4kI

ms8 Over a year ago

I dont want fibonacci number. Please see problem :/

George Hanna Over a year ago

Ohh I am so sorry, I misunderstood.

Bi Rico · Accepted Answer · 2015-06-01 06:43:47Z

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)
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)

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

Collectives™ on Stack Overflow

Implement recursion using one recursive call

3 Answers 3

2 Comments

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related