There are certain
problems that just make sense to solve using Java Recursion. Demonstrating
Fibonacci Series is one of them. Let’s take a look at something called
Fibonacci series. Here are the first few numbers of this series:

0, 1, 1, 2, 3, 5, 8, 13, 21…

Now stop reading
and try to figure out what’s going on or let’s walk thru the sequence together
and see how it works:

To obtain the sequence, we start with 0 and 1 after which
every number is the sum of the previous two numbers.

For example, the first two numbers will be 0 and 1

0, 1

For the next number, we add the previous two numbers 0 and 1
which gives one.

0, 1, 1

The next number would be 1 + 1 = 2

0, 1, 1, 2

Now, the next number would be 1 + 2 = 3

0, 1, 1, 2, 3

Continuing in this way gives the Fibonacci series. A specific
term in the series is represented as Fn where n is the position of that
number from the beginning. For example,

F0 = 0, F1 = 1, F2 = 1, F3=2, F4 = 3,
F5 = 5 and so on...

The Fibonacci series can be expressed as a recurrence
relation as shown below:

F0 = 0

F1 = 1

F

F

_{n}= F_{n-1}+ F_{n-2}; where n >= 2
What’s neat about
this sequence is that when you try to sit down and think up an algorithm to
solve this problem, you can’t help but think of recursion. Since the solution
to the next number relies on the past two iterations, recursion becomes very
handy. Now that’s not to say that the only way to solve this problem is with
Java Recursion, but it can make the coding much simpler (We also can use Java
Iterator to solve this sequence).

* Define stopping point.

* Walk towards the stopping point.

As long as we follow these two rules, we are ok, otherwise
we might get caught in an infinite loop. In this case we have to terminate our
code manually. Since we are looking for the

**Nth**number of our Fibonacci Sequence, do you guess what’s our “stopping point” would be? Nice guess! It’s the number we are wishing to solve. If the question is: “What is the 20^{th}number in the Fibonacci Sequence?”, then our precious “stopping point” is 20.
Well
then, we have our stopping point, now think about the second part of our recursion model.
How do we make our code to walk towards the stopping point? We know that the
Fibonacci sequence represents

F

_{n}= F_{n-1}+ F_{n-2}; where n >= 2. Here the_{n}represents the unique*index*of any particular number in the Fibonacci sequence. In this case, its 20.*1*.

**Private static int**index = 0;*2.*

*3.*

**public static void**main (String[] args){*4.*

**int**n1 = 0;*5.*

**int**n2 = 1;*6. System.out.println(“index: “ + index + “ = “ + n1);*

*7. fibonacci(n1, n2);*

*8. }*

*9.*

*10.*

**public static void**fibonacci(int n1, int n2){*11. System.out.println(“index: “ + index + “ = “ + n2);*

*12.*

**if**(index == 20){ //Stopping point.*13.*

**return**;*14. }*

*15. index++; //Make sure to increment our index to walk towards the end.*

*16.*

*17. fibonacci(n2, n1 + n2);*

*18. }*

Here we go! We have our working algorithm for the Fibonacci
Sequence. Now change your stopping point and explore different

*index*of the sequence.
I still remember all the troubles while I was doing this for my class project. Good post!

ReplyDeleteYeh. Recursion makes it little bit more interesting. Thanks for your comment!

ReplyDeleteWell explained!!!

ReplyDeleteThanks for your comment!

ReplyDeleteVery

ReplyDeletehelpful post! Good job!

Very helpful post! Great Job!

ReplyDeleteThanks for your Comment!

ReplyDeleteI remember struggling with

ReplyDeleteRecursion when I was first starting out. Very well explained. Keep up the good

work!

Thanks for your comment!

ReplyDelete