CODEWITHSUNDEEP
pythonrecursion
Patrick Miller
Patrick Miller

Reputation: 3

Recursion not terminating in Python

I'm trying to write a program that finds if a given number is in the Fibonacci sequence and I keep getting recursion that doesn't terminate and I'm not sure why. Line 17 seems to be the big problem. When I input 0 or 1 I get the desired answers. Just looking for help getting to an answer, I'm trying to learn so just telling me the answer doesn't help me much.

number = int(input("Enter your number:"))

def fib(n):
        if n == 0 or n == 1:
            return 1
        else:
            return (fib(n-1) + fib(n-2))
def isfib(number):
        n = 0
        if number < 0:
            print("Invalid input")
        elif number == fib(n):
            print("Number is in the sequence")
        elif number < fib(n):
            print("Number is not in the sequence")
        elif number > fib(n):
            n = n +1
            isfib(number) #where the problem occurs
isfib(number)

Upvotes: 0

Views: 246

Answers (5)

iamnotgoogle
iamnotgoogle

Reputation: 294

There are many little mistakes so i corrected those(I have added a better implementation of Fibonacci code with simple addition too):

number = int(input("Enter your number:"))

def fib(n): 
 if n == 0 or n == 1: return 1
 else:
  temp1=1
  temp=2
  temp3=0
  for z in range(n-2):
   temp3=temp
   temp+=temp1
   temp1=temp3
  return temp

def isfib(number): #it is ok not to return anything unless you need to stop the function in between
 done=0
 n=0
 while done!=1:
  if number < 0:
   print("Invalid input")
   done=1
  elif number == fib(n):
   print("Number is in the sequence")
   done=1
  elif number < fib(n):
   print("Number is not in the sequence")
   done=1
  elif number > fib(n):
   n = n +1
#i have used done instead of return to show the function can exit even if you dont return a value
#you can just 'return' instead of changing done variable and making the loop infinite
isfib(number)

Since you have used lot of recursions, i am guessing you want to do it only by using recursions. So, the code will be like this: number = int(input("Enter your number:"))

def fib(n):
 if n == 0 or n == 1: return 1
 else: return (fib(n-1) + fib(n-2))
def isfib(number,n=0):
 if number < 0: print("Invalid input")
 elif number == fib(n): print("Number is in the sequence")
 elif number < fib(n): print("Number is not in the sequence")
 elif number > fib(n):
  n = n +1
  isfib(number,n)
isfib(number)

Tested of course, it works(but again i wouldn't recommend it this way :D)

Upvotes: 1

tomcy
tomcy

Reputation: 455

I don't really know why you want to use recursive to solve this question. When you get a number, you don't know what are n-1 and n-2. Therefore, you cannot recursive on n-1 and n-2. The following example can easily check the number is in Fibonacci sequence or not:

number = int(input("Enter your number:"))
def fib(n):
    ni = 1
    ni_minus_1 = 0
    while ni + ni_minus_1 < n:
        temp = ni_minus_1
        ni_minus_1 = ni
        ni = ni + temp
    if ni + ni_minus_1 == n:
        return True
    return False

print(fib(number))

update
I guess you want to build the sequence by recursive. For example, given number is 5, you want to return the 5th element in Fibonacci sequence. Then the code would be like the following:

def build_fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return build_fib(n-1) + build_fib(n-2)
print(build_fib(6))

Upvotes: 0

Rob Gardner
Rob Gardner

Reputation: 211

Put simply, you are calling isfib(number) with the very same number you were given originally. Your "n = n + 1" just before that suggests that maybe you wanted to call isfib(n) not isfib(number).

Basically isfib(number) is just an infinite loop.

Upvotes: 0

Fgbruna
Fgbruna

Reputation: 127

The last elif of the isfib() function is not returning a call of itself,i.e it is calling itself and not doing anything with that result.

Upvotes: 0

Diiru
Diiru

Reputation: 97

Your fib function is wrong (one of the terms should be n-2)

Upvotes: 0

Related Questions