algorithm - 从选择排序中消除尾递归

Question

代码:(我尝试翻译成 Java。它用的是我不知道的另一种语言):

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);
  }
}

作业题要求消除这段代码中的尾递归。这是否意味着用迭代循环替换最后的递归调用？或者添加额外的递归调用？

我认为问题可能源于我不知道常规递归和尾递归算法之间的区别。如果我错了请纠正我，但我的理解是尾递归用于通过减少递归调用的次数来提高效率，除非调用是代码中的最后一条指令。关键是较少的递归调用意味着较少的递归堆栈存储在内存中。

编辑:修复了代码中交换调用的错误。

Answer 1

基本上，尾递归是函数调用自身时所拥有的，但之后不需要做任何事情，除了可能返回递归调用的结果。这是递归的一个特例……不在于它如何工作，而在于它很容易变成一个循环。对于不优化尾递归的编译器/解释器，这可能意味着正确工作和溢出调用堆栈之间的区别。

例如:

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

这是尾递归的，因为在 countdown 调用自身后不需要发生任何其他事情。

对比一下

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

这不是尾递归。不同的是函数在调用自身后需要重新获得控制权，所以它可以将结果乘以n。

(额外加分:您可以使用称为“连续传递样式”的技术将其转换为尾递归函数。基本上，在这种情况下，您会将结果与其他参数一起传递。)

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

但我离题了。

无论如何，删除尾递归的编译器基本上只是调整当前的调用框架，使变量成为调用时的变量，然后跳回到函数的开头。出于一些充分的理由，您的老师可能不会非常喜欢那样。但让我们从这里开始吧。

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;
    }
}

当我们重新排列内容时，空的条件 block 相当可怕。这也可以改写为

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;
    }
}

现在，您可能已经被告知 goto 是魔鬼。 :)(这被夸大了，但不应该在有更好选择的地方使用它。)所以重构以摆脱它。

我们如何摆脱它？我们找到了一个控制结构来完成 goto 试图做的事情。在这种情况下，while 循环非常适合。 condition 中缺少范围差异，此代码:

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

做完全一样的事情:

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

许多编译器甚至会为两者生成完全相同的代码。

所以让我们用 while 循环清理代码。

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;
    }
}