0

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)
Improve this question
2
  • The number of function calls that are required to compute fib(n) is 2^n with your implementation. This will never terminate for mediumish values of n. There is a more efficient way to compute that function. Commented Jan 30, 2017 at 1:18
  • Check out the answer i have added, both with recursion and without recursion. Commented Jan 30, 2017 at 1:57

5 Answers 5

Reset to default
1

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)

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

2 Comments

Thanks that's pretty much exactly how I ended up doing it after I realized I was resetting the value of n to 0 after each one of my recursive calls. Except my last elif was simply; isfib(n+1).
Just simplifying it for understandibility :D
0

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

Improve this answer

2 Comments

Thanks for that, I missed that but it still doesn't fix my recursion issue.
Your function never ends because it never returns anything. You should add some returns in the places where you print things, that will probably do.
0

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.

Improve this answer

6 Comments

But it's also adding 1 to n so shouldn't it be checking the next number in the fib sequence? So the next time it calls it should be checking the value against fib(n+1) instead.
Yes,but the argument of your function is number so you are basically not changing it at any point of the function
@PatrickMiller Its not adding 1 to n because you are calling the function again and that results in n going to 0 because you have defined it so. Also by using recursion you are still inside your earlier function which is a very dangerous thing for big numbers
That makes sense, I didn't even realize I was resetting the value of n back to 0 every time. Thank you.
It's doing exactly what I wanted to to do now, I realized exactly how to fix it once you told me I was resetting the value to n = 0 after every call.
|
0

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.

Improve this answer

1 Comment

Well n is the fib value, so isn't it changing fib(n) to fib(n+1) after each call and thus checking my number against the next fib vaul until it's equal to or greater than my input number. If I call isfib(n) then I'm not checking if my input value is in the sequence
0

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))
Improve this answer

1 Comment

What I'm trying to do is find if the input number is in the sequence. So if I input 5 it'd return true but if I input 4 it'd return false. I have to build the sequence recursively because that's how I was asked to do it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.