У меня есть вопрос о том, как преобразовать «рекурсию» в «хвостовую рекурсию». это не домашнее задание, просто всплыл вопрос, когда я попытался откорректировать теорему рекурсии из книги алгоритмов. Я знаком с 2 типичными примерами использования рекурсии (факториала и последовательности Фибоначчи), а также знаю, как реализовать их рекурсивным способом и хвостовой рекурсией. Мой код, как показано ниже (я использую Perl просто, чтобы сделать его простым, но может быть легко преобразован в C / Java / C ++)

#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 

рекурсивная функция дважды вызывает себя с другим параметром перед возвратом; Я попробовал несколько способов преобразовать это в хвостовую рекурсивную форму, но все оказалось не так.

Кто-нибудь может взглянуть на код и показать мне правильный способ сделать его рекурсивным? особенно я полагаю, что существует процедура для преобразования этой рекурсии дерева (несколько раз вызывайте рекурсивную функцию перед возвратом), может кто-нибудь пролить свет на это? Поэтому я могу использовать одну и ту же логику для решения разных вопросов позже заранее спасибо.