Question

Give a recursive algorithm to find the number of partitions of a positive integer based on the recursive definition given in Exercise 47 in Section 5.3.

Short answer

The recursive algorithm is given.

Step-by-step solution

Given that

As per Question 47 in Section 5.3

A partition of a positive integer n is a way to write n as a sum of positive integers where the order of terms in the sum does not matter.

The recursive definition of $P_{m,n}$is as follows:

${\mathrm{P}}_{\mathrm{m},\mathrm{n}}=\left\{\begin{array}{l}1\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{m}=1\\ 1\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{n}=1\\ {\mathrm{P}}_{\mathrm{m},\mathrm{m}}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{m}<\mathrm{n}\\ 1+{\mathrm{P}}_{\mathrm{m},\mathrm{m}-1}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{m}=\mathrm{n}>1\\ {\mathrm{P}}_{\mathrm{m},\mathrm{n}-1}+{\mathrm{P}}_{\mathrm{m}-\mathrm{n},\mathrm{n}}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{m}>\mathrm{n}>1\end{array}\right.$

Write recursive algorithm

It can be obtained by computing P (m,n) , Where P is the procedure given below. It can be obtained by the recursive definition given.

The recursive algorithm is as:

procedure P(m,n:nonnegative integer)

if m = 1then return 1

else if n = 1 then return 1

else if m < nthen return

else if m = n then return

else return P(m.n - 1) + P (m - n, n)