2
$\begingroup$

I am new to recursion. I am doing some practice questions and I was wondering what the technique is for going from some recursive code to identifying the number of function calls it makes.

function win(n)
   if n ≤ 3 let memo(n) = 'yes'
   if memo(n-2) = 'no' or memo(n-3) = 'no' let memo(n) = 'yes'
   else let memo(n) = 'no'
   let win(n) = memo(n)

Roughly, what is the number of steps that this program uses to compute $\mathit{win}(n)$? Is $\mathrm{step}(n)$ linear in $n$, polynomial in $n$ or exponential in $n$? Is it feasible to use this code to calculate $\mathit{win}(1000)$ on a fast supercomputer? Justify your answer.

$\endgroup$
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – dkaeae May 27 at 8:18
  • $\begingroup$ I don't think the program is correct. This is not how you implement memoization. $\endgroup$ – Yuval Filmus May 27 at 8:29
3
$\begingroup$

First, let me correct the program:

1 function win(n)
2     if memo(n) exists:
3         return memo(n)
4     if n ≤ 3:
5         memo(n) = true
6     else:
7         memo(n) = not win(n-2) or not win(n-3)
8     return memo(n)

Compared to your code, there are two main differences:

  1. If the value of the function is already known, that it is immediately returned (lines 2–3).
  2. Otherwise, we compute the value of the function recursively by invoking win rather than memo (line 7).

The running time of win depends on which values have already been calculated. For example, if you already computed the value of win on $n-2$ and $n-3$, then computing it on $n$ takes time $O(1)$. We can also bound the running time of win on input $n$ by $O(n)$, since lines 4–8 run at most once for every value of the input.

We could also implement win without any memoization:

1 function win(n)
2     if n ≤ 3:
3          return true
4     else:
5          return not win(n-2) or not win(n-3)

The running time of this implementation satisfies the recurrence $$ T(n) = T(n-2) + T(n-3) + O(1), $$ with base case $T(n) = O(1)$ for $n \leq 3$. Using standard techniques, we determine that the running time is $\Theta(c^n)$, where $c \approx 1.3247$ is the unique real root of $c^3=c+1$.

Finally, let us take a look at some values of win: $$ \begin{array}{c|cccccccccccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\\hline \mathit{win}(n) & T & T & T & T & F & F & T & T & T & F & F & T & T & T & F & F \end{array} $$ Notice the period of 5. We can easily prove the following formula by induction: for $n \neq 1$, $\mathit{win}(n)$ holds iff $n \bmod 5 \in \{0,1\}$. This gives an $O(1)$ algorithm for computing win.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.