рекурсия — отслеживание рекурсивной факториальной функции в C ++?

Возникли проблемы с небольшим упражнением,
Предположим, у меня есть:

#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;
}

Как бы вы проследили это?
Например:

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.

Теперь, если вы следуете моей логике, мой вопрос в моем последнем утверждении

returns 4 times factorialFinder(4-1)

он возвращает 4 или 20, потому что сначала умножает 5 * 4.

Извините, у меня проблемы с пониманием и почему это работает.
Пожалуйста, попробуйте объяснить, используя мою логику таким образом.

0

Решение

Один из способов создать след — это инструмент код, добавив операторы вывода трассировки. Это может быть хорошей идеей, чтобы создать некоторую поддержку для этого. Например.,

#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;
}

Результат:

-> факториал 5
-> , факториал 4
-> , , факториал 3
-> , , , факториал 2
-> , , , , факториал 1
<-. , , , Факториал 1 возвращает 1
<-. , , Факториал 2 возвращает 2
<-. , Факториал 3 возвращает 6
<-. Факториал 4 возвращает 24
<- факториал 5 возвращает 120
120

Тем не менее, просто используя отладчик выполнять код шаг за шагом может быть так же полезно с гораздо меньшим количеством работы.

2

Другие решения

Для глубокого понимания того, как работает любой код, вы можете напечатать шаги, где выполняется приложение

Например:

#include <iostream>
using namespace std;

int factorialFinder(int x) {
cout << "f: " << x << endl;
if (x==1) {
cout << "return 1" << endl;
return 1;
}else{
const int res = x*factorialFinder(x-1);
cout << "return " << res << endl;
return res;
}
}

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

И вывод:

f: 5
f: 4
f: 3
f: 2
f: 1
return 1
return 2
return 6
return 24
return 120
120
2

По вопросам рекламы [email protected]