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.

Improve this question
$\endgroup$
2
  • $\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$ Commented May 27, 2019 at 8:18
  • $\begingroup$ I don't think the program is correct. This is not how you implement memoization. $\endgroup$ Commented May 27, 2019 at 8:29

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.