论坛 › 数据结构与算法 › 关于数据结构最后一讲快速排序的优化尾递归

linfeline 发表于 2018-3-27 18:21:50

关于数据结构最后一讲快速排序的优化尾递归

if ((high - low) > MAX_SIZE)
{
        while(low < high)
        {
                pointer = Partition(a, low, high);

                if(pointer - low < high - pointer)
                {
                        QuickSort(a, low, pointer - 1);
                        low = pointer + 1;
                }
                else
                {
                        QuickSort(a, pointer + 1, high);
                        high = pointer - 1;
                }
        }
}
请问这块代码为什么就实现了尾递归？这好像和我查到资料后的个人理解不大一样。。。
个人以为是类似
int fun()
{
        return fun();
}
这类才是尾递归，没有看懂这一步的优化，麻烦各位大神指点一下。

ABC23 发表于 2018-4-27 12:18:21

尾递归：
def foo(a, b):
    # method body...
    return foo(a, b)

普通递归：
def bar(a, b):
    # method body...
    return 1 + bar(a, b)

ABC23 发表于 2018-4-27 12:19:17

尾递归是写给编译器看的，有的编译器支持的不好——能写迭代的就用循环迭代好了

查看完整版本: 关于数据结构最后一讲快速排序的优化尾递归