 Hi all
Two questions regarding :
RECURSION VS. ITERATION - CODING THROWDOWN

# When Fibs Are Good

One , in calculations for fibonacci when we ask for a 3rd number in sequence we actually return the 4th one in the set. Why is that i think i don’t understand something.
for fibonacci(3) the list is [0, 1, 1, 2] and we return  but it’s the fourth element .

Secondly I only started learning but I have read in multiple places how important code readability is and I think the recommended way of solving this exercise is unnecessarily complicated especially for beginners.

Is there any advantage to that way over my way ?

Code :

``````#readable
def xfibonacci(n):

result = 0
first = 0
second = 1

for i in range(n-1):
result = first + second
first = second
second = result
print(result)
return result

def fibonacci(n):
fibs = [0, 1]
if n <= len(fibs) - 1:
return fibs[n]
else:
idx = 2
while n > len(fibs) - 1 :
nx = fibs[idx - 1] + fibs [idx - 2]
fibs.append(nx)
idx += 1
print (fibs)
print(fibs[n])
return fibs[n]

# test cases
print(fibonacci(3) == 2)
print(fibonacci(7) == 13)
print(fibonacci(0) == 0)
``````
2 Likes

this is because in arrays we start counting from 0. this means if you want the fourth element in a array. you count 0,1,2,3. so 3 would be the fourth element.

1 Like

The diffrence is the efficience of the code. Sometimes you want something rather to be efficient than readable. A slow program is still slow even if its readable after all.

Here is youre code with a time test in it. if you run it you will see the function from codecadamy is faster.

``````import time

def xfibonacci(n):

result = 0
first = 0
second = 1

for i in range(n-1):
result = first + second
first = second
second = result
return result

def fibonacci(n):
fibs = [0, 1]
if n <= len(fibs) - 1:
return fibs[n]
else:
idx = 2
while n > len(fibs) - 1 :
nx = fibs[idx - 1] + fibs [idx - 2]
fibs.append(nx)
idx += 1
return fibs[n]

t0 = time.time()
print(xfibonacci(3) == 2)
print(xfibonacci(7) == 13)
print(xfibonacci(0) == 0)
t1 = time.time()
print(t1-t0)

t0 = time.time()
print(fibonacci(3) == 2)
print(fibonacci(7) == 13)
print(fibonacci(0) == 0)
t1 = time.time()
print(t1-t0)

``````
1 Like

Thanks for reply birra but unless I’m missing something my way is actually faster , i might be wrong.

xfibonacci
1.3589859008789062 e^-5 = 0.00915677497

fibonacci
9.298324584960938 e^-6 = 0.0230482423

Is that right or am I reading it wrong lol
Math unfortunately is not my strong point. I know I should probably work on that as well.

1 Like

neither of them recurses

The codecademy-provided solution does have some issues.

• it uses an intermediary data structure which can be cut out.
• it is using more control flow than they need to. It would suffice to loop until the list is long enough, then present the answer. (the if-else is redundant)
• it chooses to nest the while-loop inside the else-branch of the if-statement. this really bothers me, it is already exclusive to the if-branch and there is therefore no need to start walking off to the right side of the screen, better to keep the structure as flat as possible. in fact, the else keyword (and de-indent) could be removed without any change at all to the program’s behaviour.
• it both prints and returns. it should make up its mind on how the result is presented.

Addressing the last three points gives code that shows that the idea is nice, even if the implementation is not. Iterate until there’s enough, return last one. <- it’s obvious. that’s good.

Yours could be simplified too.

• Your result variable is redundant, you only need to remember two at a time.
• I think I’d rather let it do an extra iteration by removing the -1. -1’s are weird. I start looking for bugs and edge cases when I see -1’s.
• It’s difficult to see how variables relate to each other in your loop, I would rather see:
``````first, second = second, second + first
``````

(this is what makes the result variable redundant. you needed it to swap. but you also used it for storing the result, and that weirds me out. it should probably be named `tmp`, but using the above syntax is even nicer)

And then a very minor detail, I’d rename `i` to `_` to indicate that I don’t care about its value. It’s not a special name, you can think of it as alternate spelling of “ignore”. `i` is fine though.

1 Like

Recursive versions:

``````from functools import lru_cache

@lru_cache()
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)

def fib2(n, cur=0, nxt=1):
if n == 0:
return cur
return fib2(n-1, nxt, cur+nxt)

``````
2 Likes

Given this solution code,

``````def fibonacci(n):
fibs = [0, 1]
if n <= len(fibs) - 1:
return fibs[n]
else:
idx = 2
while n > len(fibs) - 1 :
nx = fibs[idx - 1] + fibs [idx - 2]
fibs.append(nx)
idx += 1
#return fibs[n]
return fibs
``````

I’m wondering why it gives twenty-one terms, instead of twenty?

``````[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
``````

This code returns twenty…

``````def fibonacci_seq(n):
fib = [0,1]
for _ in [''] * (n - 2):
fib.append(sum(fib[-2:]))
return fib
``````
``````[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
``````

Which one is correct?

https://www.miniwebtool.com/list-of-fibonacci-numbers/?number=20

1 Like

Thanks ionatan, that makes a lot of sense.
Just to clarify.
I am in no position to criticise anybody’s code I’m a toddler when it comes to programming.
At this point readability for me is paramount. It’s a win if I understand anything Thanks for your comment, even thou I don’t understand it entirely it’s food for thought.
Finding questions is as important as finding answers in my experience.

Cheers

mtf I can almost guarantee that my code is not correct I work only to pass the tests.
And I start the sequence with index at 2 maybe that’s why. I am very inexperienced this was the only way that came to mind.

So you know, it’s the CC solution code that I hope is in question, and even that indirectly. All I really ask is, what is the twentieth fibonacci? Nothing is said about the actual code.

You’re in perfectly good position to question things that don’t seem to add up so long as you can argue for it.

1 Like

That is due to this loop header:

``````    while n > len(fibs) - 1 :
``````

Let’s assume that `n` has the value `20`. At the time when the `len` of `fibs` has grown to `20`, that condition still evaluates to `True`. Within the loop, another item gets added, and we have twenty-one terms. Next time around, the condition evaluates to `False`, the loop is terminated, and our `return` value contains those twenty-one terms.

If we agree that `fibonacci(0)` should evaluate to `0`, as does the site that you cited, then we also will agree that `fibonacci(20)` should evaluate to `6765`. Since we are defining Fibonacci numbers starting with an `n` of `0` giving a result of `0`, we need a sequence of twenty-one Fibonacci numbers for it to include `fibonacci(20)`.

On the site that you cited, we need to do this to get that result, since it is essentially asking how many terms we want: This commented-out code does suggest that it was the original intent of the function to include `fibonacci(n)` as the final term:

``````#return fibs[n]
``````

The final term provided by your first code sample does correctly correspond to `fibonacci(n)`, if we do indeed agree that `fibonacci(0)` evaluates to `0`.

Whether the second code sample is correct or not depends upon what `n` represents. If it represents the number of items we want, then it is correct. However the final item in the sequence is not `fibonacci(n)`, if we agree that the Fibonacci sequence begins with `0`.

Edited on December 21, 2018 to identify what was likely the original intent of the first code sample.

If we’re given to understand that term subscripts are natural numbers, then all that matters is where we start. Whether on zero or one (for non-negative sequence)

``````Tn  where n is N
``````

By this reckoning, and what I used in my example, the smallest value for n is 1, since 0 is Real, not Natural.

``````fibonacci_seq(20)
``````

is intended to generate twenty terms. There is no term 0. Only term 1, which returns 0. If we shift the sequence to start on 1, then the twentieth term is 6765. Using natural numbers to count the terms seems intuitive, and the way I learned sequences way back when.

``````a1, a2, ... a(n-1), a(n)
``````

Essentially,

``f0 == t1``
1 Like

I was first introduced to the Fibonacci sequence with its beginning with 1, 1. More recently I’ve seen many discussions that initiate the series with 0, 1. Somewhere, I have even seen a discussion that initiates the sequence with 1, 2, but am at a loss to find it.

Just to add to the menagerie of Fibonacci functions, here’s one that’s featured on the home page of python.org:

``````# Python 3: Fibonacci series up to n
def fib(n):
a, b = 0, 1
while a < n:
print(a, end=' ')
a, b = b, a+b
print()
fib(1000)
``````

Output:

``0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987``
1 Like

I recall that type of problem, as well, but from where and when, who can say. It makes `n` the upper limit, resulting in 17 terms, so t17 is 987, and t20 is 4181.

Clearly any problem needs to be spelled out as to what n represents.

``````n = 0   INTEGER  f(20) = 6765
n = 1   NATURAL  f(20) = 4181
n = x   f(n) <= x    f(20) = 0, 1, 1, 2, 3, 5, 8, 13``````
1 Like

The On-Line Encyclopedia of Integer Sequences references the Fibonacci numbers here: A000045.

They offer this formula, with a starting index of 0:

Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.

However, that does not necessarily settle the matter of where to start the indexing.

1 Like

If we first learned of it as associated with the Golden Ratio, we would have seen the tile example, that has two `1` tiles, and one of `2`, `3`, `5`, …, with no zero. All the starting point means is a different tn, and technically, this sequence does go to t20 = 6765, where n is Natural and t1, t2 = 1, 1.

``````>>> def fibonacci_seq(n):
fib = [1,1]
for _ in [''] * (n - 2):
fib.append(sum(fib[-2:]))
return fib

>>> fibonacci_seq(20)
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
>>>
``````

By subtraction, though, zero can be inferred in the sequence, but as undefined, and therefore having no tile.

The sequence itself doesn’t have a beginning or end if we view it as a fixed interval of terms that can be shifted right and left through the sequence. Given a general term that takes two inputs.

``````-infinity < f(n) < infinity;
``````

Bottom line, we need to know the parameters to be certain of the result. I would hate the be the student who was always off by one.

``````>>> def fibonacci_term(n):
return fibonacci_seq(n)[-1]

>>> fibonacci_term(20)
6765
>>>
``````

Edited to correct error (literal) in code

1 Like

So they are adopting the zero inclusive model with a t0. Needless to say, this could still be subjective. Go back to the tile demonstration.

The point is we cannot argue for one or the other. I’m going to spend the weekend looking for papers from his era to see how he discovered the sequence. I’ll bet even he had an idea of the rolling interval. A train track has about 6000 ties per mile. Imagine each one of them as a Fibonacci number. The train itself does not have an infinite length, hardly. In our parts they’re around 2 miles long. They’re not stationary for long, if at all. What are the numbers between the locomotive and the caboose at any particular time?

In the Fibonacci sequence, each number is the sum of the previous two numbers. Fibonacci omitted the “0” included today and began the sequence with 1, 1, 2 … He carried the calculation up to the thirteenth place, the value 233, though another manuscript carries it to the next place: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377. Fibonacci did not speak about the golden ratio as the limit of the ratio of consecutive numbers in this sequence.
https://en.wikipedia.org/wiki/Fibonacci

``````>>> def fibonacci_term(n):
if n < 1: return 0
fib = [1,1]
for _ in [''] * (n - 2):
fib = [fib[-1], fib[-2] + fib[-1]]
return fib[-1]

>>> fibonacci_term(13)
233
>>>
``````

which simplifies to,

``````>>> def fibonacci_term(n):
if n < 1: return 0
a, b = 1, 1
for _ in [''] * (n - 2):
a, b = b, a + b
return b

>>> fibonacci_term(13)
233
>>>
``````
1 Like

Whether to start with 0 or 1 is a cultural artifact. In 1963, The Fibonacci Quarterly offered A Primer on the Fibonacci Sequence in its first issue. Here’s a quote from the article:

The first few Fibonacci numbers are:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, …

Nowadays, zero-based indexing is deeply ingrained in the computing mindset, and it seems that almost everything begins with 0.

1 Like