Tracing a recursive factorial function in C++?

Question

Having trouble with a little exercise, suppose I have:

#include <iostream>
using namespace std;

int factorialFinder(int x) {
    if (x==1) {
        return 1;
    }else{
        return x*factorialFinder(x-1);
    }
}

int main()
{
    cout << factorialFinder(5) << endl;
}

How would you trace this? For example:

Put in 5 into the factorialFinder function.
if (5 == 1) (False, so skip)
returns 5 times factorialFinder(5-1)
this means returns 5 times factorialFinder(4)
this means go back to function
if (4 == 1) (False, so skip)
returns 4 times factorialFinder(4-1)
...etc.

Now if you follow my logic, my question is in my last statement

returns 4 times factorialFinder(4-1)

Does it return 4 or does it return 20 because it multiplies the 5*4 first?

Answer 1

One way to generate a trace is to instrument the code, adding trace output statements. It can be a good idea to create some support for that. E.g.,

#include <iostream>
#include <string>
using namespace std;

auto operator*( int const n, string const& s )
    -> string
{
    string result;
    for( int i = 1; i <= n; ++i ) { result += s; }
    return result;
}

class Tracer
{
private:
    std::string callspec_;
    std::string result_;

    auto call_level()
        -> int&
    {
        static int the_level;
        return the_level;
    }

    static auto indent() -> string { return ".  "; }

public:
    template< class Value >
    auto result( Value v )
        -> Value
    {
        result_ = to_string( v );
        return v;
    }

    ~Tracer()
    {
        --call_level();
        clog << "<- " << call_level()*indent() << callspec_;
        if( not result_.empty() )
        {
            clog << " returns " << result_;
        }
        clog << endl;
    }

    Tracer( string funcname )
        : callspec_( move( funcname ) )
    {
        clog << "-> " << call_level()*indent() << callspec_ << endl;
        ++call_level();
    }
};

auto factorial( int const x )
    -> int
{
    Tracer trace( "factorial " + to_string( x ) );
    return trace.result( x == 1? 1 : x*factorial( x - 1 ) );
}

auto main() -> int
{
    cout << factorial( 5 ) << endl;
}

Result:

-> factorial 5
-> .  factorial 4
-> .  .  factorial 3
-> .  .  .  factorial 2
-> .  .  .  .  factorial 1
<- .  .  .  .  factorial 1 returns 1
<- .  .  .  factorial 2 returns 2
<- .  .  factorial 3 returns 6
<- .  factorial 4 returns 24
<- factorial 5 returns 120
120

However, just using a debugger to execute the code step by step can be just as enlightening with much less work.