Question

Give a recursive algorithm for computing whenever n is a positive integer and x is an integer, using just addition.

Short answer

The recursive algorithm is,

$$\begin{gathered} \mathrm{procedure}\mathrm{product}(\mathrm{n}:\mathrm{positive}\mathrm{integer},\mathrm{x}:\mathrm{integer}) \\ \mathrm{if}\mathrm{n}=1\mathrm{then}\mathrm{return}\mathrm{x} \\ \mathrm{else}\mathrm{return}\mathrm{product}(\mathrm{n}-1,\mathrm{x})+\mathrm{x} \end{gathered}$$

Step-by-step solution

Procedure product

The recursive algorithm is based on the idea that nx = (n-1)x + x . The base case is 1. x = x.

Give a recursive algorithm for computing nx

The recursive algorithm for computing is given by,

$$\begin{gathered} \mathrm{procedure}\mathrm{product}(\mathrm{n}:\mathrm{positive}\mathrm{integer},\mathrm{x}:\mathrm{integer}) \\ \mathrm{if}\mathrm{n}=1\mathrm{then}\mathrm{return}\mathrm{x} \\ \mathrm{else}\mathrm{return}\mathrm{product}(\mathrm{n}-1,\mathrm{x})+\mathrm{x} \end{gathered}$$

Therefore, the recursive algorithm is shown above.