title: Convert recursion to tail recursion
body: <p>I have a question about how to convert 'recursion' to 'tail recursion'.</p>
  <p>This is not a homework, just a question that popped up when I tried to polish the recursion theorem from a book on algorithms.</p>
  <p>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.</p>
  <p>My code is as below (I use Perl just to make it simple, but can be easily converted to C/Java/C++).</p>
  <pre class="lang-perl prettyprint-override"><code># 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 &quot;recP($k) = &quot;, recP($k), &quot;\n&quot;;
  }
  </code></pre>
  <p>When running the code, the output as below:</p>
  <pre><code>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
  </code></pre>
  <p>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.</p>
  <p>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.</p>