Question

Give a recursive algorithm for finding the sum of the first n odd positive integers.

Short answer

The recursive algorithm is,

$$\begin{gathered} \mathbf{procedure}\mathbf{}\mathrm{oddsum}(\mathrm{n}:\mathbf{positive}\mathbf{}\mathbf{integer}) \\ \mathrm{if}\mathrm{n}=1\mathrm{then} \\ \mathbf{return}1 \\ \mathbf{else} \\ \mathbf{return}\mathrm{odssum}(\mathrm{n}-1)+2\mathrm{n}-1 \end{gathered}$$

Step-by-step solution

Describe the given information

The objective is to write the recursive algorithm for the sum of the first n odd positive integers.

 Step 2: Give a recursive algorithm for computing the sum of the first n odd positive integers

The algorithm is as follows.

$$\begin{gathered} \mathbf{procedure}\mathbf{}\mathrm{oddsum}(\mathrm{n}:\mathbf{positive}\mathbf{}\mathbf{integer}) \\ \mathrm{if}\mathrm{n}=1\mathrm{then} \\ \mathbf{return}1 \\ \mathbf{else} \\ \mathbf{return}\mathrm{odssum}(\mathrm{n}-1)+2\mathrm{n}-1 \end{gathered}$$

The above recursive algorithm is based on the idea that if the sum of first n - 1 odd positive integers is found, then the sum of the first positive integers can be found by adding the value of the $n^{th}$odd positive integer to the sum of n - 1 odd positive integers. The odd positive integer would be . Also, the base case (when n = 1) gives the sum as 1.

Therefore, the recursive algorithm is shown above.