有本《数据结构与算法图解》（A Common-Sense Guide to Data Structures and Algorithms）可以参考一下：
: 
:
:
:
:
:
:
:
:
:
Loading...
有本《数据结构与算法图解》（A Common-Sense Guide to Data Structures and Algorithms）可以参考一下：
:
:
:
:
:
:
:
:
:
:
PSA and PDA
Binary search
Bitwise operations
BFS and DFS
Dijkstra's, Prim's, SPFA
Disjoint union
Greedy
Dynamic programming
Linear algebra and matrix exponentiation
Computational geometry
Polygons
Convex hull
Line sweep
Segment trees with lazy propagation
Binary indexed trees
Binary search trees (mostly splay)
Tarjan's SCC
Heavy-light decomposition
Maximum flow and bipartite matching
Hashing
我意思说hanoi tower的recursion不是重点，induction是重点，而你依然在和我讨论recursion的问题，我给一下我大一时候做hanoi tower的时候的证明（凭记忆再写一下）：
假设H(n) n其中n是蝶的过程，则显然 H(1)= 1， 只要移动1步即可。
那么显然 H(k+1)= 2*H(k)+1 , 因为显然(k+1)th的碟子必然要再上面k个碟子移走后，才能把(k+1)th移到第三柱，然后还有通过k个碟子的转移过程才能完成，即，2次k个碟子转移+(k+1)th底碟的转移 ，这个是Hainoi Recursion的定义式，好了，我的意思是recursion定义式不是重点，重点在于induction部分。
Hanoi的问题关键是要证明 2^n-1这个移蝶步骤，证明如下：
当n=1时，显然只要一步就可以完成，所以H(1)=1, 符合2^1-1=1的这个式子
假设当n=k时 H(k)=2^k-1成立
证明n=k+1时 H(k+1)是否还是成立？
H(k+1) 根据recursion定义则可以知道 H(k+1)=2*H(k)+1
=2*(2^k-1)+1 (根据induction 的kth假设）
=2^(k+1)-1
则显然2^n-1这个式子是成立的，并且是Hanoi tower的非递归解。
大部分recursion的问题，在数学上必须抛弃recursion定义，采用“线性”式子表达才是其本质。
比如BST(binary search tree)的复杂度问题，复杂度定义都是recursion,但结论都是 类似于 n Log n的非recursiond的"线性"解，这是我的上贴的意思。
:
:
:
:
:
:
:
有本《数据结构与算法图解》（A Common-Sense Guide to Data Structures and Algorithms）可以参考一下：
:
:
:
:
:
:
:
:
:
: