第4讲 递归专题讲座

递归数列讲座知识与方法递归（推）数列数列的表示方法大致有两类：一是通项公式；另一是递推公式．数列{}n a 的相邻几项的关系式简称为递推式．数学竞赛中遇到有关数列的问题不仅是等差、等比数列，许多是递归数列的问题．在解递归数列的问题时，有时需要根据递推关系求数列的通项，常常用到叠加法：()()()123121--++-+-+=n n n a a a a a a a a ；适当时需要进行代数换元转化为常见数列的通项；有时需要用到从特殊到一般的、归纳－猜想证明方法（常常用到数学归纳法）．但也有一些题目并不要把数列的通项公式求出，而往往可根据题设所给的递推关系，得到新的、更明显的递推关系．而这时就需要综合运用其他数学知识．范例选讲1. 已知11=a ，52=a ，121211++=--+n n n n n a a a a a ，求数列{}n a 的通项公式．解：定义11=F ，02=F ， ,4,3,21=+=--n F F F n n n 由所给关系式得⎪⎪⎭⎫ ⎝⎛+⎪⎪⎭⎫ ⎝⎛+=+-+21221111111n n n a a a ,由归纳法可得 ,2,1,111111122212=⎪⎪⎭⎫⎝⎛+⎪⎪⎭⎫⎝⎛+=++n a a a n nF F n从而1112251322526211+++-=⎪⎭⎫⎝⎛=+n n nn n F F F F F na ,因此(),2,1,15132212112=-=--+++n a n n n F F F n其中 ,2,1,2512515122=⎥⎥⎦⎤⎢⎢⎣⎡⎪⎪⎭⎫⎝⎛--⎪⎪⎭⎫⎝⎛+=--n F n n n 注：本题是今年冬令营的一个测试题．在解题时层层推进，比较容易找到思路．2. 证明数列knk k n n Ca 3012122⋅=∑=++都不能被5整除．解：10=a ，111=a ，又()()12232312322221222+-+=⋅=k k k．所以()()⎥⎦⎤⎢⎣⎡-++=++1212122122241n n n a ()()()()⎥⎦⎤⎢⎣⎡--+++=nn249122249122241．18211=+=x x c ，49212-=-=x x c ,所以()5mod 349182121----+≡-=n n n n n a a a a a ．,,10a a 除以5的余数为 ,1,1,3,2,2,1,4,4,2,3,3,4,1,1形成周期数列．()5mod 12n n a a ≡+，又前12项中没有被5整除的．∴命题得证．注：这是一个逆向运用二阶递推的例子．已知数列的通项公式无法证明所要求证的．反过来通过将数列的二阶递推关系找到，结合数列的周期性加以证明．3. 数列{}n a 满足10=a ，51=a ，() ,3,229322121=--=---na a a a n n n n ，证明n a 都是整数．解：由题意知93221212--=---n n n n a a a a ，9322211--=+-n n n n a a a a ．两式相减， 有1212211323222---+-+--=-n n n n n n n n a a a a a a a a ．整理，得() ,3,23223222111=-+-+=--+-n a a a a a a n n n n n n ，将1-n 个式子联乘得11120223,223n n n a a a a a a +-+-=+-又132=a ．所以322511-+=-+n n n a a a （＊），可得()32213211--=---+n n n n a a a a ，又03201=--a a ，所以0321=---n n a a （１）， 由此可推知Z a n ∈．又由（＊）式推知()3223211+-=+--+n n n n a a a a ，又123201=+-a a 所以n n n n a a 262123211⋅=⋅=+---．与（１）联立可解得322-=+n n a ．注：本题已知数列的一个递推关系是分式形式的，证明＂n a 都是整数＂有一定的难度．因此通过整理变形得到数列的另一个递推公式：0321=---n n a a ．这样证明起来变得容易了．另外本题也可通过先求数列的前几项，再根据结果猜测数列满足0321=---n n a a ，再用数学归纳法加以证明．4. 求证：由31=a ，52=a 及不等式()N n n na a a n a a n n n n n ∈≥+<<-+-+-,21111可唯一确定正整数列{}n a ．解：（1）先证明3+=n n F a 是满足条件的．（{}n F 为斐波那契数列）413F a ==，413F a ==均成立． ∵12213=-F F F .当3≥k 时,()()()21221112111-------+--=+-+=-k k k k k k k k k k k k F F F F F F F F F F F F ,因为()()()()()222132212211111-----+-=--==--=-n n n n n n n n F FF F F F F F F ．若对所有N n ∈，3+=n n F a ． 则验证2≥=k n 时，()123242111+++++--=-=-k k k k kk k F F F a a a ,所以k a a a k k k k <≤-≤-<-+-11211，na a a n a a k k k k k +<<-+-+-1111．存在数列{}n a ．（使{}n a 中每个3+=i i F a ）（２）下证：{}n a 唯一确定．用数学归纳法证明3+=n n F a 且22+≥n a n （＊）．3=n 时，92232371223122=+<<-=<a a a a a ．事实上由已知不等式可推得12112-+-+<<-k k k k k a k a a a k a ，因为N a ∈3，所以83=a ，同时2323+⨯≥a ．所以（＊）成立．4=n 时，1456733561122234223<=+<<-=<a a a a a ，又N a ∈4，所以134=a ．另外，2424+⨯≥a ，所以（＊）成立．设1-=k n 及()4≥=k k n 时（＊）成立．则1+=k n 时， 因为()12122211212=+-≤=--+---k ka k a k a a k a k k k k k ，又⎪⎪⎭⎫⎝⎛+---1212,k k k k a k a a k a 中至多只有一个整数． N a k ∈+1，且12112-+-+<<-k k k k k a k a a a k a ,所以1+k a 确定为4+k F ．且()()21222212341++≥++≥+=+==+++++k k k a a F F F a k k k k k k ．所以1+=k n 时，（＊）成立． 因此{}n a 唯一确定．证毕．综合（１）（２），可发现⎥⎥⎦⎤⎢⎢⎣⎡⎪⎪⎭⎫⎝⎛--⎪⎪⎭⎫⎝⎛+==+++33325125151n n n n F a ． 注：本题用同一法证明．在证明过程中用到了数学归纳法． 5. 数列{}n a 定义如下：01=a ，12=a ，()()⎪⎭⎫ ⎝⎛--+-+=--2111212121n a n n na a n n n n ()3≥n ．试求()11222211132a nC a C n a C a C a f n n n n n n n n n n ----+-++++= 的最简表达式．解：由题意知()()()2112121--+-+=+--n a n n na a n n n n ，所以()()()()!21!2!1!2121n n n a n a n a n n n n --+-+-=+--,令!n a b n n =，01=b ，212=b ．则()()!212121n n b b b n n n n --++=+--,所以()()()⎥⎦⎤⎢⎣⎡-----=-------!111!21221211n b b n b b n n n nn n ，令()!111n b b c nn n n ---=-，则121--=n n c c ，又02=c ，所以()!111n b b nn n -+=-.另一方面，()()()∑∑==--⋅-+=-+=nk k n k k kn nn a k k n n k n a Ck n f 11!!!11．令()∑=--+==nk k n n b k n kn n f g 1!1!，()()k nk k n k n n b k n kn b k n kn g g ⋅--+-⋅-+-+=-∑∑=+=+1111!1!12()()()()1121212!2!12!12-+=-=+=-⋅--+=⋅+--+-⋅-+-+=∑∑∑k kn k k nk k n k b bk n kn b k n kn b k n kn()()()()()()∑∑∑+==+=+--+--=-⋅+--+=12212!!11!!1!1!12n k knk k kn k k k n k k n k k n kn ()()()()()()[]11!111!11!111!11212+-+---=-++-=∑∑+=+=n n n n C n Cn n k kkn nk kkn()()!11!11+--=n n又342323=+=b b g ，所以()()1!2!11!1!31!21!3+-⋅=⎪⎪⎭⎫⎝⎛---++=n n n n g n f n ． 注：这是2000年冬令营的测试题．由已知条件比较容易根据题设的条件想到将数列{}n a 的递推关系除以!n ，从而得到{}n b 的递推关系：()!111n b b nn n -+=-．同时也应将n f 的两边同除以!n ，先求出n g 与1-n g 的关系．6. 设数列{}n a 的通项公式为()()N n a nnn ∈--=312；数列{}n b 的定义如下：20=b ，251=b ，()()N n b b b b n n n ∈--=-+12112．求证：对一切自然数n ，都有[]na nb 2=．证：我们证明更强的命题：N n b nna a n ∈+=-,22,易知数列{}n a 的特征方程是022=--x x ，所以{}n a 的递推公式是N n a a a n n n ∈+=++,212，故N a n ∈．下面用数学归纳法证明加强的命题．(1) 当1=n 时，11=a ，112225-+==b ，命题成立．(2) 假设当k n ≤时，命题成立，都有kkaa kb -+=22．当1+=k n 时，()()()[]12111211222222b b b b b k k kka a a a k k k --++=--=-----+()()1222222bkkkka a a a -++=--122)2(211112222b k k k k k k k k a a a a a a a a -+++=----+--+-+12211112222b k k k k k k a a a a a a -+++=--+++---,而()()[]kkkkk k a a 1222123121-⋅+⋅---=--()[]()1111331++-=-⋅=k k ．所以121=--k k a a ，112225222211b k k k k a a a a ==+=+-+----．所以11221++-++=k k a a k b ， 当1+=k n 时命题也成立．由（１）（２）可知，加强命题成立．同时，又因为N a n ∈,所以[]na nb 2=，原命题得证．注：本题的关键在于加强命题N n b nna a n ∈+=-,22．然后用数学归纳法加以证明．在加强命题之前可通过计算数列的前几项找到规律．7. 设()m a a a A ,,,21 =是由m 个数{}m i a i ,,2,1,1,0 =∈组成的数组．定义运算S 如下：(){}m m b b b b b b A S 2124321,,,,,,-= ，其中当1=i a 时，012=-i b ，12=i b ；当0=i a 时，112=-i b ，02=i b ，m i ,,2,1 =．用()A Sn表示()()() A S S S （n 个S ）．取()1=A ．问在()()n a a aA S n221,,, =有多少对由连续两项组成的数对()1,+i i a a ，满足01==+i i a a ？解：()1=A 时，()()na a a A Sn221,,, =中满足01==+i ia a 的数对()1,+i i a a 的个数记为n f ，满足0=i a ，11=+i a 的数对()1,+i i a a 的个数记为n g ．由题意知，()A Sn中数对()0,0必由()A S n 1-中的数对()1,0经运算S而得到，而()A S n 1-中的数对()1,0必由()A S n 2-中的1或数对()0,0经运算S 而得到．由于()A Sn 2-是22-n 数组，其中有一半的项（即32-n ）为1，所以可得如下递归关系：2312---+==n n n nf g f ． ∴当n 为奇数时， =++=+=-----45323222n n n n n n f f f 3122222110253-=+++++=---n n n f当n 为偶数时，31222212153+=++++=---n n n n f f ．∴()()1n S 中，连续两项是0的数对有()[]nn 12311-+-个．注：本题是个应用题，关键在于通过题意找到递归关系．训练题1. 设{}n a 中的每一项都是正整数，并有21=a ，72=a ，()32121221≥≤-≤---n a a a n n n ．证明：自第二项开始，数列的各项都是奇数．2. 已知00=a ，11=a ，()1221>+=--n a a a n n n ．证明：n a kn k22⇒．3. 已知数列{}n a 满足：11=a ，22=a ，且212212-++=n n n a a a ，() ,2,121222==++n a a a n n n ，试求数列的通项公式．4. 设d 为正整数，求()d x x x n mod 021≡++ ，()n i dx i ≤≤<<10的解()n x x x ,,,21 的个数．。

复习输入a,b,c,计算m 。

已知m=),,max(),,max(),,max(c b b a c b b a c b a +⨯+ 请把求三个数的最大数max(x,y,z)定义成函数和过程两种方法作此题。

递 归为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自已来定义自己的方法，称为递归定义。

例如：定义函数f(n)为：/n*f(n －1) (n>0)f(n)= |\ 1(n=0)则当n>0时，须用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)……当n=0时，f(n)=1。

由上例我们可看出，递归定义有两个要素：（1） 递归边界条件。

也就是所描述问题的最简单情况，它本身不再使用递归的定义。

如上例，当n=0时，f(n)=1，不使用f(n-1)来定义。

（2） 递归定义：使问题向边界条件转化的规则。

递归定义必须能使问题越来越简单。

如上例：f(n)由f(n-1)定义，越来越靠近f(0),也即边界条件。

最简单的情况是f(0)=1。

递归算法的效率往往很低, 费时和费内存空间. 但是递归也有其长处, 它能使一个蕴含递归关系且结构复杂的程序简介精炼, 增加可读性. 特别是在难于找到从边界到解的全过程的情况下, 如果把问题推进一步使其结果仍维持原问题的关系, 则采用递归算法编程比较合适.递归按其调用方式分为: 1. 直接递归, 递归过程P 直接自己调用自己; 2. 间接递归, 即P 包含另一过程 D, 而D 又调用P.递归算法适用的一般场合为:1. 数据的定义形式按递归定义.如裴波那契数列的定义: f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2.对应的递归程序为:Function fib(n : integer) : integer;Beginif n = 0 then fib := 1 { 递归边界 }else if n = 1 then fib := 2else fib := fib(n-2) + fib(n-1) { 递归 }End;这类递归问题可转化为递推算法, 递归边界作为递推的边界条件.2. 数据之间的关系(即数据结构)按递归定义. 如树的遍历, 图的搜索等.3. 问题解法按递归算法实现. 例如回溯法等.从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到" 尽头 "的时候, 再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断" 回溯 "寻找解的方法, 称作" 回溯法 ". 例1、给定N （N>=1），用递归的方法计算1+2+3+4+…+（n-1）+n 。

离散数学中的递归定义与算法描述递归是离散数学中一个重要的概念，它在数学、计算机科学以及其他领域中都起着至关重要的作用。

递归定义是指一个对象或者概念被自身的一部分来定义的情况。

在这篇文章中，我们将探讨离散数学中的递归定义以及如何用算法描述递归。

一、递归定义递归定义在离散数学中是很常见的。

它主要用于定义数列、集合、图形等数学对象。

递归定义通常包含两个方面：基本情况和递归规则。

基本情况是指在递归定义中的最简单的情况，它不是通过递归规则来定义的，而是直接给出的。

递归规则用于描述一个对象如何由它自身的一部分来定义。

例如，斐波那契数列是一个经典的递归定义的数列。

它的基本情况是当 n=0 或 n=1 时，斐波那契数列的值都为 1。

递归规则是当 n 大于 1 时，斐波那契数列的第 n 项等于前两项的和，即 F(n) = F(n-1) + F(n-2)。

递归定义的一个重要特点是它能够自然而然地表达对象之间的层次结构和递进关系。

通过递归定义，我们可以清晰地描述一个复杂对象是如何由简单的组成部分逐步构建而成的。

二、算法描述在离散数学中，我们经常需要将递归定义转化为算法来实现。

算法描述是一种精确、可实现的规范，用于描述如何计算或实现一个递归定义的对象。

算法描述主要包括输入、输出和具体的计算步骤。

输入是指算法需要的初始条件或输入数据。

输出是算法计算得到的结果或输出数据。

算法描述需要根据递归规则来定义具体的计算步骤。

通常情况下，算法会包含递归调用和条件判断两个主要的计算步骤。

对于递归定义的对象，算法描述需要考虑递归调用的情况。

递归调用是指在算法中调用自身来解决更小规模的子问题。

通过递归调用，算法可以逐步解决递归定义的对象，直到达到基本情况为止。

同时，算法描述也需要考虑条件判断的情况。

条件判断是指在算法的执行过程中，根据一定条件来选择不同的计算路径。

在递归算法中，条件判断通常用于判断是否达到了基本情况，从而决定是否继续进行递归调用。

递归的理解
递归是一种算法或编程技巧，它通过自身调用来解决问题，常常被用来处理具有递归结构的问题。

在递归中，一个函数或子程序会重复调用自身，直到达到终止条件为止。

递归的理解需要注意以下几个方面：
首先，递归必须有一个终止条件，否则会陷入死循环。

终止条件是指递归应该停止的条件，一旦达到这个条件，递归就会结束。

其次，在递归过程中，每一级递归都需要相同的处理方式。

也就是说，每次递归都要按照同样的逻辑进行处理，直到达到终止条件。

第三，在递归中，每次调用都会有一定的开销，包括函数调用、参数传递和栈空间的分配等。

因此，在使用递归时，需要注意内存的使用和性能的优化。

最后，递归常常被用来解决复杂的问题，例如快速排序、归并排序、二叉树的遍历等。

但是，如果不恰当地使用递归，会导致栈溢出等问题。

因此，在使用递归时，需要仔细考虑其适用性和实现方式。

总之，递归是一种非常有用的算法思想，理解递归需要掌握其基本原理和注意事项，才能正确地应用到实际问题中。

- 1 -。

【C】函数递归算法讲解在数学与计算机科学中，递归算法是指在函数的定义中使用函数自身的方法。

在程序中，递归是通过函数的调用来实现的。

函数直接调用其自身，称为直接递归；函数间接调用其自身，称为间接递归。

在函数定义中，其内部操作又直接或间接地调用了自身，则称这样的函数为递归函数。

生活中我们也存在这样的递归现象，比如：从前有座山,山里有个庙，庙里有个老和尚和一个小和尚。

一天，老和尚在对小和尚讲故事，故事的内容是：从前有座山,山里有个庙，庙里有个老和尚和一个小和尚。

一天，老和尚在对小和尚讲故事，故事的内容是：从前有座山,山里有个庙，庙里有个老和尚和一个小和尚。

一天，老和尚在对小和尚讲故事，故事的内容是……故事中又调用了这个故事正如函数中又调用了这个函数一样。

•••••••••••#include<iostream>using namespace std;int f()//自定义函数{ return f();}int main()//主函数 { cout<<f();//函数调用 return 0;} 但上述函数的定义是不合理的，因为递归函数和生活中的递归现象具有不同之处：生活中有些递归现象可以无限递归，但递归函数必须有递归终止条件。

所以，递归函数有两大要素：①递归关系式：对问题进行递归形式的描述。

②递归终止条件：当满足该条件时以一种特殊情况处理而不是用递归关系式处理。

参考程序：••••••••••••••••••#include<iostream>using namespace std;void output(int n)//自定义函数 { if(n==1) cout<<1<<' ';//递归终止条件 else//递归关系式 { output(n-1); cout<<n<<' '; } }int main()//主函数{ int n; cin>>n; output(n);//函数调用 return 0;}参考程序：•••••••••••••#include<iostream>using namespace std;int sum(int n)//自定义函数 { if(n==1) return 1;//递归终止条件 else return n+sum(n-1);//递归关系式}int main()//主函数{ int n; cin>>n; cout<<sum(n);//函数调用 return 0;}参考程序：•••••••••••••#include<iostream>using namespace std;int jc(int n)//自定义函数 { if(n==1) return 1;//递归终止条件 else return n*jc(n-1);//递归关系式 }int main()//主函数 { int n; cin>>n; cout<<jc(n);//函数调用 return 0;}参考程序：••••••••••••••#include<iostream>using namespace std;int xn(int x,int n)//自定义函数 { if(n==0) return 1;//递归终止条件 else return x*xn(x,n-1);//递归关系式}int main()//主函数{ int x,n; cin>>x>>n; cout<<xn(x,n);//函数调用 return 0;}参考程序：•••••••••••••#include<iostream>using namespace std;int f(int n)//自定义函数 { if(n<=1) return n;//递归终止条件 else return f(n-1)+f(n-2);//递归关系式 }int main()//主函数 { int n; cin>>n; for(int i=0;i<=n;i++) cout<<f(i)<<' ';//函数调用 return 0;}••••••••••••••#include<iostream>using namespace std;int gcd(int m,int n)//自定义函数 { if(m%n==0) return n;//递归终止条件 else returngcd(n,m%n);//递归关系式}int main()//主函数{ int m,n; cin>>m>>n; cout<<gcd(m,n);//函数调用 return 0;}••••••••••••••••••••••••••#include<iostream>using namespace std;int a[20];bool flag;//利用全局变量falg传递结果void judge(int n,int m)//自定义函数{ if(a[n]==m) flag=true;//递归终止条件else if (n==1) return;//递归终止条件 else//递归关系式 { judge(n-1,m-a[n]); judge(n-1,m); }}int main()//主函数 { int n,m; cin>>n; for (int i=1; i<=n; ++i) cin>>a[i]; cin>>m; flag=false; judge(n,m);//函数调用if (flag) cout<<'YES'<<endl; else cout<<'NO'<<endl; return 0;}••••••••••••••••••••••••#include<iostream>#include<cmath>using namespace std;int sum;void res(int a,int y)//自定义函数{ for(int i=y;i<=sqrt(a);i++) { if(a%i==0) res(a/i,i); } sum++;}int main()//主函数{ int n,a; cin>>n; while(n--) { cin>>a; sum=0; res(a,2); cout<<sum<<endl; } return 0;}••••••••••••••#include<iostream>using namespace std;int f(int n)//自定义函数 { if(n==1) return 1;//递归终止条件 else return 2*f(n-1)+1;//递归关系式}int main()//主函数 { int n; cin>>n; cout<<f(n);//函数调用 return 0;}•••••••••••••••••••#include<iostream>using namespace std;int step=0;//步数void hanoi(int n,char a,char b,char c)//自定义函数{ if(n==1) cout<<'第'<<++step<<'步：'<<'将圆盘'<<n<<'从'<<a<<'移动到'<<c<<endl; else { hanoi(n-1,a,c,b); cout<<'第'<<++step<<'步：'<<'将圆盘'<<n<<'从'<<a<<'移动到'<<c<<endl; hanoi(n-1,b,a,c); } }int main()//主函数 { int n; cin>>n; hanoi(n,'A','B','C');//函数调用 return 0;}。

1.用递归法计算n!【讲解】递归是算法设计中的一种基本而重要的算法。

递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题，是分治策略的具体体现。

递归方法具有易于描述、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用，是许多复杂算法的基础。

递归概述一个函数在它的函数体内调用它自身称为递归（recursion）调用。

是一个过程或函数在其定义或说明中直接或间接调用自身的一种方法，通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

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

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

一般来说，递归需要有边界条件、递归前进段和递归返回段。

当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

使用递归要注意以下几点：（1）递归就是在过程或函数里调用自身；（2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。

例如有函数r如下：int r(int a){ b=r(a−1);return b;}这个函数是一个递归函数，但是运行该函数将无休止地调用其自身，这显然是不正确的。

为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。

常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。

构造递归方法的关键在于建立递归关系。

这里的递归关系可以是递归描述的，也可以是递推描述的。

例4-1 用递归法计算n!。

n!的计算是一个典型的递归问题。

使用递归方法来描述程序，十分简单且易于理解。

（1）描述递归关系递归关系是这样的一种关系。

设{U1,U2,U3,…,U n,…}是一个序列，如果从某一项k开始，U n和它之前的若干项之间存在一种只与n有关的关系，这便称为递归关系。

注意到，当n≥1时，n!=n*(n−1)!（n=0时，0!=1），这就是一种递归关系。

递归法的概念1. 递归法就像是套娃游戏，一个套一个，越套越小，直到最后一个不能再套为止。

想象一下，你正在玩俄罗斯套娃，每打开一个娃娃，里面还有一个更小的，直到最后一个小得不能再小。

这就是递归的精髓!2. 在编程世界里，递归就是函数自己调用自己。

听起来有点像绕口令，对吧？就好比你问妈妈"晚饭吃什么"，妈妈说"问问爸爸"，你又去问爸爸，爸爸说"问问妈妈"。

如此循环往复，直到有人受不了喊一声"吃披萨!"，这个循环才算结束。

3. 递归法的关键在于:a) 基本情况: 就是那个最小的娃娃，再也不能打开的那个。

b) 递归步骤: 就是不断打开娃娃的过程，每次都变小一点。

c) 终止条件: 就是当你发现再也打不开娃娃时，游戏就结束了。

4. 举个栗子吧! 假设我们要计算5的阶乘(5!)。

用递归法怎么想呢？- 5! = 5 * 4!- 4! = 4 * 3!- 3! = 3 * 2!- 2! = 2 * 1!- 1! = 1 (这就是我们的基本情况，不能再分解了)然后我们再反过来，一步步乘回去，最后得到5!=120。

是不是感觉脑袋有点晕？没关系，这就是递归的魅力所在!5. 使用递归法时要小心点哦，别像陷入无限循环的"先有鸡还是先有蛋"的问题。

要是没有设好终止条件，你的程序就会像失控的列车，一路狂奔到计算机喊"停不下来啦!"6. 递归虽然看起来很酷，但也不是万能的。

有时候它会让你的程序变得像蜗牛爬行一样慢。

所以，要像品尝美食一样适度使用递归，既能享受其优雅，又不至于撑着肚子走不动路。

7. 总的来说，递归就像是解开一个层层包裹的神秘礼物。

每打开一层，你都离真相更近一步。

当你终于拆到最后一层，豁然开朗的感觉简直妙不可言！。