CODEWITHSUNDEEP
algorithmrecursionpseudocodetail-recursion
Dreana
Dreana

Reputation: 587

Rewrite linear recursive function as tail-recursive function

I was wondering, how do I proceed when rewriting a "regular" recursive function as a tail recursive one? Is there some kind of strategy?

For example: I have this simple function which I would like to turn into a tail recursive one:

int rec(int n) {
    if (n % 2 || n > 10) {
    return n;
    }
    return  rec(n+1) + rec(n+2);
}

Any help is appreciated.

Upvotes: 1

Views: 872

Answers (2)

Sylwester
Sylwester

Reputation: 48775

You need to start off with the base cases and look at the patterns for the default cases closest to the base case. In your case all base cases count up until n is 11 so the closest default case to the base case is 9. The next one is 7 and it includes the 9 so we have this pattern:

n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ... 
r 0 | 2 | 4 | 6 | 8 |  10 11 12 13
    |   |   |   |  10+11
    |   |   |   8+10+11
    |   |   6+8+10+11
    |   4+6+8+10+11     
    2+4+6+8+10+11

Based on this is obvious all odd numbers below 11 becomes the sum of the successor and all the even numbers up to 10 plus 11.

I suggest something like this for an iterative tail recursive version:

int rec_helper(int n, int acc) {
    if (n == 12) {
        return 11+acc;
    }
    return rec_helper(n+2, acc+n);
}

int rec(int n) {
    if (n % 2 || n > 10) {
        return n;
    }
    return rec_helper(n+1, 0); 
}

In this case though this is overkill. Notice that the series except 11 is a Arithmetic progression and the sum is well defined. The result does not need recursion at all:

int rec(int n) {
    if (n % 2 || n > 10) {
        return n;
    }
    return (121-n*n)/4;
}

Upvotes: 1

ruakh
ruakh

Reputation: 183544

The answer depends on your definitions of a "tail recursive" function and of "rewriting" a function, but I'm going to assume a mostly-informal understanding along these lines:

  • no iteration that wasn't in the original version.
  • no explicit stacks/arrays/etc. that weren't in the original version.
  • no recursive calls except tail-recursive ones (meaning, calls that are the entire expression in a return statement).
  • helper functions are OK, but mutual recursion is not.
  • non-equivalencies resulting from real-world considerations like integer overflow, stack overflow, roundoff error, etc., are not of concern.

That out of the way . . . you should know that it's not always possible to rewrite a function in a tail-recursive way. Your own example has the function make two recursive calls in the non-base case, and we obviously can't change both of them to be the entire expression in a return statement, so the only reason that your example can be rewritten as tail-recursive is that we can eliminate one of those calls.

So, let's start with your function:

int rec(int n) {
    if (n % 2 || n > 10) {
        return n;                 // line 3
    }
    return  rec(n+1) + rec(n+2);  // line 5
}

Now, if n is odd, then we return n at line 3; so if we've reached line 5, then we know that n must be even. This means that if we've reached line 5, then n+1 is odd and rec(n+1) will be n+1. So we can eliminate one recursive call:

int rec(int n) {
    if (n % 2 || n > 10) {
        return n;
    }
    return (n+1) + rec(n+2);
}

Next, it helps to expand out a real example to see what it looks like:

rec(6) = 7 + rec(8)
       = 7 + (9 + rec(10))
       = 7 + (9 + (11 + rec(12)))
       = 7 + (9 + (11 + (12)))

An important insight is that, since addition is associative, we can group terms in the opposite way:

rec(6) = ((7 + 9) + 11) + 12

This is useful because it means that we can compute a partial sum of results as we proceed, and pass that as a separate argument:

int rec(int n, int sum_so_far) {
    if (n % 2 || n > 10) {
        return sum_so_far + n;
    }
    return rec(n+2, sum_so_far + (n+1));
}

. . . and now we have a tail-recursive function, but it requires clients to pass in an extra argument! To fix that, we just rename it to rec_helper and wrap it in a function for clients to call:

int rec_helper(int n, int sum_so_far) {
    if (n % 2 || n > 10) {
        return sum_so_far + n;
    }
    return rec_helper(n+2, sum_so_far + (n+1));
}

int rec(int n) {
    return rec_helper(n, 0);
}

As you can see, there isn't a general strategy; rather, we needed to analyze the function, and exploit facts about the integers, to eliminate one recursive call, and then we needed to do the same thing again to convert the other recursive call into a tail-recursive call.

However, one aspect of what we did is a very common pattern, namely, moving the recursing into a helper function that takes an additional argument, where that argument holds the partial results that have been computed so far. I would say that I use this pattern at least 90% of the time when constructing a tail-recursive function.

Upvotes: 8

Related Questions