关于递归

[craiiz]

迫于最近不小心看到了《算法图解》，遂开始学习排序；当试到快排时，有个问题让人很疑惑: 最初版本： 这里当递归出口条件为 数组长度等于 1 时，会报错； 修改后的版本： 将出口条件修改为数组长度<2 时，就能正常运行

问题： len(array)<2 和 len(array) == 1 这两句话不是等价的么？？？？？

[chairuosen]

也可能是 0 啊

[shintendo]

等于 1 和小于 2 怎么会是等价的？？

[craiiz]

@chairuosen 关键是无论哪种写法，它都到不了 0 啊。给的数据长度都是大于 2 的，每次递归拆分列表的时候，如果长度要到 0，一定要先变 1 。

也可能是我没想明白。

[gwy15]

怎么就到不了 0 了，
qs([1,0]) -> pivot=1, greater = [], smaller = [0]
qs([]) -> boom

[craiiz]

@shintendo 我是这么想的：列表长度不可能小于 0 吧？ 可能是 0，但要变为 0，肯定会先变成 1 。既然两种情况(被排序的列表不停地被拆分)都必然会经过 len(array) == 1 的情况，那么在这限定条件下，这两种写法就是等价的。

[rabbbit]

例如 1 2 3 4 5 6

此时 base_line 为 1
greaters 为 [2, 3, 4, 5, 6]
smallers 为 []
所以报错了

[craiiz]

@gwy15 boom 。明白了，感谢。

[craiiz]

@rabbbit 明白了，感谢。

[craiiz]

此题终结

[chairuosen]

另外：遇到自己想不明白的问题，每一行结果都打日志看呀，又不是黑盒

[yuruizhe]

@craiiz 当 pivot 是最小值，smallers 是一个空数组，继续对 smallers 调用 sort()，就会无限递归下去；反之，当 pivot 是最大值，greaters 是一个空数组，继续对 greater 调用 sort()，也会无限递归下去，用例：[1,6,5,4,3,2,]

[craiiz]

@chairuosen 了解，我用 IDE 好了，现在想着学习就只用终端加记事本了。

[craiiz]

@yuruizhe 明白了，谢谢大神

[crella]

我看其他人写的 py 脚本，一般不都是把 import 语句放在文件开头的吗？