Fibonacci series using recursion in python

Question

num = int(input())

def fibonacci(n):
#complete the recursive function
if n<=1:
print(1)
else:
print (fibonacci (n-3))

fibonacci(num)

This code doesn't work, can anyone tell me the problem? And please prive solution also that why will it work or not

Answer 1

"""
is recursion required by task or not?

assuming it is, you should:
+ store the fibonacci terms serie when computing terms (and handle length limit of list used)
+ compute each term that is not yet stored (and store them up to list limit) and retrieve those wich are stored
+ get nth term by computing first (n-2)th term, then adding (n-1)th term to spare some recursivity

however, task may not expect you using memoization ^^
"""

fib_terms = [1,1]

def fibonacci(n):
x = len(fib_terms)
if n < x: return fib_terms[n]
if n == x:
t = fib_terms[n-2] + fib_terms[n-1]
fib_terms.append(t)
return t
return fibonacci(n-2) + fibonacci(n-1)

"""
but now, with that function and its buffer, recursion will never occur if you need to output all terms of serie up to n, as previous terms are always known ;P

in any recursive implementation cases, function return only the nth term (until you add smart print inside, and reset buffer before external calls) so you may loop to print the serie
"""

Answer 2

Thank you soo much

Answer 3

Fibonacci of n = fibonacci(n-1) + fibonacci (n-2)

Answer 4

well, i forgot to implement the list limit: it's quite optional as may only ends to error(s) for high values of n (above the list index limit or memory limit), wich would not occur for a recursive expected solution ;)

anyway, to make it quite more safe, you just have to add a fib_limit variable initialized with the maximum n limit, and change the line:

if n == x:

by:

if n == x and x < fib_limit:

then recursion only occur for n >= fib_limit in case of looping to print all serie up to n ;)

Answer 5

Easiest way is here:-
_______________________

num = int(input())
x, y=0,1

def fibonacci(n):
global x ,y
if n<=0:
return 0
else:
print(x)
x,y=y,x+y
fibonacci(n-1)

fibonacci(num)

Answer 6

It gives a type error that + should not work for None type of something error

Answer 7

You should retunr values instead of printing them

Answer 8

num = int(input())

def fibonacci(n):
#complete the recursive function
if n<=1:
return (1)
else:
return(fibonacci(n-1)+fibonacci(n-2))

print(fibonacci(num))

It outputs 8 not the series

Answer 9

I used for loop after recusions

Answer 10

what is the exact task description?

How is supposed formatted the output?

using recursion to find a specific term of fibonacci serie is not really efficient, but using recursion to output whole serie up to a specific term is the worst way to use and from quite to the much ineficient (if you use or not memoization)...

the berter way would be to use last terms memoization to whole serie memoization (if you plan to display many times some fibonnacci terms) to spare time in all cases and memory in former case ^^

Answer 11

Then please share the code with memorization, i dont know how to write it that way

Answer 12

Kairav Bhatia Here's a one-liner that returns the nth fibonacci number:

def fib(n, a=0, b=1): return fib(n-1, a+b, a) if n > 1 else a

Here's a better approach (using iteration):

def fib(n, a=0, b=1):
for i in range(n-1): a, b = a+b, a
return a

# Hope this helps