递归的思想其实很简单, 就是可以将解原始问题分解成为解规模较小的同类问题。
简单地说, 如果一个算法间接或直接地调用自身, 则可以称这个算法是递归算法。
递归算法会由两部分组成: 递归调用 + 递归终止条件
先看个简单的例子:
阶乘大家都很熟悉:
n! = n × (n-1) * ... * 2 * 1 = n * (n-1)!
于是解决n的阶乘的问题就转变成了解决(n-1)的阶乘的问题了, 依次下去直到条件满足终止递归, 即 n = 0.
再看看比较经典的汉诺塔游戏:
X, Y, Z 三个塔, 初始时在X塔上有n个盘子从小到大依次从上而下叠加, 先需要借助Y塔移到Z塔上, 并且移动过程中不能有大盘在小盘上的情况出现。
好, 来分析一下这个问题:
如果n = 1, 也就是说只有一个盘子, 简单, 直接从X移到Z就可以了。
当n > 1时, 我们从第二个盘子开始分析, 而对于1号盘子我们已经成功的移到了目标塔Z上去了, 那剩下的就是将2号移到塔Z上去。 此时我们可以完全不考虑从3号到n号的盘子, 因为它们都比1好和2好大, 所以可以当作不存在。 这样的话, 问题就可以分解了:
初始问题:
1号盘子在目标塔Z上, 2号在X塔上, 需将2好从X塔移到Z塔上 -
hanio(2, fromX, toZ)
转换问题:
a) hanio(1, fromZ, toY)
b) move(2, fromX, toZ)
c) hanio(1, fromY, toZ)
这样一来规模为2的问题就转换成了两次规模为1的问题再加上一次移动。
同样, 当规模为n的时候, 也就是去解决两次规模为n-1的汉诺塔问题和一次移动。。。如此递归下去就okay啦。
再来看一个例子: 求出n个布尔(0 或 1)的所有组合
很容易知道结果是有 2*2*2*...*2 = 2^n 种组合。 而 2^n = 2*2^(n-1)
所以我们分析下:
1. 定义一个长度为n的数组arr
2. 当n=1的时候, arr[0] = 0, 或者 arr[0] = 1。 只有这两中可能, 然后这也是递归的终止条件, 所以此时遍历arr把每一个元素打印出来
3. 当n>1的时候, 实际上就是在n-1打印的基础上把第n位的值设置为0或者1就可以了
所以可以得出以下递归方法:
public class Recursive {
public static void main(String[] args) {
int num = 10;
int[] b = new int[num];
coding(b, num);
}
private static void coding(int[] b, int n) {
if (n == 1) { // 这个是递归终止条件
b[n - 1] = 0;
out(b);
b[n - 1] = 1;
out(b);
} else { // 递归调用
b[n - 1] = 0; // 唯一要做的就是把第n个元素赋值, 其余的交给递归来处理
coding(b, n - 1); // 递归
b[n - 1] = 1;
coding(b, n - 1);
}
}
private static void out(int[] b) {
for (int i = 0; i < b.length; i++)
System.out.print(b[i]);
System.out.println();
}
}
总结:
递归的关键就是怎样把复杂问题分解成为多个相同的小规模问题进行解决。
每个level只需要做同样/相似的一件事情(比如汉诺塔中的move, 布尔组合中的set value), 其余的递归调用, 最终结果在递归终止块来完成。。。。。。
分享到:
相关推荐
递归问题的一种直观执行模型 针对递归过程的直观理解问题,提出了一种形式语言.通过该形式语言,可在 对递归程序宏观仅有所了解的基础上构造出直观执行模型.实例证明,此直观执行模 型能有效地使复杂递归过程具体化
详细分析了几个经典的递归问题:整数划分 完全背包 01背包等,日后还会完善。
java 内的递归问题极其练习代码,比较全面的讲述了递归问题,希望不太熟悉此部分的可以通过此文档懂得理解递归。
递归问题的二叉树求解方法.pdf
递归问题的Java实现
基于c语言实现的汉诺塔递归问题
递归问题的Java实现.pdf
汉诺塔c语言递归 基于C语言实现的 汉诺塔递归问题
c语言递归问题(汉诺塔)
一组要解决的递归问题(包括解决方案)
中职C语言中递归问题的解决方法探索.pdf
当一个算法(如二分查找)中包含对自己的递归调用时,关于这个算法时间复杂性的分析最终都转化为一个递归方程的求解问题,而这样的算法不在少数。在算法中介绍了3种方法。
acm递归算法总结acm递归算法总结!!!!!!!!!!!!!!!!!!!!!!!
完美解决多级递归查询,支持多种数据库,可以参照类似写法。有的数据库还是不支持的,但有类似的写法如oracle
n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---...
acm竞赛题,涉及到递归和回溯算法,可以转成宽度优先搜索
代码有详细注释! 1.语言:使用java编程 2.数据结构:使用单链表头插法仿实现栈 3.非递归使用DFS搜索一条路径 4.递归求解所有路径
https://blog.csdn.net/weixin_42512675/article/details/102147534
数据结构实验 解决迷宫问题,用递归方法生成迷宫、打印迷宫、找到走出迷宫的路径并输出
将河内塔问题的经典递归算法改写为非递归算法,对所有递归问题化解为非递归问题有参考价值