Editor

Python Program to Print the Fibonacci Series Using Recursion

Beginner · Recursion

The Fibonacci series starts with 0 and 1, and each next term is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13 and so on. That rule is recursive, because term n is defined using terms n - 1 and n - 2, so it turns straight into a function that calls itself. This program prints the first 10 terms with a recursive function.

Program

fibonacci_using_recursion.py
def fibonacci(n):
# Base cases: term 0 is 0 and term 1 is 1
if n == 0:
return 0
if n == 1:
return 1
# Recursive step: each term is the sum of the two terms before it
return fibonacci(n - 1) + fibonacci(n - 2)
terms = 10 # or: terms = int(input("How many terms? "))
if terms <= 0:
print("Please enter a positive number of terms")
else:
print("First", terms, "terms of the Fibonacci series:")
for i in range(terms):
print(fibonacci(i), end=" ")
print()
Output
First 10 terms of the Fibonacci series:
0 1 1 2 3 5 8 13 21 34

How it works

  1. A recursive function calls itself, and it needs a base case, where it can answer straight away, and a recursive step, which moves closer to the base case on every call.
  2. The base cases are n == 0 and n == 1, the two starting terms 0 and 1, and without them the function would call itself forever.
  3. The recursive step returns fibonacci(n - 1) + fibonacci(n - 2), which is exactly the rule of the series.
  4. fibonacci(4) asks for fibonacci(3) and fibonacci(2), which ask for smaller terms in turn, until every call reaches a base case and the answers add up to 3.
  5. This is easy to read but slow for big n, because the same terms are worked out again and again: fibonacci(20) alone makes 21,891 calls.

Other ways to write it

Remembering answers with lru_cache

Remembering answers with lru_cache
from functools import lru_cache
@lru_cache(maxsize=None) # remember every answer already worked out
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print("Term 10:", fibonacci(10))
print("Term 50:", fibonacci(50))
print("Term 100:", fibonacci(100))
Output
Term 10: 55
Term 50: 12586269025
Term 100: 354224848179261915075

lru_cache stores the result of every call, so each term is worked out only once, and the same recursive function becomes fast enough for the 100th term.

Building the whole series recursively

Building the whole series recursively
def fibonacci_series(n):
# Base cases: the first one or two terms
if n == 1:
return [0]
if n == 2:
return [0, 1]
series = fibonacci_series(n - 1) # the first n - 1 terms
series.append(series[-1] + series[-2]) # add one more term
return series
print("First 10 terms:", fibonacci_series(10))
Output
First 10 terms: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

This version returns the series as a list, and each call builds on the list for one term fewer, so it makes only n calls instead of thousands.

Try it yourself

Add a counter that goes up by 1 each time fibonacci() is called, and print how many calls fibonacci(15) makes.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises