Need help understanding this recursion via pseudocode

Question

Given the recursive algorithm in this pseudocode:

RTC(n)
Input:  A nonnegative integer, n
Output:  A numerator or denominator (depending on parity of n) in an approximation of
If n < 3
    Return (n + 1)
If n >= 3
    t: = RTC(n – 1)
    If n is odd
        s:= RTC(n – 2)
        Return (s + t)
    If n is even
        r:= RTC(n – 3)
        Return (r + t)
If n is even
    print ‘Your approximation is ‘ , RTC(n) , ‘/’ , RTC(n – 1) , ‘.’

What is the output for the algorithm if the input n is 6?

The answer is: Your approximation is 17/12.

I'm finding myself stuck on how the recursive value is passed back up once I hit the base case. Take the variable t, for example. with the function getting called as RTC(6), it makes sense to me that t gets assigned RTC(5) which then calls the function with argument 5, getting to t=RTC(4), etc. Once I get to my base case of RTC(2) and the return value is n+1 or 3, then how do i pass that back up the recursion? Do I add? do I multiply? why?

As a side note, is it me or is there a lot of recursion going on in this snippet? This problem is from a bank of questions that should generally be able to be evaluated fairly quickly, not requiring more than a few minutes per question, certainly not much more than 5 minutes.

It would be nice to have the rest of what is approximated on output. Seeing $17/12$ I would guess it is $\sqrt 2$ because that is one of the convergents. You are expected to just follow through the code starting with $n=6$ and see what happens. A couple minutes seems to me reasonable for this. — Ross Millikan, Jun 28 '20 at 02:30
Something got cut off. "Output: ... in an approximation of" - approximation of what? — , Jun 28 '20 at 02:36
How do you ever reach the final "If n is even"? Every possible path before that has a Return statement. — , Jun 28 '20 at 02:38
There is not a lot of recursion. If you enter with $n=6$ you need the results from $n=3$ and $n=5$. Then you need the result of $n=1$. That is not very many. -1 — Ross Millikan, Jun 28 '20 at 02:38
Bungo. The last condition and print statement is NOT part of the recursive routine. — peawormsworth, Jun 28 '20 at 03:11

score 2 · Accepted Answer · answered Jun 28 '20 at 02:39

2

There is indeed a lot of recursion going on if you trace the operation of the algorithm, but it's easy if you start from the small values of $n$ and go up.

$\def \op #1{\operatorname {#1}} \def \RTC {\op{RTC}} \RTC(1) = 2\\ \RTC(2) = 3\\ \RTC(3) = \RTC(2)+\RTC(1)=5\\ \RTC(4) = \RTC(3)+\RTC(1)=7\\ \RTC(5) = \RTC(4)+\RTC(3)=12\\ \RTC(6) = \RTC(5)+\RTC(3)=17 $

answered Jun 28 '20 at 02:39

saulspatz

53,131

This helps me understand what's going on here, but is there another approach where I start with RTC(6) and recurse back? What if I was working with a large number for n, say 576 (to pick a random number)? Would I follow the same process and start at the base case and evaluate as I move up? – Academic Reboot Jun 28 '20 at 03:01
Yes, you can recurse; just try writing it down, starting from $$RTC(6)=RTC(5)+RTC(3)=(RTC(4)+RTC(3))+(RTC(2)+RTC(1))=...$$ I wouldn't want to do this for $576$, though. – saulspatz Jun 28 '20 at 03:11
For a larger number I would note that for $n$ odd $RTC(n)=RTC(n-1)+RTC(n-2)$ while for $n$ even $RTC(n)=RTC(n-2)+2RTC(n-3)$, which is the recursion for convergents to $\sqrt 2$. If you are in a computer science class it would be unfair to ask you to notice this, which is presumably why the question was for a small $n$. You are expected to unpack it as shown here. – Ross Millikan Jun 28 '20 at 03:20

score 0 · Answer 2 · answered Jun 28 '20 at 02:33

0

You could write the code and print what is happening to the variables.

python3:

def rtc(n):
    if n < 3:
        return n+1
    if n >=3:
        t = rtc(n-1)
        if n % 2:
            s = rtc(n-2)
            return s+t
        else:
            r = rtc(n-3)
            return r+t
for n in range(12):
    if not n % 2:
        print('Your approximation is {}/{}'.format(rtc(n),rtc(n-1)))

.

Your approximation is 1/0
Your approximation is 3/2
Your approximation is 7/5
Your approximation is 17/12
Your approximation is 41/29
Your approximation is 99/70

answered Jun 28 '20 at 02:33

peawormsworth

279

1

I don't think this is useful to OP. I believe the intent was to follow through the code and see what happens. The problem is that $n=4$ won't show much and if n is odd there is no output. – Ross Millikan Jun 28 '20 at 02:36
The last part of the pseudo code can not be part of the routine. The print statement is not in the recursion.
The last line says that to find the fraction using: rtc(5) / rtc(6). The routine does return a number on odd inputs.
– peawormsworth Jun 28 '20 at 03:08
def rtc(n): return n+1 if n<3 else rtc(n-(2 if n%2 else 3))+rtc(n-1) – peawormsworth Jun 28 '20 at 03:12

Need help understanding this recursion via pseudocode

2 Answers2