Eliminate tail recursion from selection sort

Question

code: (my attempted translation to Java. its in a different language that i dont know):

selection_sort(int a, int b){
  if(a == b+1){
      //do nothing
  }else{
      i = minIndex(arr, a, b); //minIndex finds minimum value of 2 index's an array
      if(i != a)
          swap(arr, i, a);
      selection_sort(a+1, b);
  }
}

The homework question asks to eliminate the tail recursion in this code. Would that mean to replace the last recursive call with an iterative loop? Or to add extra recursive calls?

I think the problem may stem from me not knowing the difference between a regular recursive and a tail recursive algorithm. Please correct me if I am wrong, but my understanding was that tail recursion is used to increase efficiency by reducing the number of recursive calls except if the call will be the last instruction in the code. The point being that less recursive calls means less recursive stacks to store in memory.

EDIT: mistake in the swap call in the code fixed.

score 5 · Accepted Answer · edited Feb 24 '14 at 14:57

Basically, tail recursion is what you have when a function calls itself, but doesn't need to do anything after that, other than possibly return the result of the recursive call. It's a special case of recursion...not in how it works, but in the fact that it is easy to turn into a loop instead. For compilers/interpreters that don't optimize tail recursion, that can mean the difference between working correctly and overflowing the call stack.

For example:

void countdown(int t) {
    if (t <= 1) return;
    printf("%d\n", t);
    countdown(t - 1);
}

This is tail-recursive, since nothing else needs to happen after countdown calls itself.

Contrast with something like

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

This is not tail-recursive. The difference is that the function needs to regain control after it calls itself, so it can multiply the result by n.

(Bonus extra point though: you can turn this into a tail-recursive function using a technique called "continuation-passing style". Basically, in this case, you'd pass the result along with the other parameters.)

int factorial(int n, int product = 1) {
    if (n <= 1) return product;
    return factorial(n - 1, product * n);
}

But i digress.

Anyway, compilers that remove tail recursion basically just tweak the current call frame so that the variables are what they'd have been for a call, and then jump back to the beginning of the function. Your teacher probably isn't going to like that very much, for a few good reasons. But let's start there.

selection_sort(int a, int b){
  tail_call:
    if(a == b+1){
      //do nothing
    }else{
      i = minIndex(arr, a, b);
      if(i != a)
          swap(arr, i, a);

      // tweak the variables so the next iteration sees (a+1, b)
      a += 1;
      goto tail_call;
    }
}

While we're rearranging stuff, empty conditional blocks are rather hideous. This can also be rewritten as

selection_sort(int a, int b){
  tail_call:
    if(a != b+1){
      i = minIndex(arr, a, b);
      if(i != a)
          swap(arr, i, a);

      // tweak the variables so the next iteration sees (a+1, b)
      a += 1;

      goto tail_call;
    }
}

Now, you've probably been told that goto is the devil. :) (That's overstated, but it shouldn't be used where there's a better option.) So refactor to get rid of it.

How do we get rid of it? We find a control structure that does what the goto was trying to do. And in this case, a while loop fits the bill quite nicely. Absent scope differences in condition, this code:

loop:
    if (condition) {
        ...magic...
        goto loop;
    }

does exactly the same thing as this:

while (condition) {
    ...magic...
}

to the point where many compilers will even generate the exact same code for both.

So let's clean up the code with a while loop.

selection_sort(int a, int b){
    while (a != b+1) {
        int i = minIndex(arr, a, b);
        if(i != a)
            swap(arr, i, a);

        a += 1;
    }
}

Thank you so much for walking me through step by step. You did lose me, though, at the goto part. Ive actually never used goto and thought it was just a psuedocode thing. Is it actual code? — YazanLpizra, Feb 19 '14 at 03:46
@yazan: In many languages, it is. Java doesn't have `goto`, so you can consider it a pseudocode thing if you're stuck with it. But most other languages in the C'ish family (and many many other languages, for that matter) do. — cHao, Feb 19 '14 at 04:13

score 1 · Answer 2 · edited May 23 '17 at 10:31

You can see about tail recursive here What is tail recursion?, What is tail-recursion elimination? and you may try this code, I have not tested, just the idea

selection_sort(){
  int firstIndex = 0;
  int lastIndex = arr.length;
  while(firstIndex < lastIndex) {
      int i = minIndex(arr, firstIndex, lastIndex);
      if(i != a) {
          swap(entries, i, firstIndex); 
      }
      firstIndex ++;
  }
}

Cause you can see in tail recursion version, it just update a, so we may try while loop

Eliminate tail recursion from selection sort

2 Answers2