冒泡排序是种很简单的排序方式. 如果用循环方式, 通常就是两层循环.
由于两层循环都是与元素个数 N 线性相关, 所以可以简单估算出它的时间复杂度是 O(N2), 通常而言, 这是较糟糕的复杂度.
当然, 这也几乎是所有简单方式的宿命, 想简单就别想效率高!
前面篇章说到递归也是一种循环, 所以普通循环能解决的问题, 用递归也能解决. 我们来看看怎么写出它来.
用递归解决冒泡排序问题
摘要: 用递归的方式来实现的冒泡排序程序.
经典递归分析
摘要: 简要介绍了阶乘与菲波那契数列两个经典的递归例子, 并重点分析了递归与迭代的异同, 以及递归调用与栈之间的关系.
在前面一篇中, 已经看过许多直观的递归的例子, 在这篇里, 将分析两个经典的递归问题, 阶乘与菲波那契数列数列, 在此过程中, 还将对比递归与循环(迭代)间的异同, 探讨递归与内存中的栈的关系, 以及递归的效率等问题.
如无特别说明, 示例使用的是 Java, IDE 则为 Eclipse.
阶乘(factorial)
阶乘大家应该都很熟悉了. 下面是一些简单例子:
2!= 2×1=2
3!= 3×2×1=6
用一个简单的循环就可以把它写出来. 不过我们现在打算用递归来写.
有趣的递归(Recursion), 一些直观的示例
摘要: 递归的一些有趣例子.
从前有座山, 山上有座庙, 庙里有个老和尚在给小和尚讲故事: "从前有座山, 山上有座庙, 庙里有个老和尚在给小和尚讲故事: ..."
反复而纠结的定义
看完这个故事, 对递归你已经有了印象, 很好, 这样已足够. 如果你不幸是个喜欢精确定义的人, 那么答案可能无法让你满意:
你想知道递归是什么, 你得先知道什么是递归.
To understand recursion, you must understand recursion.
把你绕晕了没有? 你可能想这叫啥子定义哟. 如果你去谷歌英文页搜索"recursion", 谷歌就会给你来这么一下:
谷歌说: "你是说递归吗? (Did you mean: recursion)".
拼写绝对是正确的, 这不过是谷歌给你开的"递归式"的玩笑.
说完了谷歌, 再说说必应(Bing), Bing 是什么意思呢:
Bing = Bing is not google(Bing 不是谷歌)
你还是不满意, 那再看看 GNU, GNU 又是啥呢:
GNU = GNU’s Not Unix(GNU 不是 Unix)