У меня вопрос о том, как преобразовать "рекурсию" в "хвостовую рекурсию". это не домашнее задание, просто возникает вопрос, когда я пытался отполировать теорему рекурсии из книги алгоритмов. Я знаком с 2 типичными примерами использования рекурсии (факториал и последовательность Фибоначчи), а также знаю, как реализовать их рекурсивным образом и хвостовым рекурсивным способом. Мой код выглядит следующим образом (я использую Perl, чтобы сделать его простым, но его можно легко преобразовать в C/Java/С++)
#this is the recursive function
sub recP {
my ($n) = @_;
if ($n==0 or $n==1 or $n==2) {
return 1;
} else {
return (recP($n-3)*recP($n-1))+1;
}
}
for (my $k=1;$k<10;$k++) {
print "*"x10,"\n";
print "recP($k)=", recP($k), "\n";
}
При запуске кода вывод, как показано ниже:
recP(1)=1
recP(2)=1
recP(3)=2
recP(4)=3
recP(5)=4
recP(6)=9
recP(7)=28
recP(8)=113
recP(9)=1018
рекурсивная функция дважды вызывает себя с другим параметром перед возвратом; Я пробовал несколько способов конвертировать это в хвостовой рекурсивный путь, но все получается неправильно.
Может ли кто-нибудь взглянуть на код и показать мне правильный способ сделать его хвостовым рекурсивным? особенно я считаю, что существует обычная процедура для преобразования этой рекурсии дерева (вызывайте рекурсивную функцию несколько раз до возвращения), может ли кто-нибудь пролить свет на это? Поэтому я могу использовать ту же логику для обработки разных вопросов позже. спасибо заранее.