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.

Answer 1

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 $

Answer 2

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