`
huhu_long
  • 浏览: 71388 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

递归问题

阅读更多
递归的思想其实很简单, 就是可以将解原始问题分解成为解规模较小的同类问题。

简单地说, 如果一个算法间接或直接地调用自身, 则可以称这个算法是递归算法。

递归算法会由两部分组成: 递归调用 + 递归终止条件

先看个简单的例子:
阶乘大家都很熟悉:
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), 其余的递归调用, 最终结果在递归终止块来完成。。。。。。
分享到:
评论

相关推荐

    经典递归问题

    整数划分是递归问题的一个典型例子,它涉及到将一个正整数 i 分割成若干个正整数的和,要求这些整数的和等于 i,并且每个部分不超过某个给定的最大值 j。计算划分的个数可以通过两种情况来递归解决:一是包含 j 作为...

    递归问题的一种直观执行模型

    递归问题的一种直观执行模型 针对递归过程的直观理解问题,提出了一种形式语言.通过该形式语言,可在 对递归程序宏观仅有所了解的基础上构造出直观执行模型.实例证明,此直观执行模 型能有效地使复杂递归过程具体化

    java 递归问题文档

    这篇“java 递归问题文档”很可能是对递归的深入讲解和实例分析,旨在帮助初学者理解和掌握这一关键技能。 首先,我们需要理解递归的基本原理。递归函数通常包含两个主要部分:基本情况(base case)和递归情况...

    递归问题的二叉树求解方法.pdf

    ### 递归问题的二叉树求解方法详解 #### 引言 递归作为一种强大的编程技巧,在软件设计中占据着举足轻重的地位。它允许程序通过自我调用来解决与自身相同或相似的子问题,从而简化了复杂的程序设计过程,提高了...

    acm迷宫递归问题源码

    知识点:ACM迷宫递归问题与回溯算法 标题中的“ACM迷宫递归问题源码”指向了一个在ACM(国际大学生程序设计竞赛)背景下的算法问题,主要涉及递归和回溯算法。这类问题通常是在一个迷宫环境中寻找从起点到终点的...

    递归问题的Java实现.zip

    在"递归问题的Java实现.zip"文件中,我们很可能会找到关于如何在Java中使用递归解决实际问题的详细说明和示例代码。 1. **递归定义与原理**: - 递归定义:一个函数或方法通过调用自身来解决问题的过程。 - 基本...

    一组要解决的递归问题包括解决方案

    在"一组要解决的递归问题包括解决方案"中,我们可以深入探讨递归的概念、工作原理及其在JavaScript中的应用。 1. **递归基础**:递归的核心思想是分治法,即将复杂问题分解为多个相同或相似的子问题,直到子问题变...

    数据结构中递归问题教学方法初探.pdf

    在数据结构和算法教学中,递归问题的教学是相当重要的,因为它是许多基础课程中的核心概念。递归不仅在程序设计课程中遇到,在后续的数据结构、操作系统、计算机原理等课程中也有大量应用。因此,掌握递归对于学生...

    c语言递归问题(汉诺塔).doc

    c语言递归问题(汉诺塔)

    acm递归算法总结竞赛

    在ACM(国际大学生程序设计竞赛)中,递归算法是一种常见的解决问题的方法,它通过函数自身调用自身来实现问题的解决。递归的核心在于找到基本情况(base case),即可以直接求解的问题,以及每次递归调用时问题规模...

    Hanoi塔问题的一种非递归算法

    Hanoi塔问题作为计算机科学领域内经典的递归问题之一,因其简洁性和挑战性而广受关注。通常,Hanoi塔问题的解决方案多采用递归算法,尽管其逻辑清晰、易于理解,但在实际应用中却面临时间和空间效率的问题。尤其是在...

    递归问题的Java实现.pdf

    递归是一种常用的编程技术,它将大问题分解成多个同类型的小问题进行求解。递归的核心思想是通过函数自身调用自身来解决子问题。递归算法在编程实现时具备以下特点:首先,递归方法会通过if-else或switch语句区分...

    阿克曼函数 c程序 递归与非递归算法的综合

    通过比较这两个程序,你可以看到递归和非递归算法在实现上的差异,以及它们在处理复杂递归问题时的不同策略。 理解并分析这两个程序,可以帮助你深入学习C语言编程,特别是递归和栈的概念。同时,这也为理解递归...

    递归实现:汉诺塔问题

    汉诺塔(Hanoi Tower)问题是一个经典的递归问题,源自一个古老的故事。传说在印度的一个神殿里,有三根金刚石柱子,第一根柱子上自上而下按大小顺序叠着64个金盘。神殿的僧侣们要在世界末日之前完成这样一个任务:...

    河内塔问题的非递归解法

    这种技巧对于处理其他递归问题,如树的遍历、图的搜索等问题,也有一定的启发作用。 在提供的压缩包文件"**HanoiTower**"中,可能包含了实现非递归算法的代码示例,你可以进一步学习和研究这些代码,以便更好地掌握...

    链式栈实现递归和非递归迷宫路径求解

    非递归DFS避免了系统栈的深度限制,适用于解决大规模问题。 递归解决方案则直接利用函数调用栈,每次进入新的节点,都进行一次函数调用,当到达出口或无路可走时,返回上一层。递归方法简洁直观,但可能导致大量...

    递归算法到非递归算法的转换.ppt

    对于递归问题,如汉诺塔,非递归解决方案通常需要显式地管理状态,比如使用堆栈来保存中间步骤。非递归版本的汉诺塔问题解决方案会将递归调用替换为对栈的操作,按照规则将盘片移动至目标位置。 总的来说,将递归...

    数据库设计之递归树查询

    本文将深入探讨如何通过递归查询来解决这类问题,并着重讲解使用`WITH`语句来实现递归查询的方法,适用于多种数据库系统,如MySQL、PostgreSQL、SQL Server等。 一、理解递归查询 递归查询是一种在数据库中遍历层级...

    汉诺塔问题 C语言实现 递归调用

    汉诺塔问题是一种经典的递归问题,广泛应用于计算机科学领域,特别是算法设计与分析中。在C语言中实现汉诺塔问题,不仅能够加深对递归的理解,还能提高编程技能。 ### 汉诺塔问题简介 汉诺塔(Tower of Hanoi)...

    如何提升JavaScript的运行速度(递归篇)

    因此,解决 JavaScript 中的递归问题是非常重要的。 Memoization 技术是解决递归问题的一种方法,它可以缓存之前运算结果,以避免重复计算已经计算过的结果。Memoizer 函数可以用来将递归调用转换为缓存结果,减少...

Global site tag (gtag.js) - Google Analytics