Solution: 2017 Winter Midterm - 15
Author: Michiel SmidQuestion
$\newcommand{\Hello}{{\rm H {\scriptsize ELLO}}}
\newcommand{\elsesp}{\phantom{\mathbf{else}\ }}$
Consider the recursive algorithm $\Hello$, which takes as input an integer $n \geq 0$:
(see document for missing code)
If we run algorithm $\Hello(7)$, how many times is the word "hello" printed?
(a)
4
(b)
5
(c)
7
(d)
6
Solution
\enquote{hello} is printed when HELLO is called with an argument of 0 or 1. We can draw a recursive tree to see how many times the HELLO$(1)$ is called.
HELLO$ (1) $ is called 5 times. Thus, \enquote{hello} is printed 5 times.