FAQ: Recursion vs. Iteration - Coding Throwdown - When Fibs Are Good

This community-built FAQ covers the “When Fibs Are Good” exercise from the lesson “Recursion vs. Iteration - Coding Throwdown”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Learn Recursion: Python

FAQs on the exercise When Fibs Are Good

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

It should be noted that the function outline it gives will actually retrieve the value at the index provided and not actually the Nth term in the sequence.

def fibonacci(n):

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

1 Like

I guess the fibonacci explanation given here should be updated. The first element is 0 and so on… the test cases given should be -

print(fibonacci(4) == 2)
print(fibonacci(8) == 13)
print(fibonacci(0) == 0)

Below is a solution is could come up with. It has explicit assignment for 0th, 1st and 2nd positions…

def fibonacci(n):
if n < 0:
ValueError(“Input 1 or greater only!”)
if n <= 1:
return 0
if n == 2:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)

1 Like

Fibonacci numbers are a sequence, and in order to form a sequence we need a general term that defines each number in the sequence. Since the sequence is based upon addition, it follows we will have two sequential operands, the first being zero. This gives us a starting list, [0, 1]. If d is the difference between terms, this is the only time there is unity in a Fibonacci sequence. After that the ratio of any two latter terms begins to approach the Golden Ratio.

The fact that there is one instance where d is Unity is my argument for beginning the sequence with zero. Start with 1 and the next term as 1 then where is there any suggested sequence?

Yes, there are sequences, 1, 1, 2, 3, 5, … but the suggestive component is missing. The zero. Zero plus one is one.

1 Like

I agree 100%, then as per your suggested sequence (which is what I also consider as fibonacci) 0, 1, 1, 2, 3, 5… the 4th element should be 2 not the 3rd (as given in the actual test case). Am I missing anything here?

2 Likes

We’re both in disagreement of the SCT, so I’d say, no, you’re not missing anything. Glean from this and move forward. Compromises are well and good part of the process.

1 Like

Off-course!! Thanks for your input… Really Appreciate it!! I am glad I found someone to clarify my doubts…

2 Likes

I found this “Coding Throwdown” challenge lots of fun, but I’m curious about the run-times of the solutions we found. Am I missing something, or did we not get quizzed on those?

For example, here’s my solution (spoiler alert) to the Fibonacci challenge. I believe the run-time is O(N). Is that correct? Also, can you recommend a general strategy for testing function run-time?

 def fibonacci(n):
    base = {0: 0, 1: 1}
    for i in range(2, n + 1):
        base[i] = base[i-2] + base[i-1]
    return base[n]
1 Like
>>> def fib(n):
	a, b = 0, 1
	while n > 0:
		a, b = b, b + a
		n -= 1
	return a

>>> fib(20)
6765
>>> 

Now compare. Both give the same result. Which uses less resources?

4 Likes

You are correct that the run time of each method (yours and mtf’s) is O(N). But that covers a lot of territory (i.e., 10 * O(N) is still O(N).). Also, besides run time, you need to consider memory. Your method involves creating a dictionary that contains every fib less than fib(n), whereas his keeps only two numbers in memory at a given time.

That said, why not actually measure the run times?. The module timeit is a great resource, very nicely explained here.

Using it to compare the two functions, we get:

        Comparison of time (in seconds) taken
        for each of two methods of computing fib(n),
        1000 runs at each n.
         n          dict time        tuple time
          ****************************
        50          0.0164           0.0076
       100          0.0360           0.0175
       200          0.0726           0.0360
       400          0.1604           0.0884
       800          0.4011           0.2358
      1600          1.0445           0.6996
      3200          3.2599           2.2922
      6400         11.0521           8.2141
>>> 

(Source code here.)
You can see that for N < 1000 or so, doubling N does seem to more or less double the time. Also, the time for the “tuple” approach is consistently about one-half of the “dict” approach. These ratios begin to fall apart for higher N (fib(6400) has 1338 digits), presumably due to “real life” hardware considerations.

3 Likes

Your function uses fewer resources for the reasons Patrick mentions. I’d like to be writing more memory- and time- efficient functions, so I appreciate your sharing.

2 Likes

Thanks for the explanation and demonstration.

Very helpful.

1 Like