Question: 2014 Fall Final - 23

Consider the following recursive algorithm $\ThreeHeadsOrThreeTails$, which takes as input a positive integer $k$:

$\mathbf{Algorithm}$ $\ThreeHeadsOrThreeTails(k)$:
$\quad \text{flip a fair coin three times};$
$\quad \mathbf{if}\ \text{the result is $HHH$ or $TTT$}$
$\quad \quad \mathbf{then}\ \mathrm{return}\ k$
$\quad \mathbf{else}$
$\quad \quad \ThreeHeadsOrThreeTails(k + 1)$
$\quad \mathbf{endif}$

You run algorithm $\ThreeHeadsOrThreeTails(1)$, i.e., with $k = 1$. Define the random variable $X$ to be the value of the output of this algorithm. What is the expected value of $X$?