摘出本章比较感兴趣的一部分,首先是关于递归的简述。
递归有两个基本法则:
1.
基准情形:不用递归就能求解
2.
不断推进:对于需要用递归求解的情形,递归调用必须朝着基准情形推进。
下面列举一些例子。
例1 无终止的递归
public static int bad(int n){
if(n==0)
return 0;
else
return bad(n/3+1)+n-1;
}
在这个例子中,bad(1)会反复求bad(1),同样bad(2)也是。将陷入死循环,知道jvm奔溃。
例2 打印输出正整数
设有一个正整数n并希望将其打印。而仅有的IO只允许处理单个数字并输出(printDigit)。分析:要打印76321,首先打印出7632,再打出1。而打印出1只需printDigit(n%10)就可以。打印7632可以用print(76321/10)。
public static void print(long n){
if(n>=10)
print(n/10);
printDigit(n%10);
}
不过这个例子并不是很高效,因为mod是非常耗时的,n%10=n-(n/10)*10。
因此引出递归的第三个法则:
3.
设计法则:假设所有的递归调用都能运行。
当编写递归程序时,要牢记其第四条基本法则:
4.
合成效益法则:在求解一个问题的同一实例时,切勿在不同的递归调用中做重复性工作。
因此,使用递归来计算斐波那契之类的简单数学函数值并不合适。
分享到:
相关推荐
2021-算法设计与分析-02-递归与分治-2.pdf
这是对计算机引论导引课程ppt资料 第1章:概念自动机语言 第2章:正则语言 第3章:上下文无关语言 第4章:下推自动机 第5章:图灵机 第6章:非确定性图灵机、上下文无关语言的可判定性 第7章:可判定性回顾 第8章:...
共6章内容,算法引论,递归与分治,动态规划,贪心算法,回溯法,分支限界法。
本资料详细讲解了如下内容:算法引论,递归与分治策略,动态规划,贪心算法,回溯法,分支限界法,NP完全性理论与近似算法。注:PPT格式。
计算机算法分析与设计 主要内容:算法引论,递归于分治策略,动态规划,贪心算法,回溯法,分支界限法,概率算法,NP完全性理论,近视算法,算法优化策略
第1章 算法引论 第2章 递归与分治策略
21世纪大学本科计算机专业系列...目录概览第1章 算法引论 第2章 递归与分治策略 第3章 动态规划 第4章 贪心算法 第5章 回溯法 第6章 分支限界法 第7章 概率算法 第8章 NP完全性理论 第9章 近似算法 第10章 算法优化策略
考研用书:算法设计与分析电子教案 第1章 算法引论 第2章 递归与分治策略
第一章 引论 1.1 组合数学研究的对象 1.2 组合问题典型实例 1.2.1 分派问题 1. 2.2 染色问题 1.2.3 幻方问题 1.2.4 36军官问题 1.2.5 中国邮路问题 习 题 第二章 排列与组合 2.1 两个基本计数...
高级数理逻辑第七章:λ-演算(Lambda 演算);λ-演算是一套用于研究函数定义、函数应用和递归的形式系统
第一部分 基本概念和算法导引 第1章 算法分析基本概念 第2章 数学预备知识 第3章 数据结构 第4章 堆和不相交集数据结构 第二部分 基于递归的技术 第5章 归纳法 第6章 分治 第7章 动态规划 第三部分 最先割...
目录: 1.算法引论 2.递归与分治策略 3.动态规划 4.贪心算法 5.回溯法 6.分支限界法 7.概率算法 8.NP完全性理论 9.近似算法 10.算法优化策略
主要内容介绍 第1章 算法引论 第2章 递归与分治策略 第3章 动态规划 第4章 贪心算法 第5章 回溯法 第6章 分支限界法
这是上课用的课件,主要讲解程序设计的基础东西,非常基础、清晰,适宜作为启蒙浏览,对于初学者应该有很大帮助。一共九章。...第六章 递归算法设计;第七章和第八章合为一个PPT;第九章 可编程结构模型;
第一章 引论 基本概念 第二章 语言基础知识 1. 基本概念 2. 求给定句型的推导(最左、最右) 3. 画出给定句型的语法分析树,并指出其短语,直接短语和句柄4. 证明文法的二义性 第三章 词法分析 1. 基本概念 2. NFA--...
第一章 引论 1.1 什么叫编译程序 1.2 编译过程概述 1.3 编译程序的结构 1.4 编译程序与程序设计环境 1.5 编译程序的生成 第二章 高级语言及其语法描述 2.1 程序语言的定义 2.2 高级语言的一般特性 ...
第1章 算法引论 第2章 递归与分治策略 第3章 动态规划 第4章 贪心算法 第5章 回溯法 第6章 分支限界法 第7章 概率算法 第8章 NP完全性理论 第9章 近似算法 第10章 算法优化策略
第一章 无尽之旅 历史一瞥 设计游戏 游戏类型 集思广益 设计文档和情节图板 使游戏具有趣味性 游戏的构成 常规游戏编程指导 使用工具 从准备到完成一使用编译器 实例:FreakOut 总结 ...