Question

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

Short answer

The recursive algorithm is,

$$\begin{gathered} \mathbf{procedure}sum\hspace{0.17em}(n:\mathbf{positive}\mathbf{}\mathbf{integer}) \\ \mathbf{if}n=1\mathbf{then} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{return}\mathbf{}\mathbf{1} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{else} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{return}\mathbf{}\mathrm{sum}(\mathrm{n}-1)+\mathrm{n} \end{gathered}$$

Step-by-step solution

 Step 1: Describe the given information

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

Give a recursive algorithm for computing the sum of the first n positive integers

Call the algorithm "sum" and the input is a positive integer .

procedure sum (n: positive integer)

The smallest positive integer is 1 and thus sum of the first positive integer is the integer 1 itself.

if n = 1 then

return 1

The sum of the first n integers is the sum of the first n - 1 integers (when is greater than 1 ) increased by n .

retrun sum (n-1)+n

By combining all these steps, the algorithm is obtained as,

$$\begin{gathered} \mathbf{procedure}sum\hspace{0.17em}(n:\mathbf{positive}\mathbf{}\mathbf{integer}) \\ \mathbf{if}n=1\mathbf{then} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{return}\mathbf{}\mathbf{1} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{else} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{return}\mathbf{}\mathrm{sum}(\mathrm{n}-1)+\mathrm{n} \end{gathered}$$

Therefore, the recursive algorithm is shown above.