Solution: 2019 Winter Midterm - 14

Author: Michiel Smid

Question

Consider the recursive algorithm $\HelloWorld$, which takes as input an integer $n \geq 0$:

$\mathbf{Algorithm}\ \HelloWorld(n)\mathrm{:}$
$\mathbf{if}\ n = 0\ \mathrm{or}\ n = 1$
$\mathbf{then}\ \mathrm{print}\ \mathit{Hello}\ \mathit{World}$
$\mathbf{else}\ \mathbf{if}\ n \text{ is a multiple of } 3$
$\qquad \mathbf{then}\ \HelloWorld\left( n \middle/ 3 \right);$
$\qquad \qquad \ \ \mathrm{print}\ \mathit{Hello}\ \mathit{World};$
$\qquad \qquad \ \ \HelloWorld\left( 2n \middle/ 3 \right)$
$\qquad \mathbf{else}\ \HelloWorld(n + 1)$
$\qquad \mathbf{endif};$
$\mathbf{endif}$

Which of the following is correct?

(a)

None of the above.

(b)

For any integer $n \geq 0$, algorithm $\HelloWorld(n)$ terminates.

(c)

There exists an integer $n \geq 0$, for which algorithm $\HelloWorld(n)$ does not terminate.

(d)

All of the above.

Solution

If $ (a) $ is true, then it would not be recursive

$ (b) $ is pretty much what a recurisve function is