Given a non-negative number n find the nth Fibonacci Number.
The Fibonacci Sequence is the series of numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
The 0th number is 0. 1st number is 1. Thereafter every number is derived by adding two numbers before it.
Fib(0) = 0 Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)
As part of this exercise first, find the Fibonacci number without using recursion and then using recursion. Please note that the recursive implementation makes two recursive calls.
The above exercise is very trivial. So just to add some pep to the exercise let us provide a third implementation where the Fibonacci number is calculated using a single recursive call instead of two. If you implement this correctly then you would have taken a tiny step into the world of Memoization.
The idea is while computing Fib(n), Fib(n-1) and Fib(n-2) are computed. Fib(n-1) is computed after computing Fib(n-2) and Fib(n-3). Thus in this example, we can see that Fib(n-2) is computed twice. So while computing Fib(n-1), Fib(n-2) has to be computed and hence if we can store this computation and later reuse it then we could avoid the second recursive call. This storing of computed result for later reuse is called Memoization and is part of Dynamic Programming.
While solving the Fibonacci problem using Memoization, a naive solution such as this uses O(n) space. But each of the computed values is used only once and not more than once. Always it is the just previously computed value that is required and all the values prior to that are not required. Hence it is just enough to have storage space for the just one last previously computed value. Thus the storage space required is O(1) instead of O(n). Please take a look at my solution for the implementation details.
As usual, please pay attention to the documentation, inline comments, and checking of illegal arguments.
I strongly urge the readers to make a sincere attempt in implementing the solution. I am providing my implementation so that you can compare it with yours. Looking straightaway at my solution may not be as helpful as making a physical attempt to solve the problem even if your solution is incomplete or not perfect.
You could also carry your source code in a public repository hosted on GitHub and if you prefer you could share the link to your source code in the comment section so that other readers could take a look at it and provide their comments.
Please provide your support and express your encouragement by using the social buttons provided below and share this effort with others.
Here is the link to my solution.
The Fibonacci Sequence is the series of numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
The 0th number is 0. 1st number is 1. Thereafter every number is derived by adding two numbers before it.
Fib(0) = 0 Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)
As part of this exercise first, find the Fibonacci number without using recursion and then using recursion. Please note that the recursive implementation makes two recursive calls.
The above exercise is very trivial. So just to add some pep to the exercise let us provide a third implementation where the Fibonacci number is calculated using a single recursive call instead of two. If you implement this correctly then you would have taken a tiny step into the world of Memoization.
The idea is while computing Fib(n), Fib(n-1) and Fib(n-2) are computed. Fib(n-1) is computed after computing Fib(n-2) and Fib(n-3). Thus in this example, we can see that Fib(n-2) is computed twice. So while computing Fib(n-1), Fib(n-2) has to be computed and hence if we can store this computation and later reuse it then we could avoid the second recursive call. This storing of computed result for later reuse is called Memoization and is part of Dynamic Programming.
While solving the Fibonacci problem using Memoization, a naive solution such as this uses O(n) space. But each of the computed values is used only once and not more than once. Always it is the just previously computed value that is required and all the values prior to that are not required. Hence it is just enough to have storage space for the just one last previously computed value. Thus the storage space required is O(1) instead of O(n). Please take a look at my solution for the implementation details.
As usual, please pay attention to the documentation, inline comments, and checking of illegal arguments.
Fibonacci Implement the class Fibonacci with the following public methods. public int fib(int n); public int fibUsingDoubleRecursion(int n); public int fibUsingSingleRecursion(int n);
I strongly urge the readers to make a sincere attempt in implementing the solution. I am providing my implementation so that you can compare it with yours. Looking straightaway at my solution may not be as helpful as making a physical attempt to solve the problem even if your solution is incomplete or not perfect.
You could also carry your source code in a public repository hosted on GitHub and if you prefer you could share the link to your source code in the comment section so that other readers could take a look at it and provide their comments.
Please provide your support and express your encouragement by using the social buttons provided below and share this effort with others.
Here is the link to my solution.
Nice post!!thanks for sharing good post. java vogue have good collection for improve program skill visit Programming Questions And Answers
ReplyDelete