[Arch] Java数据结构与算法 - 递归

博客首页 » Arch Java数据结构与算法 - 递归

发布于 20 Jul 2015 09:25
标签 blog
用数学归纳发,来解决问题的方式。也就是通过把复杂问题,转化成只考虑一次次简单问题叠加,直至初始状态。

三角数字

阶乘

变位子

递归二分查找

分治算法

汉诺塔问题(Hanoi)

伪代码

hanoi(from, temp, target) {
  if (from.size() > 1) {
    hanoi(from.subTree(), newStack(target.getName()), new Stack(temp.getName()));
    move(from, target);
  } else {
    move(from, target);
  }
}
 
from = new Stack("A");
for (i = 0; i < n; i ++)
  from.push(n - i);
hanoi(from, new Stack("B"), new Stack("C"));

归并排序 Merge Sort

归并两个有序数列,成为一个有序数列
对于无序数列,可以递归二分,直至只有一个元素

改进:可以通过传递一个Workspace,避免在递归中反复分配空间,提高空间效率。

运行效率 O(N*logN)
log2(N)是执行递归次数,N是执行复制比较的次数

递归转化为非递归

使用栈+switch+循环可以将递归转化为非递归
简单算法也可以只是用多个循环完成

乘方

2的幂次方
偶数次方
奇数次方

背包问题

组合问题

递归可以展开成树


本页面的文字允许在知识共享 署名-相同方式共享 3.0协议和GNU自由文档许可证下修改和再使用,仅有一个特殊要求,请用链接方式注明文章引用出处及作者。请协助维护作者合法权益。


系列文章

文章列表

  • Arch Java数据结构与算法 - 递归

这篇文章对你有帮助吗,投个票吧?

rating: 0+x

留下你的评论

Add a New Comment