Ненужные рекурсионные вызовы ⇐ C++

[Anonymous]

Рассмотрим эту рекурсивную функцию: < /p>

Код: Выделить всё

bool foo(u_int d){
if (d > 1) return foo(d - 1) or foo(d - 2);
return true;
}
< /code>
Эта функция возвращает true для всех значений d. Если бы он был оценен наивно, это сделало бы o (f_n) рекурсивные вызовы, где F_n - NTH Fibonacci номер. < /P>
Однако »или« выражения оцениваются эффективно. Если один термин правда, другой не оценивается, поскольку он не изменит значение выражения. Поэтому foo (d-2) 

никогда не вызывается, поэтому сложность функции равен o (d).
Я проверил это, вызывая Foo (100) , что закончилось очень быстро. F_100t3.5e20, поэтому не было так много рекурсивных вызовов. Он ведет себя очень аналогично, поскольку «выражения также оптимизированы. < /p>

Код: Выделить всё

bool foo(u_int d){
if (d > 1) return foo(d - 1) and foo(d - 2);
return false;
}
< /code>
Теперь рассмотрим эту функцию: < /p>
int bar(){
return 0 * bar();
}

Это вызывает бесконечную рекурсию, хотя 0 * Что -то всегда 0.
Я также попробовал следующую функцию:

Код: Выделить всё

int bar(u_int d){
if (d > 1) return 0 * bar(d - 1) * bar(d - 2);
return 1;
}
< /code>
Здесь также сделаны рекурсивные вызовы. Я запустил бар (40) 

, и была заметная задержка. Я сравнил время выполнения панели функций с Baz
bool baz(u_int d){
if (d > 2) return baz(d - 1) and baz(d - 2);
return true;
}
< /code>
И они очень похожи. Они оба делают O (f_n) рекурсивные вызовы. 0 * Что -то всегда 0, поэтому нет необходимости оценивать рекурсивные вызовы.

Подробнее здесь: https://stackoverflow.com/questions/794 ... sion-calls