-1

that is the code (I use python 3):

def fibonacci(x):
  if x == 1 or 2:
    return 1
  f = fibonaci(x-1) + fibonaci(x-2) 
  return f

print(fibonacci(4))

What I would like to get as an output is 3, which is the fourth Fibonacci number. However I get 1 as an output.

f = fibonaci(x-1) + fibonaci(x-2)

I think that code does not do what I want it to do. Lets say I would take fibonacci(3) as my input.

What I think should happen:

f = fibonacci(3-1) + fibonacci(3-2)

fibonacci(3-1) and fibonacci(3-2) should both return 1 right? so f should be = 2 and fibonacci(3) should give me 2 as an output. But what I get as an output is still 1. Where is the mistake?

Math Noob
  • 25
  • 1
  • 6
  • 2
    `x == 1 or 2` is always True. – Mark Ransom Aug 04 '20 at 20:01
  • 1
    `f = fibonaci(x-1) + fibonaci(x-2)` ==> `f = fibonacci(x-1) + fibonacci(x-2)` and it is a slow thing – Patrick Artner Aug 04 '20 at 20:07
  • @PatrickArtner yup I saw that now as well, thank you. By slow you mean that the code could have been written more efficiently? I just newly got into recursion, maybe I will be able to write it more smartly in the future :D – Math Noob Aug 04 '20 at 20:18
  • 1
    dont do recursion.use the linear version without recursion from https://stackoverflow.com/a/499245/7505395 - its much faster and less errorprone. Try yours with fibonaci(100) - the linear version takes under 1s to give you all numbers... – Patrick Artner Aug 04 '20 at 20:53
  • Will check that out too, thanks ! I was assigned to do this task by recursion, it was only for the purpose of practice. – Math Noob Aug 04 '20 at 21:53

1 Answers1

3

The mistake is in your if clause. What you meant was probably this:

if x == 1 or x == 2:

as if 2 is always "true", so for any x you will be getting 1.

However, this will still be wrong, as in Fibonacci sequence the first two numbers are 0 and 1, so:

if x <= 1:
    return x
VisioN
  • 143,310
  • 32
  • 282
  • 281