第4章 递归基础

4.1递归概述4.2Fibonacci数列4.3其它典型题目-4.3.1Hanoi塔问题-4.3.2数的计算第4章递归4.1递归的概念与应用递归是一种非常重要的算法思想，它不仅是一种编程技巧，更是一种解决问题的思维方式。在本章中，我们将深入学习递归的基本概念，并通过几个经典的例子来掌握它的应用和优化方法。递归通过将复杂问题分解为更小的、相似的子问题来解决。理解递归的核心在于找出递归关系和递归终止条件，这是编写高效递归代码的关键。第4章递归4.1递归概述递归是一种强大的算法设计思想，通过将复杂问题分解为更小的子问题来求解。理解递归的关键在于掌握其“递推”与“回归”的过程。核心思想：将复杂问题分解为简单的子问题，直到子问题可直接求解，再回溯得到原问题的解。核心思想工作流程：包含“递推”（将问题分解为子问题）和“回归”（从子问题回溯求解）两个过程。工作流程典型应用：1.问题定义递归（如阶乘、斐波那契）2.数据结构递归（如树、文件夹）3.问题解法递归（如汉诺塔）典型应用1)定义F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2)。从第三项开始，每一项都是前两项之和。2)递归求解代码利用递归思想实现的C++代码如下：4.2.1Fibonacci数列概述intfib(inti)//返回第i项的值{if(i==0)return0;if(i==1) return1;returnfib(i-2)+fib(i-1);}4.2.2消除重复求解（备忘录）1.问题分析原始递归解法会导致大量的重复计算，随着n的增大，时间复杂度呈指数级增长，效率极其低下。2.解决方案：备忘录法引入“备忘录”（通常是数组或哈希表），将已经计算过的子问题结果存储起来。当再次需要该结果时，直接从备忘录中读取，避免重复递归计算。inta[100]={0,1};//备忘录数组intfib(inti){if(a[i]>0||i==0)

returna[i];a[i]=fib(i-1)+fib(i-2);returna[i];}图4-2斐波那契数列递归求解的重复计算示意与优化代码问题描述：将n个圆盘从A柱移到C柱，每次只能移动一个，且不能将大盘放在小盘上移动规则：一次只能移一个圆盘。圆盘只能在三根柱子间移动。任何时刻，大盘不能放在小盘之上。图4-3-1Hanoi塔初始状态图4.3.1Hanoi塔问题递归思想：要移动n个盘子，可以分解为三个步骤：1.将n-1个盘子从A柱移到B柱（以C柱为辅助）。2.将第n个盘子从A柱移到C柱。3.将n-1个盘子从B柱移到C柱（以A柱为辅助）。核心：将移动n个盘子的问题，转化为移动n-1个盘子的子问题。算法分析核心代码：递归函数move实现移动逻辑。voidmove(intn,chara,charc,charb){if(n==0)return;move(n-1,a,b,c);//把n-1个盘子从a移到b，用c做辅助cout<<++k<<":"<<a<<"→"<<c<<endl;//移动第n个盘子move(n-1,b,c,a);//把n-1个盘子从b移到c，用a做辅助}参数说明：n：盘子数量，a：源柱子，c：目标柱子，b：辅助柱子4.3.1Hanoi塔问题（程序实现）4.3.2数的计算（题目与分析）题目规则：找出满足特定规则的数的个数。规则是在数的左边添加不超过其一半的自然数，且该过程可递归进行。题目描述递归分析：设f(n)为n能扩展出的数的个数，则递推公式为：f(n)=1+f(1)+...+f(n/2)其中，“1”代表数n本身。算法分析优化问题：在直接递归求解过程中，会存在大量重复计算子问题的情况，导致效率低下。解决：需引入“备忘录”技术进行剪枝优化。优化策略4.3.2数的计算（程序实现）inta[1001];//备忘录数组intdfs(intm){//递归函数定义if(a[m]>0)returna[m];//记忆化搜索a[m]=1;//包含自身for(inti=1;i<=m/2;i++)//枚举左加数a[m]+=dfs(i);//累加结果returna[m];//返回总数}//函数结束课堂小结核心知识回顾递归思想：将复杂问题逐步分解为规模更小的子问题，通过递归调用自身求解，最终合并子问题答案得到原问题解。经典实