вывод каждой итерации рекурсивной функции
Здравствуйте, может кто-нибудь сказать мне, как вывести каждое число в этой последовательности Фибоначчи, сохраняя при этом рекурсивную функцию, чтобы вместо отображения конечного числа отображалась последовательность чисел.
Спасибо 🙂
<?php
function fib($x){
if($x <= 2){
return 1;
}
return fib($x-1) + fib($x-2);
}
echo fib(10);
?>
Решение
Причина, по которой эхо выводится только из одного числа вместо всех номеров в последовательности, заключается в том, что вы повторяете вызов функции вместо того, когда функция получает номер в последовательности.
<?php
function fib($x){
if($x <= 2){
return 1;
}
echo $x . " ";
return fib($x-1) + fib($x-2);
}
fib(10);
Вызовите функцию fib () и введите число перед повторным вызовом fib (). Кроме того, вы можете положить 'echo $x . " ";' перед «оператором if» в начале функции, если вы хотите отобразить числа, которые также <= 2
Другие решения
Чтобы избежать потери производительности, вы должны хранить результаты, которые вы уже вычислили. Тогда вам просто нужно повторить ту, которую вы вычислили, тогда все будет в порядке.
$knownResults = array();
function fib($x){
global $knownResults;
if($x <= 2){
return 1;
}
if(!array_key_exists($x-1, $knownResults)) {
$knownResults[$x-1] = fib($x-1);
echo "fib(".($x-1).") = ".$knownResults[$x-1]."\n";
}
if(!array_key_exists($x-2, $knownResults)) {
$knownResults[$x-2] = fib($x-2);
echo "fib(".($x-2).") = ".$knownResults[$x-2]."\n";
}
return $knownResults[$x-1] + $knownResults[$x-2];
}
echo "result: ".fib(40)."\n";
Вы не можете вывести последовательность в рекурсивной функции, потому что здесь нет «проходной» последовательности. Рекурсивная функция разветвляется каждый раз с меньшими числами, пока не достигнет наименьшего числа.
Функция в целом будет называться экспоненциальным временем. Для fib (5) функция вызывается 9 раз, а для fib (10) функция вызывается 109 раз!
Если вы помещаете эхо внутри функции и просматриваете вызовы функций в виде дерева, эхо-сигнал перемещается в порядке пост-заказа:
