Fibonacci Series Using Recursion Program in Java and Python
ISC 2005 Fibonacci series using recursion solution with algorithm, explanation, Java program and simple Python program.
Question:
A class Recursion has been defined to find the Fibonacci series up to a limit. Some of the members of the class are given below:
Specify the class Recursion giving details of the constructor, int fib() and void generate_fibseries(). You may assume other functions are written for you and you need not write the main function.
Algorithm:
Step 1: Start.
Step 2: Define a class named Recursion.
Step 3: Declare integer variables a, b, c and limit.
Step 4: In the constructor, initialize a = 0, b = 1, c = 0 and limit = 0.
Step 5: Accept the number of terms to be generated and store it in limit.
Step 6: Define the recursive method fib(n).
Step 7: If n <= 1, return a, which represents the first Fibonacci term.
Step 8: If n == 2, return b, which represents the second Fibonacci term.
Step 9: Otherwise, return fib(n - 1) + fib(n - 2).
Step 10: In generate_fibseries(), run a loop from 1 to limit.
Step 11: For every value of the loop counter, call fib(i) and store the returned value in c.
Step 12: Display c as the next term of the Fibonacci series.
Step 13: Stop.
Explanation:
The Fibonacci series is formed by adding the two previous terms to get the next term. In this program, the first two terms are treated as fixed starting values: a = 0 and b = 1. Therefore the series begins as 0, 1, 1, 2, 3, 5 and so on. The variable limit does not mean the maximum value of the series. It means the number of terms to be printed.
The important part of the program is the recursive method fib(int n). A recursive method is a method that calls itself to solve a smaller version of the same problem. For Fibonacci terms, the nth term depends on the previous two terms. So the method returns fib(n - 1) + fib(n - 2) for all terms after the first two. This directly matches the definition of the Fibonacci series.
Every recursive method must have stopping conditions, otherwise it will keep calling itself forever. Here, the stopping conditions are n <= 1 and n == 2. For the first term, the method returns a, which is 0. For the second term, it returns b, which is 1. These base cases allow larger terms to be calculated step by step. For example, fib(5) becomes fib(4) + fib(3), and those calls continue until they reach the first or second term.
The method generate_fibseries() does not calculate the whole series at once. It uses a loop from 1 to limit and calls fib(i) for each term position. The returned term is stored in c and printed. This keeps the recursion inside fib() and the display work inside generate_fibseries(). The design is useful for ISC theory questions because it clearly separates initialization, recursive calculation and series generation.
Java Program:
/**
* The class Recursion prints the Fibonacci series up to n terms
* using the concept of recursion.
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
* @Question Year : ISC Theory 2005 Question 12
*/
import java.util.Scanner;
class Recursion
{
int a;
int b;
int c;
int limit;
Recursion()
{
a = 0;
b = 1;
c = 0;
limit = 0;
}
void input()
{
Scanner sc = new Scanner(System.in);
System.out.print("Enter the limit: ");
limit = sc.nextInt();
}
int fib(int n)
{
/*
* Base cases:
* first term is 0 and second term is 1.
*/
if(n <= 1)
return a;
else if(n == 2)
return b;
else
return fib(n - 1) + fib(n - 2);
}
void generate_fibseries()
{
System.out.println("The Fibonacci Series is:");
// Generate each term by calling the recursive method.
for(int i = 1; i <= limit; i++)
{
c = fib(i);
System.out.print(c + " ");
}
}
public static void main(String args[])
{
Recursion ob = new Recursion();
ob.input();
ob.generate_fibseries();
}
}Equivalent Python Program:
class Recursion:
def __init__(self):
self.a = 0
self.b = 1
self.c = 0
self.limit = 0
def input_value(self):
self.limit = int(input("Enter the limit: "))
def fib(self, n):
# Base cases for the first two Fibonacci terms.
if n <= 1:
return self.a
elif n == 2:
return self.b
else:
return self.fib(n - 1) + self.fib(n - 2)
def generate_fibseries(self):
print("The Fibonacci Series is:")
# Generate each term by calling the recursive method.
for i in range(1, self.limit + 1):
self.c = self.fib(i)
print(self.c, end=" ")
ob = Recursion()
ob.input_value()
ob.generate_fibseries()Output:
Leave a Reply
Your email address will not be published. Comments are reviewed before appearing publicly.