JAVA program to find fibonacci series for first n terms using recursion
This JAVA program is to find fibonacci series for first n terms using recursion. Fibonacci series is a series in which each number is the sum of preceding two numbers.
For example, fibonacci series for first n(7) terms is 0,1,1,2,3,5,8.
Logic
We return 0 of value is 0 and one if value is 1.For the remaining elements, we make recursive calls by adding the values decreased by 1 and 2.
Dry Run of the Program
Take input as n=5
We enter function fibo()
int fibo(int val)
n=5
if(val==0) false
else if(val==1) false
else
return (fibo(val-1)+fibo(val-2)); i.e. return (fibo(5-1)+fibo(5-2)); i.e. return (fibo(4)+fibo(3))
A recursive call[fibo(4) and fibo(3)]
For fibo(4),
if(val==0) false
else if(val==1) false
else
return (fibo(val-1)+fibo(val-2)); i.e. return (fibo(4-1)+fibo(4-2)); i.e. return (fibo(3)+fibo(2))
A recursive call[fibo(3) and fibo(2)]
For fibo(3),
if(val==0) false
else if(val==1) false
else
return (fibo(val-1)+fibo(val-2)); i.e. return (fibo(3-1)+fibo(3-2)); i.e. return (fibo(2)+fibo(1))
A recursive call[fibo(4) and fibo(3)]
For fibo(2),
if(val==0) false
else if(val==1) false
else
return (fibo(val-1)+fibo(val-2)); i.e. return (fibo(2-1)+fibo(2-2)); i.e. return (fibo(1)+fibo(0))
A recursive call[fibo(4) and fibo(3)]
For fibo(1),
if(val==0) false
else if(val==1) true
return 1
For fibo(1),
if(val==0) true
return 0
So now we will have for(i=0;i<n;i++) we call fibo(i)
0 … fibo(0)
1 … fibo(1)
1+0 = 1 … fibo(2)
1+1 = 2 …fibo(3)
2+1 = 3 …fibo(4) ….final answer
Program
import java.util.*;
class mr13
{
public static void main(String args[])
{
int n,i;
Scanner sc = new Scanner(System.in);
System.out.println("Enter the nth term");
n=sc.nextInt();
System.out.println("Fibonacci series of first "+n+" terms is");
for(i=0;i<n;i++)
{
System.out.print(fibo(i)+" ");
}
}
static int fibo(int val)
{
if (val==0)
return 0;
else if (val==1)
return 1;
else
return (fibo(val-1)+fibo(val-2));
}
}
