Question
Recursion is an important programming paradigm. It allows specifying operations in a concise manner, and provides solutions which are developed fast. There are several related aspects: parameter passing (as for any function), returning from the call, efficiency of the resulted code. Choose only one questions to respond to:
1. Choose a simple problem which can be solved using a recursive function. Provide two solutions (one recursive and one non recursive), and comparatively analyze them (especially from the efficiency point of view). The solution doesn't have to be fully implemented in java. Brief pseudo code is good enough.
2. Identify advantages and disadvantages of using recursion, and briefly discuss them.
3. Compare and contrast recursive with iterative implementation of problems.
4. Are there problem types that need a recursive approach instead of an iterative approach? How could one identify them?
5. What is really difficult about recursion? Do we need a mindset change when approaching recursion?
6. What elements should be considered and included in any recursive method? Discuss these elements using an example of a recursive method.
Part II
Consider a method which calculates and returns the following series:
S(i) = 1 + 1/2² + 1/3² + 1/4² + 1/5² … + 1/i².
The argument (i) has to be provided by user. The output is the value of S(i) which should be displayed either in the output window of the IDE, or in a GUI (however, designing a GUI is not mandatory.
a) Design and implement seriesIter, the iterative version of the method.
b) Design and implement seriesRec, the recursive version of the method.
c) Write a driver program TestSeriesVal.java to test the two methods.
All the java files and an output sample (the result obtained in the output window of the IDE) wrapped in a zip archive.
Solution Preview
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
1. Choose a simple problem which can be solved using a recursive function. Provide two solutions (one recursive and one non recursive), and comparatively analyze them (especially from the efficiency point of view). The solution doesn't have to be fully implemented in java. Brief pseudo code is good enough.Fibonacci’s problem
Recursion solution
Function fibo in : n
If n <= 1 then
Return n
Else
Return fibo(n-1) + fibo(n-2)
End if
End Function
Non-recursion solution
Function fibo in : n
If n <= 1 then
Return n
End if
Declare First, Second, Temp as integer
First := 1
Second := 1
For i := 2 to n -1
Temp = Second
Second := First + Second
First := Temp
End loop
Return Second
End Function...