Help me trace this weird recursive algorithm

[acerious]

BEGIN SEQ (n)
    IF (n <= 3) THEN
        RETURN n * 2
    ELSE
        RETURN SEQ (n - 3) + SEQ (n - 1) 
    ENDIF
END

For instance, for n = 8, I ran it in a compiler and the final return value is 38.

I tried tracing it in the program printing the value of n out but it was very confusing.

My compiler trace output:
/////////////////
Pre 8, Pre 5, Satisfied at 2

Pre 4, Satisfied at 1

Satisfied at 3

Pre 7, Pre 4, Satisfied at 1

Satisfied at 3

Pre 6, Satisfied at 3

Pre 5, Satisfied at 2

Pre 4, Satisfied at 1

Satisfied at 3

Final answer: 38
/////////////////
Satisfied values are the return n values before they were multiplied by 2.
Pre values are the ELSE recursive n values before they get returned.

This is very confusing for me and Ive been at it for hours, please don't be vague and try to let me figure it out myself, simple direct explanations would be really awesome at this point. Thanks.

[Schol-R-LEA]

Uhm, first off, what language is this in? It certainly isn't standard C++, not unless you've been doing funny things with the pre-processor. Even that wouldn't explain the lack of semi-colons. Is this supposd to be in an actual language, or is it pseudo-code used to explain the algorithm?

[acerious]

Pseudocode for the recursive algorithm yes. If you want the C++ code here it is.

#include <iostream>
using namespace std;

int recurse (int);

int main()
{

    int ans;
    int n = 8;
    ans = recurse(n);

    cout << "Final answer: " << ans << endl;

    return 0;
}

int recurse (int n)
{

    if (n <= 3)
    {
        cout << "Satisfied at " << n << "\n";
        cout << "Actual satisfy at " << n*2 << "\n";
        cout << endl;
        return n * 2;


    }

    else
    {
            cout << "Pre " << n << ",  ";
        return recurse (n-3) + recurse (n-1);

    }       cout << endl;
}

[Nutster]

So what is your actual question regarding this code? What do need help understanding?

[acerious]

I need help understanding how the trace works. I understand the basics with one recursive call but with 2, it gets really confusing.

[Nutster]

Some of what you have to realise is that either recursion could occur first. For other experts who think that one particular recursive call will always occur first, the compiler design and the optimizer could easily switch that around. Whichever recursive call occurs first will complete to the end before the other call executes.

So to trace this, build a tree, with a branch for each recursive call. In each branch, including the initial stem, write the value of n, which starts at 8. Unfortunately, I have difficulty representing a full tree in a text environment.

| 8
| (8-3=)5 - (other branch) (8-1=)7
Because your trace stated

Pre 8, Pre 5, Satisfied at 2

the first branch was taken first.
| (5-3=)2 - (5-1=)4
X 6

Pre 4, Satisfied at 1

So now we are working on the second branch of the previous node.
(5-1=)4
| (4-3=)1 - (4-1=)3
And this took the first branch. Generally whichever recursive function happens first, will keep on happening first.
X 2
Now it will work on the 3. And the process condinues like that to the end.

[vijayan121]

In general,
1. try to represent an elusive concept as a class - objects are more flexible than code.
2. C++ is one of the few programming languages with a strong sense of initialization and deinitialization - exploit it.

For example:

#include <iostream>

int recurse( int n )
{
    static int rdepth = 0 ;
    enum { TABSZ = 4 } ;

    struct trace_helper
    {
        explicit trace_helper( int n, const char* descr = "" )
            : arg(n), description(descr), tab( ++rdepth * TABSZ, ' ' )
        {
            std::cout << tab << "enter trace(" << arg << ") : "
                      << description << " \n" ;
        }

        ~trace_helper()
        {
            std::cout << tab << "exit trace(" << arg << ") : "
                      << description << " \n" ;
            --rdepth ;
        }

        const int arg ;
        const char* const description ;
        const std::string tab ;
    };

    trace_helper tracer( n, n <= 3 ? "n<=3 => return n*2 " :
                                     "n>3 => return recurse(n-3) + recurse(n-1)" ) ;

    return n <= 3 ? n * 2 : recurse(n-3) + recurse(n-1) ;
}