0

Coded in Python 3:

def fibonacci(n):
    if(n <= 1):
        return n
    else:
        return(fibonacci(n-1) + fibonacci(n-2))
n = int(input("Enter number of terms:"))
print("Fibonacci sequence:")
for i in range(n):
    print(fibonacci(i))

Enter number of terms:100 Fibonacci sequence: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887

After this it stucks and not executing the next series What is the reason?

enter image description here

Mark Rotteveel
  • 100,966
  • 191
  • 140
  • 197
Pari Mugilan
  • 21
  • 1

2 Answers2

2

I can go higher with my computer, even if the reason is mainly because it's a really bad algorithm.

For that kind of problem, you should use dynamic programming, in short, you store the result of every sequence, so in order to get the next one, you query your already gotten result instead of doing all the sequence over again.

You can read a bt more here : https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

It will take more space as you keep all result in memory, but you will gain way more time.

You are using a recursive function in a loop, where the main goal of the recursive function is to get n-1, this is .. a lot of wasted time. Too much in fact. You should either use iterative, or recursive, but not both at the same time.

f = [0,1]
def fibonacci(n):
    if(n>1):
        fibonacci(n-1)
    if(n<=0):
        return
    f.append(f[n]+f[n-1])
n = int(input("Enter number of terms:"))-2
print("Fibonacci sequence:")
fibonacci(n)
for e in f:
    print(e)

To be honest, i won't take too much time writting an optimized fibonacci recursive function while there's probably a lot around. I edited your code as much as I can, trying to keep the spirit.

So, we launch the recursive function only "once"

fibonacci(n)

We set n as input()-2 because we already have two number in our sequence.

f=[0, 1]

This is the list where we will keep our sequence

def fibonacci(n):
    if(n>1):
        fibonacci(n-1)
    if(n<=0):
        return
    f.append(f[n]+f[n-1])

What we will do in the recursive function is : Telling that we need the previous result if till we get down to 1. We already have f[1] so we don't have to calculated it. We have a return if we provide somthing like 0 or lower, preventing it to break if some user put negative value. Then we add the result to the end of f[]

After we ran the recursive function, this will give you a list with an ordered fibonnaci sequence to n

real    0m0,034s
user    0m0,018s
sys     0m0,014s

This is the time i get with n=1000 on my device

Vollfeiw
  • 244
  • 2
  • 9
  • 2
    While this code shows the use of dynamic programming, it's harder to understand than it needs to be because you're using a global variable. Also, it's not likely to work correctly if you call it twice since you don't clear `f`. I'd suggest returning the cache or passing it in instead. – joanis Apr 05 '21 at 11:50
  • 1
    There's a lot that could be done, as i said, i want to keep the spirit. One user input, one run, and done. But yeah, could be passing the cache instead, i tried to keep it simple, and i didn't know if passing the cache or keeping it as global would be easier to understand. And even without clearing the cache, we could use the length of the cache instead of i(n>1) to launch it again. – Vollfeiw Apr 05 '21 at 12:15
  • I like your additional explanations, it's very clear now. – joanis Apr 05 '21 at 18:28
1

As listed above in the comments, the algorithm is very inefficient, but there may be a way to speed it up and that's to use caching

To do so first import the functools module, this is an inbuilt module so there is no reason to install it with pip

to use it is simple

from functools import cache

@cache
def myFunc():
    #  your code here

final code

from functools import cache

@cache
def fibonacci(n):
    if(n <= 1):
        return n
    else:
        return(fibonacci(n-1) + fibonacci(n-2))
n = int(input("Enter number of terms:"))
print("Fibonacci sequence:")
for i in range(n):
print(fibonacci(i))

FYI, cache uses the LRU caching technique, you can learn more about it here. Also check out the docs for the same here

AkIonSight
  • 365
  • 3
  • 13