Edit Question - KnowledgeHub

Title Body

I have a question about how to convert 'recursion' to 'tail recursion'. This is not a homework, just a question that popped up when I tried to polish the recursion theorem from a book on algorithms. I am familiar with the 2 typical examples of using recursion (factorial and Fibonacci sequence), and also know how to implement them in a recursive way and tail-recursive way. My code is as below (I use Perl just to make it simple, but can be easily converted to 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 .. 10) { print "recP($k) = ", recP($k), "\n"; } When running the code, the output as below: 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 The recursive function invokes itself twice with different parameters before return. I've tried several ways to convert this to a tail recursive function but all turned out to be wrong. Can anybody take a look at the code and show me the correct way to make it tail-recursive? Especially I believe there is a routine for the conversion for this tree recursion (invoke recursive function multiple times before return), can anyone shed some light on this? So I can use the same logic to handle different questions later.

Tags (comma-separated) Cancel