当前位置：文档之家 › 第六章 递归算法

第六章 递归算法

  • 格式：ppt
  • 大小：523.00 KB
  • 文档页数：24

下载文档原格式

  / 24

合集下载

递归算法及经典例题详解

递归算法及经典例题详解

递归算法及经典例题详解
1.什么是递归
递归简单来说就是在运行过程中不断调用自己，直到碰到终止条件，返回结果的过程。

递归可以看作两个过程，分别是递和归。

递就是原问题把要计算的结果传给子问题；归则是子问题求出结果后，把结果层层返回原问题的过程。

下面设一个需要经过三次递归的问题，为大家详细看一下递归的过程：当然，现实中我们遇到递归问题是不会按照图中一样一步一步想下来，主要还是要掌握递归的思想，找到每个问题中的规律。

2.什么时候使用递归
递归算法无外乎就是以下三点：1.大问题可以拆分为若干小问题2.原问题与子问题除数据规模不同，求解思路完全相同3.存在递归终止条件
而在实际面对递归问题时，我们还需要考虑第四点：
当不满足终止条件时，要如何缩小函数值并让其进入
下一层循环中
3.递归的实际运用（阶层计算）
了解了大概的思路，现在就要开始实战了。

下面我们来看一道经典例题：
求N的阶层。

首先按照思路分析是否可以使用递归算法：
1.N！可以拆分为（N-1）！*N
2.（N-1）！与N！只有数字规模不同，求解思路相同
3.当N=1时，结果为1，递归终止
满足条件，可以递归：
publicstaticintFactorial(int num){if(num==1){return num;}return num*Factorial(num-1);}
而最后的return，便是第四步，缩小参数num的值，让递归进入下一层。

一般来说，第四步往往是最难的，需要弄清该如何缩
小范围，如何操作返回的数值，这一步只能通过不断
地练习提高了（当然如果你知道问题的数学规律也是
可以试出来的）。

算法与数据结构第6章 递归

算法与数据结构第6章 递归

递归设计的步骤如下： (1)对原问题f(s)进行分析,假设出合理的“较小问题”f(s')(与数 学归纳法中假设n=k-1时等式成立相似)； (2)假设f(s')是可解的,在此基础上确定f(s)的解,即给出f(s)与f(s') 之间的关系(与数学归纳法中求证n=k时等式成立的过程相似)；
(3)确定一个特定情况(如f(1)或f(0))的解,由此作为递归出口(与 数学归纳法中求证n=1时等式成立相似)。
这样f(sn)便计算出来了,因此,递归的执行过程由分解和 求值两部分构成。
求解fun(5)的过程如下：
fun(5) d1:fun(4) d2:fun(3) d3:fun(2) d4:fun(1) fun(5)=120 fun(4)=24 fun(3)=6 fun(2)=2
返回 1
思考题：
递归的本质是什么？
f(s1)=m1 (6.1)
这里的 s1与m1均为常量 ,有些递归问题可能有几个递归出口。 递归体的一般格式如下：
f(sn+1)=g(f(si),f(si+1),…,f(sn),cj,cj+1,…,cm)
(6.2)
其 中 ,n,i,j,m 均 为 正 整 数 。 这 里 的 sn+1 是 一 个 递 归 “ 大 问 题” ,si,si+1,…,sn 为递归“小问题” ,cj,cj+1,…,cm是若干个可以直接 (用非递归方法)解决的问题,g是一个非递归函数,可以直接求值。
else
return(head->data+Sum(head->next)); }
3. 问题的求解方法是递归的
有些问题的解法是递归的,典型的有Hanoi问题求解,该问题 描述是：设有 3个分别命名为 X,Y和 Z的塔座 ,在塔座X上有 n个 直径各不相同,从小到大依次编号为1,2,…,n的盘片 ,现要求将X 塔座上的n个盘片移到塔座 Z上并仍按同样顺序叠放 ,盘片移动 时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在 X,Y和 Z中任一塔座；任何时候都不能将一个较大的盘片放在 较小的盘片上。设计递归求解算法 ,并将其转换为非递归算法。 设Hanoi(n,x,y,z)表示将n个盘片从x通过y移动到z上,递归分 解的过程是：

简述递归算法的执行过程

简述递归算法的执行过程

简述递归算法的执行过程摘要：1.递归算法的定义和基本原理2.递归算法的执行过程3.递归算法的应用实例4.递归算法的时间复杂度和优化方法5.总结正文：递归算法是一种自调用算法，通过将问题分解为更小的子问题来解决问题。

它在计算机科学和数学领域中广泛应用，具有可读性和实用性。

下面详细介绍递归算法的执行过程、应用实例、时间复杂度和优化方法。

一、递归算法的定义和基本原理递归算法是一种算法，它通过将问题分解为更小的子问题来解决问题。

这些子问题与原始问题具有相似的特征，从而使得算法可以通过重复调用自身来解决这些子问题。

在递归算法中，有一个基本情况（base case）和递归情况（recursive case）。

基本情况是问题规模足够小，可以直接给出答案的情况；递归情况则是将问题分解为更小的子问题，并重复调用算法本身来解决这些子问题。

二、递归算法的执行过程1.初始化：定义问题的初始条件，通常是基本情况。

2.判断基本情况：如果问题规模足够小，直接给出答案。

3.划分问题：将问题分解为更小的子问题，并确保这些子问题与原始问题具有相似的特征。

4.递归调用：将子问题传递给算法本身，重复执行步骤1-3，直到基本情况出现。

5.合并结果：将递归调用返回的结果合并，得到最终答案。

三、递归算法的应用实例1.计算阶乘：递归算法可以用于计算一个正整数的阶乘。

例如，计算5的阶乘：```def factorial(n):if n == 0:return 1else:return n * factorial(n-1)```2.计算Fibonacci 数列：递归算法可以用于计算Fibonacci 数列。

例如，计算第n个Fibonacci 数：```def fibonacci(n):if n == 0:return 0elif n == 1:return 1else:return fibonacci(n-1) + fibonacci(n-2)```四、递归算法的时间复杂度和优化方法1.时间复杂度：递归算法的时间复杂度通常为O(2^n)，其中n为问题的规模。

递归算法

递归算法

一．递归算法概述程序调用自身的编程技巧称为递归（ recursion）。

一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。

用递归思想写出的程序往往十分简洁易懂。

二．递归算法的特点递归算法是一种直接或者间接地调用自身算法的过程。

在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。

递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。

(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。

所以一般不提倡用递归算法设计程序。

(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。

递归次数过多容易造成栈溢出等。

所以一般不提倡用递归算法设计程序。

三．递归算法要求递归算法所体现的“重复”一般有三个要求：一是每次调用在规模上都有所缩小(通常是减半)；二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。

四．例子（用从C＋＋描述）：行数程序#include <iostream>using namespace std;0 void p (int w){1 if(w>0){2 cout<<w<<" ";3 p(w-1);4 p(w-1);5 }6 }void main(){int a;cin>>a;p(a);}当输入a=4后的打印结果：当p（0）执行完了，就会执行p(1)中的语句5（所以在方格a中，填“5”）。

06递归算法PPT课件

06递归算法PPT课件

递归的定义
若一个对象部分地包含它自己, 或用它自己给自 己定义, 则称这个对象是递归的；若一个过程直接地 或间接地调用自己, 则称这个过程是递归的过程。
递归的定义
直接递归 fun_a() {… fun_a() … }
间接递归 fun_a() {… fun_b() …}
fun_b() {… fun_a() …}
c1, c2,……，cm是若干个可以直接（用非递归方法）解决的问题， g是一个非递归函数，反映了递归问题的结构。
递归模型
例如，阶乘函数 递归出口
1,
当n0时
n! n(n1)!, 当n1时
递归体
ห้องสมุดไป่ตู้
递归的执行过程
实际上，递归是把一个不能或不好直接求解的 “大问题”转化为一个或几个“小问题”来解决，再 把这些“小问题”进一步分解成更小的“小问题”来 解决，如此分解，直至每一个“小问题”都可以直接 解决（此时分解到递归出口）。
递归调用执行过程：
... ...
main() x=17
bn=bSearch(a,x,0,7)
...
bn=bSearch(a,x,0,7)
mid=3 bn=bSearch(a,x,4,7)
...
4
...
return(bn=bSearch(a,x,4,7))
mid=5
bn=bSearch(a,x,4,4)
6.1 递归的概念
若一个算法直接地或间接地调用自己本身，则称 这个算法是递归算法。
1.问题的定义是递归的
例如：阶乘函数的定义
1
当n=0时
n=
n*(n-1) 当n>0时
2. 问题的解法存在自调用 例如：折半查找算法

递归算法详解完整版

递归算法详解完整版

递归算法详解完整版递归算法是一种重要的算法思想，在问题解决中起到了很大的作用。

它通过将一个大问题划分为相同或类似的小问题，并将小问题的解合并起来从而得到大问题的解。

下面我们将详细介绍递归算法的定义、基本原理以及其应用。

首先，我们来定义递归算法。

递归算法是一种通过调用自身解决问题的算法。

它通常包括两个部分：基础案例和递归步骤。

基础案例是指问题可以被直接解决的边界情况，而递归步骤是指将大问题划分为较小问题并通过递归调用自身解决。

递归算法的基本原理是"自顶向下"的思维方式。

即从大问题出发，不断将问题划分为较小的子问题，并解决子问题，直到达到基础案例。

然后将子问题的解合并起来，得到原始问题的解。

递归算法的最大特点是简洁而优雅。

通过将复杂问题分解为简单问题的解决方式，可以大大减少代码的复杂程度，提高程序的效率和可读性。

但是递归算法也有一些缺点，包括递归深度的限制和复杂度的不确定性。

过深的递归调用可能导致栈溢出，而不合理的递归步骤可能导致复杂度过高。

递归算法有许多应用场景，我们来介绍其中一些典型的应用。

1.阶乘问题：计算一个数的阶乘。

递归算法可以通过将问题划分为更小的子问题来解决。

例如，n的阶乘可以定义为n乘以(n-1)的阶乘。

当n 等于1时，我们可以直接返回1作为基础案例。

代码如下：```int factorial(int n)if (n == 1)return 1;}return n * factorial(n - 1);```2.斐波那契数列问题：求斐波那契数列中第n个数的值。

斐波那契数列的定义是前两个数为1，然后从第三个数开始，每个数都是前两个数的和。

递归算法可以通过将问题划分为两个子问题来解决。

当n等于1或2时，直接返回1作为基础案例。

代码如下：```int fibonacci(int n)if (n == 1 ， n == 2)return 1;}return fibonacci(n - 1) + fibonacci(n - 2);```3.二叉树问题：对于给定的二叉树，递归算法可以通过递归调用左子树和右子树的解来解决。

递归算法 递推公式求解

递归算法递推公式求解递归算法是一种自我调用的算法，它通过不断将问题分解为更小的子问题来求解问题。

递归算法的核心是递推公式，也称为递归式，它描述了如何将问题分解为子问题，并如何从子问题的解中得到原问题的解。

递推公式通常具有以下形式：T(n) = aT(n/b) + f(n)其中，T(n) 表示问题规模为n 时的时间复杂度，a 表示每次递归调用的次数，b 表示每次递归调用后问题规模缩小的比例，f(n) 表示除了递归调用外的其他操作的时间复杂度。

为了求解递推公式，我们可以使用以下方法：1.迭代法：通过迭代递推公式的方式逐步计算出T(n) 的值。

这种方法比较直观，但对于较大的n 值，迭代次数可能非常多，计算量也会非常大。

2.替换法：通过猜测T(n) 的形式，并将其代入递推公式中进行验证。

如果猜测正确，则可以得到T(n) 的解。

这种方法需要对问题有一定的了解和猜测能力。

3.大师定理：大师定理是一种求解递推公式的通用方法。

它可以根据递推公式的形式，直接给出T(n) 的时间复杂度。

大师定理有多种形式，其中最常用的是以下三种：a. 如果f(n) = O(n^c)，其中c < log_b(a)，则T(n) = O(n^log_b(a))。

b. 如果f(n) = O(n^c)，其中c = log_b(a)，则T(n) = O(n^c * log_n)。

c. 如果f(n) = O(n^c)，其中c > log_b(a)，且对于所有足够大的n，有af(n/b) <= f(n)，则T(n) = O(f(n))。

需要注意的是，大师定理只是一种求解递推公式的工具，它并不能解决所有类型的递推公式。

在实际应用中，我们需要根据具体问题选择合适的求解方法。

常用特殊算法


6．2．1 递推算法的适用性
但并不是所有的递归算法都适合改写成递推算 法， 最起码的条件是求解过程允许从有明确结果的低 阶问题开始。阶乘问题就允许从 1！开始，推算到我 们希望的某一阶为止，因此，采用递推算法来求解阶 乘问题就比递归算法好得多。 但有很多递归算法的求 解起点是有限制的，不允许从低阶问题开始求解，也 就不能改写成递推算法。例如有名的“梵塔问题”就 是这样， 一阶梵塔的解法是明确的， 如果 N 阶梵塔的 解法已知，就可以推出 N＋1 阶梵塔的解法，看起来 很适合采用递推算法， 但该问题就是不允许从一阶梵 塔开始，必须从 N 阶梵塔开始。 “梵塔问题”已经成 为递归算法的经典实例， 没有其它算法比用递归算法 更直观有效。
6．3．1 回溯算法的特点
回溯算法有以下基本特点： 问题的求解必须是由有限的若干部分组成的，例如一条从迷宫入口到迷宫出口的路 径是由若干（中间没有分支的） “路段”组成的；一种服装的裁剪下料方案是由各 个衣片的摆放位置组成的； 一种配方是由各种原料的取舍用量组成的； 一局棋局是 由开局、中盘、残局、结局各阶段的下法组成的。如果我们把问题解的所有可能的 组成部分称为“元素”的话，那么元素的范围必须是有限的，例如配方问题中原料 的种类和用量是有一定范围的。 一个问题如果有多个解的话， 各个解的区别在于它 们的组成元素的取舍不同。问题的一个解的部分元素构成“部分解” ，不同解之间 可以有相同的“部分解” ，例如配方 A 包含有 6 种原料，配方 B 包含有 7 种原料， 两种配方中有 4 种原料是相同的，它们都可以是符合要求的配方。 回溯算法求解问题的过程是由“部分解”向“完整解”推进的过程（开始时部分解 是空的，一个元素也没有） 。推进的方法是在“部分解”的基础上增加一个新元素， 如果新增加这个元素之后仍然满足问题的规定条件（约束条件） ，我们就得到一个 新的“部分解” ，然后再试着增加一个新的元素。如果新增加这个元素之后破坏了 问题的规定条件，我们就将这个新元素取出来， “回溯”到没有增加这个新元素时 的状态，另外选取别的元素再试。将这种试探一直进行下去，当“部分解”完全满 足问题的条件时，这时的“部分解”就称为“完整解” ，可以将其输出。当搜索完 全部可能组合之后仍然没有得到“完整解” ，就证明该问题无解。 在回溯算法进行的过程中，各步的处理方法都是相同的，符合递归算法的特点，因 此，回溯算法中一般都配合递归算法来进行。在递归的过程中，可供选择的元素范 围越来越小， 约束条件也越来越苛刻， 从而保证递归过程可以在有限的时间之内结 束。在递归过程中，问题的“部分解”是作为全局数据处理，而当前可供选择的元 素范围和当前约束条件的动态值是作为局部数据处理（需要用户堆栈保护） 。

离散数学中递归算法的工作原理解析

离散数学中递归算法的工作原理解析离散数学是一门研究离散对象和离散结构的数学学科，其在计算机科学中有着广泛的应用。

递归算法是离散数学中的一个重要概念，本文将对递归算法的工作原理进行解析。

1. 递归算法的定义递归算法是一种通过反复调用自身来解决问题的算法。

它通常包含了一个递归出口（基本情况）和一个递归体（递归情况）。

当问题达到递归出口时，算法停止递归并返回结果。

否则，算法继续递归调用自身，将问题分解为规模更小的子问题，并在子问题上进行递归求解。

2. 递归算法的优点与注意事项递归算法具有以下优点：1) 逻辑清晰简洁：递归算法能够使用简洁的方式描述问题的解决过程。

2) 结构灵活：递归算法能够解决各种类型的问题，适用范围广泛。

然而，递归算法也需要注意以下事项：1) 递归深度：递归算法的性能与问题的规模成反比。

递归深度过大可能导致栈溢出或性能下降。

2) 重复计算：递归算法中可能存在重复计算，增加了计算量。

可以使用记忆化技术（如动态规划）来优化递归算法。

3. 递归算法的应用场景递归算法在计算机科学中有广泛的应用，包括但不限于以下领域：1) 数据结构：递归算法常用于处理树、图、链表等数据结构，如树的遍历、图的深度优先搜索等。

2) 排列组合：递归算法可以用于生成排列组合，如全排列、组合数等。

3) 分治算法：分治算法通常使用递归来将问题分解为更小的子问题，并分别求解。

4. 递归算法的实现步骤实现一个递归算法通常包括以下步骤：1) 定义递归出口：确定递归算法何时停止递归，返回结果。

2) 确定递归体：根据问题的特点，将问题分解为规模更小的子问题，并调用自身来解决子问题。

3) 设计递归调用：根据子问题的规模和性质，设计递归调用的方式。

4) 处理子问题的结果：将子问题的结果合并得到原问题的结果。

5. 递归算法的示例：阶乘计算下面通过计算阶乘的例子来具体说明递归算法的工作原理：```python# 递归算法计算阶乘def factorial(n):if n == 0:return 1else:return n * factorial(n-1)```上述代码中，factorial函数通过递归来计算阶乘。

递归算法课件

写成函数形式，则为：
当n 0时 1 f ( n) n * f (n 1) 当n 0时
这种函数定义的方法是用阶乘函数自己本身定义了 阶乘函数，称上式为阶乘函数的递推定义式。
数学归纳法表明，如果我们知道某个论点对最小的情 形成立，并且可以证明一个情形暗示着另一个情形，那么我 们就知道该论点对所有情形都成立。 数学有时是按递归方式定义的。 例1：假设S（n）是前n个整数的和，那么S（1）= 1，并且 我们可以将S（n）写成S（n）= S（n-1）+ n。 根据递归公式，我们可以得到对应的递归函数： int S(int n) { if (n == 1) return 1; else return S(n-1) + n; } 函数由递归公式得到，应该是好理解的，要想求出S （n），得先求出S(n-1)，递归终止的条件（递归出口）是(n == 1)。
↑
low 第二次: 下标 元素值 0 1 1 3 2 4
↑
mid 3 5 4 17 5 18 6 31
↑
high 7 33
↑
low 第三次: 下标 元素值 0 1 1 3 2 4 3 5 4 17
↑
mid 5 18 6 31
↑
high 7 33
↑
low high mid
• Public static void main(String args[]) •{ • int[] shus={1,3,4,5,17,18,31,33};
求Fib(5)的递归计算过程如图所示。
Fib(5) Fib(4) Fib(3) Fib(2) Fib(1) Fib(2) Fib(3) Fib(2) Fib(1) Fib(0)
Fib(1) Fib(0) Fib(1)
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

阶乘递归函数运行时栈的变化过程： 阶乘递归函数运行时栈的变化过程：
6.5 递归算法的效率分析
我们以斐波那契数列递归函数的执行效率为例来讨论 递归算法的执行效率问题。 递归算法的执行效率问题。 斐波那契数列Fib(n)的递推定义是： 斐波那契数列 的递推定义是： 的递推定义是
0 Fib ( n ) = 1 Fib ( n − 1) + Fib ( n − 2 )
+
C D E
C
D
C
E
D
E
6.72 回溯法及设计举例 回溯法的基本思想是：对一个包括有很多结点， 回溯法的基本思想是：对一个包括有很多结点，每个 的基本思想是 结点有若干个搜索分支的问题， 结点有若干个搜索分支的问题，把原问题分解为对若 干个子问题求解的算法。当搜索到某个结点、 干个子问题求解的算法。当搜索到某个结点、发现无 法再继续搜索下去时，就让搜索过程回溯（即退回） 法再继续搜索下去时，就让搜索过程回溯（即退回） 到该结点的前一结点，继续搜索这个结点的其他尚未 到该结点的前一结点， 搜索过的分支； 搜索过的分支；如果发现这个结点也无法再继续搜索 下去时，就让搜索过程回溯到这个结点的前一结点继 下去时， 续这样的搜索过程； 续这样的搜索过程；这样的搜索过程一直进行到搜索 到问题的解或搜索完了全部可搜索分支没有解存在为 止。
例：求解迷宫问题
迷宫问题的搜索过程： 迷宫问题的搜索过程：
路口 1 2 3 4(死 路 ) 3(死 路 ) 2 5(死 路 ) 2 6 动作 向前 向左 向右 回溯 回溯 向前 回溯 向右 向左 结果 进入2 进入3 进入4 进入3 进入2 进入5 进入2 进入6 进入7
当 n = 0时 当 n = 1时 当 n > 1时
6−4
按照上式，求第 项斐波那契数列的递归函数如下 项斐波那契数列的递归函数如下： 按照上式，求第n项斐波那契数列的递归函数如下：
public static long fib(int n){ if(n == 0 || n == 1) return n; else return fib(n - 1) + fib(n - 2); } //递归出口 递归出口 //递归调用 递归调用
6.1 递归的概念
若一个算法直接地或间接地调用自己本身， 若一个算法直接地或间接地调用自己本身，则称 这个算法是递归算法。 这个算法是递归算法。 递归算法 1.问题的定义是递归的 问题的定义是递归的 例如： 例如：阶乘函数的定义 1 n= n*(n-1) 当n>0时 时 当n=0时 时
2. 问题的解法存在自调用 例如： 例如：折半查找算法
测试主函数设计如下： 测试主函数设计如下：
public static void main(String[] args){ int[] a = {1, 3, 4, 5, 17, 18, 31, 33}; int x = 17; int bn; bn = bSearch(a, x, 0, 7); if(bn == -1) System.out.println("x不在数组 中"); 不在数组a中 不在数组 else System.out.println("x在数组 中，下标为 + bn); 在数组a中 下标为" 在数组 }
if(n > 0) display(n - 1);
//递归 递归
//n<=0为递归出口，递归出口为空语句 为递归出口， 为递归出口 }
例2：设计求解委员会问题 ：
A B C D E
C D C E A B A C A D A E
B
C
B
D
B
E
D
E
B C D E
A A A A
B C D E
B
B
C
B
D
B
E
6.2 递归算法的执行过程
例1：阶乘的递归算法 ：
public static long fact(int n) throws Exception{ int x; long y; if(n < 0){ throw new Exception("参数错！"); 参数错！ 参数错 } if(n == 0) return 1; else{ x = n - 1; y = fact(x); return n * y; } }
第6章 递归算法 章
6.1 递归的概念 6.2 递归算法的执行过 6.3 递法的效率分析 6.6 递归算法到非递归算法的转换 6.7 设计举例
本章主要知识点： 本章主要知识点： ● 递归的概念 ● 递归算法的设计方法 ● 递归算法的执行过程 ● 递归算法的效率
fib(5)的递归调用树 的递归调用树
Fib(5)
Fib(4)
Fib(3)
Fib(3)
Fib(2)
Fib(2)
Fib(1)
Fib(2)
Fib(1)
Fib(1)
Fib(0)
Fib(1)
Fib(0)
Fib(1)
Fib(0)
6.6 递归算法到非递归算法的转换
一般来说，如下两种情况的递归算法可转化为非递归算法： 一般来说，如下两种情况的递归算法可转化为非递归算法： （1）存在不借助堆栈的循环结构的非递归算法，如阶乘计算 ）存在不借助堆栈的循环结构的非递归算法， 问题、斐波那契数列的计算问题、 问题、斐波那契数列的计算问题、折半查找问题等 （2）存在借助堆栈的循环结构的非递归算法。所有递归算法 ）存在借助堆栈的循环结构的非递归算法。 都可以借助堆栈转换成循环结构的非递归算法。 都可以借助堆栈转换成循环结构的非递归算法
6.7 设计举例
6.7.1 一般递归函数设计举例 例1： 设计一个输出如下形式数值的递归函数。 ： 设计一个输出如下形式数值的递归函数。 n n n ... n ...... 3 3 3 2 2 1
递归函数设计如下 ： public static void display(int n){ for(int i = 1; i <= n; i ++){ System.out.print(" } System.out.println(); " + n);
递归调用执行过程： 递归调用执行过程：
例2：折半查找递归算法 折半查找递归算法
public static int bSearch(int[] a, int x, int low, int high){ int mid; if(low > high) return -1; mid = (low + high) / 2; if(x == a[mid]) return mid; else if(x < a[mid]) return bSearch(a, x, low, mid - 1); else return bSearch(a, x, mid + 1, high); } //在下半区查找 在下半区查找 //在上半区查找 在上半区查找 //查找成功 查找成功 //查找不成功 查找不成功
设计一个计算3！得主函数如下 用来说明递归算法的 设计一个计算 ！得主函数如下,用来说明递归算法的 执行过程： 执行过程：
public static void main(String[] args){ long fn; try{ fn = fact(3); System.out.println("fn = " + fn); } catch(Exception e){ System.out.println(e.getMessage()); } }
例 ：汉诺塔问题的递归求解过程
A B C A B C
1 2 3 4 (a) 4 (b) 1 2 3
A
B
C
A
B
C
1 1 2 3 (c) 4 (d) 2 3 4
6.4 递归过程和运行时栈
递归函数的执行过程具有三个特点： 递归函数的执行过程具有三个特点： （1）函数名相同； ）函数名相同； （2）不断地自调用； ）不断地自调用； （3）最后被调用的函数要最先被返回。 ）最后被调用的函数要最先被返回。 系统用于保存递归函数调用信息的堆栈称作运行时栈。 系统用于保存递归函数调用信息的堆栈称作运行时栈。 运行时栈 每一层递归调用所需保存的信息构成运行时栈的一个工作 每一层递归调用所需保存的信息构成运行时栈的一个工作 记录 栈顶的工作记录保存的是当前调用函数的信息， 栈顶的工作记录保存的是当前调用函数的信息，所以栈顶 的工作记录也称为活动记录 活动记录。 的工作记录也称为活动记录。
递归调用执行过程： 递归调用执行过程：
6.3 递归算法的设计方法
适宜于用递归算法求解的问题的充分必要条件是： 适宜于用递归算法求解的问题的充分必要条件是： （1）问题具有某种可借用的类同自身的子问题描述的性质 ） （2）某一有限步的子问题（也称作本原问题）有直接的解 ）某一有限步的子问题（也称作本原问题） 存在。 存在。 当一个问题存在上述两个基本要素时， 当一个问题存在上述两个基本要素时，设计该问题的递归 算法的方法是： 算法的方法是： （1）把对原问题的求解表示成对子问题求解的形式。 ）把对原问题的求解表示成对子问题求解的形式。 （2）设计递归出口。 ）设计递归出口。