Recursive Definition for finding the sum of the first n odd positive integers: i

Question

Recursive Definition for finding the sum of the first n odd positive integers: if n = 1 then return 1 else return odd_sum (n -1) + 2n -1 Verify the recursive definition above, by answering the following Three-Question Approach questions. The Base-Case Question: Is there a non-recursive way out of the algorithm, and does the algorithm work correctly for this base case? The Smaller-Caller Question: Does each recursive call to the algorithm involve a smaller case of the original problem, leading inescapably to the base case? The General-Case Question: Assuming the recursive call(s) to the smaller case(s) works correctly, does the algorithm work correctly for the general case? Using JAVA programming, implement the recursive definition. Your code should meet the following requirements: Prompt the user for a valid input Check if the input value is valid or not. For an invalid input, reject the input and prompt the user again for a valid one. Your code should print changes of the input value while executing itself. The final output (the sum of the first n odd positive integers) should be printed along with intermediate output values (sums of the first n-1, n-2, n-3... odd integers).

Explanation / Answer

1.

a) All recursive algorithms must have the following:

Base Case (i.e., when to stop)

Work toward Base Case

Recursive Call (i.e., call ourselves)

The "work toward base case" is where we make the problem simpler. The recursive call, is where we use the same algorithm to solve a simpler version of the problem. The base case is the solution to the "simplest" possible problem (For example, the base case to adding a list of numbers would be if the list had only one number... thus the answer is the number).

b) Smaller-Caller Question: Does each recursive function call involve a smaller case of the original problem leading to the base case?

Yes, Each recursive function call involve a smaller case of the original problem leading to the base case.

For example, smaller case of the above recursive function is sum of first odd positive integers.

c) A recursive function has the following general form (it is simply a specification of the general function we have seen many times):

ReturnType Function( Pass appropriate arguments ) {

if a simple case, return the simple value   // base case / stopping condition

else call function with simpler version of problem
}

For a recursive function to stop calling itself we require some type of stopping condition. If it is not the base case, then we simplify our computation using the general formula.

2.

import java.io.*;

import java.util.*;

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.