递归的经典例子,(4)递归式求解的三种方法
递归的经典例子,(4)递归式求解的三种方法详细介绍
本文目录一览： 递归算法的经典例子
具体如下。递归阶乘n!=n*(n-1)*(n-2)*...*1(n>0)publicstaticIntegerrecursionMulity(Integern){if(n==1){汉诺塔问题publicstaticvoidhanio(intn，chara，charb，charc){判定一系列字符串中是否有相同的内容publicclassCrf。递归算法（英语：recursionalgorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的。
计算机里面什么是递归？
递归，就是在运行的过程中调用自己。构成递归需具备的条件：1. 子问题须与原始问题为同样的事，且更为简单；2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。例如，下列为某人祖先的递归定义：某人的双亲是他的祖先（基本情况）。某人祖先的双亲同样是某人的祖先（递归步骤）。斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21..... I[1] 斐波纳契数列是典型的递归案例：递归关系就是实体自己和自己建立关系。Fib(0) = 1 [基本情况] Fib(1) = 1 [基本情况] 对所有n > 1的整数：Fib(n) = (Fib(n-1) + Fib(n-2)) [递归定义] 尽管有许多数学函数均可以递归表示，但在实际应用中，递归定义的高开销往往会让人望而却步。例如：阶乘（1) = 1 [基本情况] 对所有n > 1的整数：阶乘（n) = (n * 阶乘（n-1)) [递归定义] 一种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这时你已经知道该怎么做的。如此的定义在数学中十分常见。例如，集合论对自然数的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。
递归就是一个过程或者函数在运行的过程中调用自己。他通常可以把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来解决。
递归,又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。
程序调用自身的编程技巧称为递归递归，作为一种算法，在程序设计语言中广泛应用。
递归的意思是一般指的改变目录及其子目录和文件 由后往前层层递归所谓$:也就是咱们平常说的“命令提示符”也就是你可一在后面瞧命令
在数学和计算机科学中，当一类对象或方法可以由两个属性定义时，它们表现出递归行为:
简单的基线条件---不使用递归产生答案的终止情况
一组规则将所有其他情形缩减到基线条件
例如，以下是某人祖先的递归定义:
某人的父母是他的祖先(基线条件)
某人祖先的祖先也是他的祖先(递归步骤)
斐波那契数列是递归的经典例子:
Fib(0) = 1 基线条件1；
Fib(1) = 1 基线条件2；
对所有整数n,n > 1时：Fib(n) = (Fib(n-1) + Fib(n-2))。
许多数学公理基于递归规则。例如，皮亚诺公理对自然数的形式定义可以描述为:0是自然数，每个自然数都有一个后继数，它也是自然数。通过这种基线条件和递归规则，可以生成所有自然数的集合。
递归定义的数学对象包括函数、集合，尤其是分形。
递归还有多种开玩笑的“定义”。
非正式定义
递归是当程序的一个步骤涉及调用程序本身的过程。经历递归的过程被称为“递归”。
要理解递归，必须认识到程序和程序运行之间的区别。程序是基于一组规则的一组步骤。程序的运行实际上包括遵循规则和执行步骤。一个类比:一个程序就像一个书面的食谱；运行一个程序就像实际准备饭菜一样。
递归与过程规范中对其他程序执行的引用相关，但不相同。例如，食谱可能指烹饪蔬菜，而需要依次加水等步骤是另一个程序。然而，递归过程是指(至少)其中一个步骤需要一个相同过程的新实例，就像酸面团配方需要上次制作相同配方时剩下的一些面团。这立即产生了一个无限循环的可能性；如果为了程序能够完成，在某些情况下跳过有问题的步骤，这样递归只能在定义中被正确使用，比如一个酸面团配方，它还告诉您如何获取一些生面团，以防您以前从未做过生面团。即使定义正确，递归过程对人类来说也不容易执行，因为它需要区分过程的新调用和旧调用(部分执行)；这需要对程序的各种同步实例的进展程度进行一些管理。因此，递归定义在日常情况下非常罕见。一个例子可以是下面的寻找迷宫之路的过程，继续前进，直到到达出口或分支点(死角被认为是带有0个分支的分支点)。如果到达的点是出口，终止。否则，递归地使用该过程，依次尝试每个分支；如果每次试验都只到达死胡同而失败，返回到导致这个分支点的路径并报告失败。这是否真正定义了终止过程取决于迷宫的性质:它不允许循环。在任何情况下，执行该过程都需要仔细记录所有当前探索的分支点，以及哪些分支已经被彻底尝试过。
在语言中
语言学家诺姆·乔姆斯基和其他许多人都认为，一种语言中语法句子数量没有上限，语法句子长度也没有上限(超出了实际的限制，例如说出来的时间)，这可以解释为自然语言中递归的结果。 这可以用句法范畴的递归定义来理解，例如句子，一个句子可以有一个结构，在这个结构中，跟在动词后面的是另一个句子:多萝西认为女巫是危险的，在这个结构中，女巫是危险一句出现在更大的句子中。因此，一个句子可以递归地(非常粗略地)定义为一个结构，包括一个名词短语、一个动词和可选的另一个句子。这实际上只是递归数学定义的一个特例。
这提供了一种理解语言创造的方法——无限数量的语法句子——因为它立即预言句子可以是任意长度的:多萝西认为托托怀疑铁皮人说的....除了可以递归定义的句子之外，还有许多结构，因此一个句子可以通过许多方式将一个类别的实例嵌入另一个类别。多年来，一般来说，语言都被证明适合这种分析。
然而，最近，丹尼尔·埃弗雷特基于他对皮拉汉语的主张，对递归是人类语言的一个基本属性这一普遍接受的观点提出了挑战。Andrew Nevins, David Pesetsky 和 Cilene Rodrigues是许多反对这一观点的人之一。 在任何情况下，文学自我引用都可以被认为不同于数学或逻辑递归。
递归不仅在语法中起着至关重要的作用，在自然语言语义中也是如此。例如，单词and可以理解为一种功能，它可以应用于句子含义，从而创造出新的句子，同样也可以用于名词短语含义、动词短语含义和其它。它也适用于不及物动词、及物动词或双及物动词。为了给它提供一个适当灵活的单一表示，并且通常被定义为使得它可以将这些不同类型的含义中的任何一种作为参数。这可以通过为一个简单的案例定义它来实现，在这个案例中，它组合了句子，然后根据简单的案例递归地定义其他案例。
递归语法是一种包含递归生成规则的形式语法。
递归幽默
递归有时在计算机科学、程序设计、哲学或数学教科书中幽默地使用，通常是通过给出循环定义或自我引用，在循环定义或自我引用中，假定的递归步骤不会更接近基线条件，而是导致无限回归。这样的书在词汇表中包含一个笑话条目并不罕见，大致如下：
另一个笑话是“要理解递归，你必须理解递归。” 在谷歌网络搜索引擎的英文版本中，当搜索“递归”时，网站会提示“你的意思是:递归？”Andrew Plotkin的另一种形式如下:“如果你已经知道递归是什么，就记住答案。否则，找一个比你更靠近道Douglas Hofstadter 的人；然后问他或她什么是递归。”
递归首字母缩写也可以是递归幽默的例子。例如，PHP代表“PHP Hypertext Preprocessor”，WINE代表“WINE Is Not an Emulator.”，GNU代表“GNU's not Unix”。
在数学中
递归定义的集合
例子:自然数
递归定义集合的典型例子由自然数给出:
0是自然数；
如果n是自然数，那么n+1也是自然数；
自然数集合是满足前两个属性的最小集合。
例子:真正可达命题的集合
另一个有趣的例子是公理系统中所有“真正可达”命题的集合。
如果一个命题是公理，它就是一个真正可达的命题。
如果一个命题可以通过推理规则从真正可达命题中获得，那么它就是真正可达命题。
真正可达命题集是满足这些条件的最小命题集。
这个集合被称为“真正可达命题”，因为在数学基础的非建设性方法中，真正命题的集合可能大于由公理和推理规则递归构造的集合。有限细分规则
有限细分规则是递归的几何形式，可用于创建类似分形的图像。细分规则从由有限多个标签标记的多边形集合开始，然后以仅依赖于原始多边形标签的方式将每个多边形细分为更小的标记多边形，这个过程可被迭代。创建康托集合的标准“中间三分之一”技术是细分规则，重心细分也是细分规则。函数递归
一个函数可以根据自身被部分地定义。一个常见的例子是斐波那契数列: F(n) = F(n ? 1) + F(n ? 2)。为了使这样的定义有用，它必须引入非递归定义的值，在这种情况下，F(0) = 0，F(1) = 1。
一个著名的递归函数是阿克曼函数，它不同于斐波那契数列，如果没有递归，它将无法被表达的。涉及递归定义的证明
如前几节所述，将标准的案例证明技术应用于递归定义的集合或函数，会产生结构归纳法，这是数学归纳法的一种强有力的推广，广泛用于数学逻辑和计算机科学中的推导证明。递归优化
动态规划是一种优化方法，它以递归的形式重述了多阶段或多步骤优化问题。动态规划的关键结果是贝尔曼方程(Bellman equation)，它将优化问题早期(或较早步骤)的值写入到后期(或较晚步骤)的值中。递归定理
在集合论中，这是一个保证递归定义函数存在的定理。给定一个集合X,集合X中的一个元素a和一个函数f: X -->X，定理表明存在一个唯一的函数F：N-->X(N表示包括0的自然数集合)，使得满足F(0)=a , F(n+1)=f(F(n)) (对于任何自然数n)。
唯一性的证明
取两个函数F：N-->X和G：N-->X使得满足：
F(0)=a
G(0)=a
F(n+1)=f(F(n))
G(n+1)=f(G(n))
其中a是集合X中的一个元素。
数学归纳法可以证明对于所有自然数都有F(n)=G(n)：
基线条件：当n=0时，等式F(0)=a=G(0)成立；
递归步骤：假设当k∈N时，F(k)=G(K)成立,然后F(k+1)=f(F(k))=f(G(k))=G(k+1),因此F(k)=G(k)意味着F(k+1)=G(k+1)
通过归纳，F(n)=G(n) (其中n∈N)。
在计算机科学中
一种常见的简化方法是将一个问题分成相同类型的子问题。作为一种计算机编程技术，这被称为分治法，是许多重要算法设计的关键。分治法是一种自上而下解决问题的方法，通过解决越来越小的实例来解决问题。相反的方法是动态编程，这种方法是自下而上的方法，通过解决越来越大的实例来解决问题，直到达到所需的大小。
递归的一个经典例子是阶乘函数的定义，这里用C代码给出:
unsigned int factorial(unsigned int n) {undefined
if (n == 0) {undefined
return 1;
} else {undefined
return n * factorial(n - 1);
}
}
该函数在输入的较小版本(n-1)上递归调用自身，并将递归调用的结果乘以n，直到达到基线条件，类似于阶乘的数学定义。
当一个函数被定义为更简单、通常更小的自身时，计算机编程中的递归就是一个例子。然后通过组合从问题的简单版本中获得的解决方案来设计问题的解决方案。递归的一个示例应用是在编程语言的解析器中。递归的最大优点是通过有限的计算机程序可以定义、解析或产生无限组可能的句子、设计或其他数据。
递推关系是递归定义一个或多个序列的方程，可以“解决”某些特定类型的递推关系来获得非递归定义。
在艺术领域
俄罗斯娃娃或俄罗斯套娃是递归概念的一个物理艺术例子。
自1320年乔托的Stefaneschi三联画问世以来，递归就一直用于绘画。它的中央面板包含红衣主教Stefaneschi的跪像，举着三联画本身作为祭品。
M.C. Eschers 印刷画廊 (1956)描绘了一个扭曲的城市，其中包含一个递归包含图片的画廊，因此无限。
10道pascal的递归习题，简单一点啊
1、 斐波那契数列
【问题描述】
斐波那契数列0,1,1,2,3,5,8,13,21,34,55…从第三项起，每一项都是紧挨着的前两项的和，写出计算斐波那契数列任意一个数据项的递归程序。
【输入格式】
所求的项数
【输出格式】
数据项的值
【输入样例】
10
【输出样例】
34
2、 倒序数
【问题描述】
用递归算法写程序，输入一个非负整数，输出这个数的倒序数。
【输入格式】
一个非负整数
【输出格式】
倒序结果
【输入样例】
123
【输出样例】
321
3、 十进制数转成八进制数
【问题描述】
用递归算法，把任一给定的十进制正整数转换成八进制数。
【输入格式】
一个正整数，表示需要转换的十进制数。
【输出格式】
一个正整数，表示转换之年的八进制数。
【输入样例】
15
【输出样例】
17
4、 求N!的值
【问题描述】
用递归算法，求N！的精确值（N以一般整数输入）。
【输入样例】
10
【输出样例】
10！= 3628800
5、 求最大公约数
【问题描述】
用递归算法求两个正整数M和N的最大公约数。
【输入格式】
两个数，即M和N的值。
【输出格式】
最大公约数。
【输入样例】
8 6
【输出样例】
Gcd=2
6、 背包问题
【问题描述】
简单的背包问题。设有一个背包，可以放入的重量为S。现有N件物品，重量分别为W1，W2，…，Wn（1≤i≤n）,均为正整数，从n件物品中挑选若干件，使得放入背包的重量之和正好为S。找到一组即可。
【输入格式】
第一行是物品总件数和背包的载重量，第二行为各物品的重量。
【输出格式】
各所选物品的序号和重量。
【输入样例】
5 10
1 2 3 4 5
【输出样例】
Number : 1 weight : 1
Number : 4 weight : 4
Number : 5 wright : 5
7、 2的幂次方
【问题描述】
任何一个正整数都可以用2的幂次方表示。例如：
137=27+23+20
同时约定用括号来表示方次，即ab要表示为a(b)。
由此可知，137可表示为
2(7)+2(3)+2(0)
进一步：
7=22+2+20 (21用2表示)
3=2+20
所以，最后137可表示为：
2(2(2)+2+2(0))+2(2+2(0))+2(0)
又如：
1315=210+28+25+2+1
所以，最后137可表示为：
2(2(2+2(0))+2)+2(2+2(0))+2(0)
【输入格式】
正整数N（N≤20000）。
【输出格式】
用0，2表示的符合约定的N（在表示中不能有空格）。
【输入样例】
137
【输出样例】
2(2(2)+2+2(0))+2(2+2(0))+2(0)
8、 加法表(NOIP1998)
【问题描述】
著名科学家卢斯为了检查学生对进位制的理解，给出了如下的一张加法表，表中的字母代表数字。例如：
+ L K V E
L L K V E
K K V E KL
V V E KL KK
E E KL KK KV
其含义为:
： L+L=L, L+K=K, L+V=V, L+E=E
K+L=K, K+K=V, K+V=E, K+E=KL
…
E+E=KV
根据这些规则可推导出：L=0，K=1，V=2，E=3
同时可以确定该表表示的是4进制加法。
【输入格式】
第一行表示行数N（N≤9）。
以下N行，每行包括N个字符串，每个字符串间用空格隔开。（字符串仅有一个“+”号，其他都由大写字母组成）。
【输出格式】
第一行是各个字母表示的数。
第二行表示加法运算是几进制的。
若不可能组成可法表，则应输出“error!”。
【输入样例】
3
+M L
M ML M
L M L
【输出样例】
M=1 L=0
2
9、 数的计数
【问题描述】
我们要求找出具有下列性质的数的个数（包含输入的自然数N）：
先输入一个自然数N（N≤1000），然后对自然数按照如下方法进行处理：
② 不作任何处理；
② 在它的左边加上一个自然数，但该自然数不能超过原数（输入的N）的一半；
③ 加上数后，继续按此规则进行处理，直到不能再加自然数为止。
【输入格式】
。
【输出格式】
各所选物品的序号和重量。
【输入样例】
6
【输出样例】
6
满足条件的数为6，16，26，126，36，136（此部分不必输出）
10、集合划分问题
【问题描述】
N个元素的集合 {1，2，3，4，…，N} 可以划分为若干个非空子集。例如：当N=4时，集合 {1，2，3，4} 可以划分为15个不同的非空子集，如下：
{{1}，{2}，{3}，{4}} {{1，2}，{3}，{4}} {{1，3}，{2}，{4}}
{{1，4}，{2}，{3}} {{2，3}，{1}，{4}} {{2，4}，{1}，{3}}
{{3，4}，{1}，{2}} {{1，2}，{3，4}} {{1，3}，{2，4}}
{{1，4}，{2，3}} {{1，2，3}，{4}} {{1，2，4}，{3}}
{{1，3，4}，{2}} {{2，3，4}，{1}} {{1，2，3，4}}
其中：
集合 {{1，2，3，4}} 由1个子集组成；
集合 {{1，2}，{3，4}} {{1，3}，{2，4}} {{1，4}，{2，3}}
{{1，2，3}，{4}} {{1，2，4}，{3}} {{1，3，4}，{2}}
{{2，3，4}，{1}} 由2个子集组成；s(4,2) = 6
集合 {{1，2}，{3}，{4}} {{1，3}，{2}，{4}} {{1，4}，{2}，{3}}
{{2，3}，{1}，{4}} {{2，4}，{1}，{3}} {{3，4}，{1}，{2}}
由3个子集组成； s(4,3)=7
集合 {{1}，{2}，{3}，{4}}由4个子集组成。
给定正整数N和M，计算出N个元素的集合 {1，2，3，4，…，N} 可以划分为多少个不同的由M个非空子集组成的集合。
【输入格式】
一行数据，是元素个数N和非空了集数M。
【输出格式】
计算出的不同的由M个非空子集组成的集合数。
【输入样例】
4 3
【输出样例】
6
【算法分析】
所求的是第二类Stirling数，可推导出如下递归公式：
以s(5,3)为例：
S(5,3)可以由① 往s(4,2)中加一个元素成为s(5,3),共7种；
② 往s(4,3)中加一个元素成为s(5,3),共3*6=18种
则：s(5,3) = 3*s(4,3) + s(4,2) = 25 导出：
s(n,m) = m*s(n-1,m)+s(n-1,m-1)
s(n,n+1) = 0
s(n,0) = 0
s(0,0) = 1
再例：
考虑3个元素的集合，可划分为
① 1个子集的集合：{{1，2，3}}
② 2个子集的集合：{{1，2}，{3}}，{{1，3}，{2}}，{{2，3}，{1}}
③ 3个子集的集合：{{1}，{2}，{3}}
∴F(3,1)=1; F(3,2)=3; F(3,3)=1;
如果要求F(4,2)该怎么办呢？
A.往①里添一个元素{4}，得到{{1，2，3}，{4}}
B.往②里的任意一个子集添一个4，得到
{{1，2，4}，{3}}，{{1，2}，{3，4}}，
{{1，3，4}，{2}}，{{1，3}，{2，4}}，
{{2，3，4}，{1}}，{{2，3}，{1，4}}
∴F(4,2) = F(3,1) + 2*F(3,2) ＝ 1+2*3 ＝ 7
1.
有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2个人大2岁。问第2个人，说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大。显然，这是一个递归问题。要求第5个人的年龄，就必须先知道第4个人的年龄，而第4个人的年龄也不知道，要求第4个人的年龄必须先知道第3个人的年龄，而第3个人的年龄又取决于第2个人的年龄，第2个人的年龄取决于第1个人的年龄。而且每一个人的年龄都比其前1个人的年龄大2。
2.用递归方法求n！
3.用递归方法求斐波那契数列
4.有1*n的一个长方形，用一个1＊1、1＊2、1＊3的骨牌铺满方格。例如当n=3时为1＊3的方格。此时用1＊1，1＊2，1＊3的骨牌铺满方格，共有四种铺法。图4.4.3列出了四种铺法。
5.设s是一个具有n个元素的集合s={a1,a2,…an},现将s集合划分成k个满足下列条件的子集合s1,s2，s3。。。。；
1、si<>空；
2、si∩sj=空；
3、s1∪s2∪s3….
∪sn=s
(1<=i,j<=k,i<>j)
则称s1,s2…sn是集合s的一个划分，它相当于把集合s中的n个元素放入k个无标号的盒子中，使得没有一个盒子为空，试确定n个元素的集合放入k个无标号盒的划分数s(n,k)
6.设有一个背包，可以放入的重量为s。现有n件物品，重量分别为t1
,
t2
,
t3
…
ti
…
tn
，ti
(1≤
i≤n)，均为正整数。从n件物品中挑选若干件，使得放入背包的重量之和正好为s
【输入样例】
【输出样例】
the
number
of
object:5
number:1
weight:1
total
weight=10
number:3
weight:
2
1
6
2
7
5
number:4
weight:7
7.输出n个元素的无重复的全排列。N个元素有n！种不同排列
8.任何一个正整数都可以用2的幂次方表示.例如：137=2^7+2^3+2^0。同时约定次方用括号来表示，即a^b可表示为a(b)。由此可知，137可表示为：2(7)+2(3)+2(0)，进一步：7=2^2+2+2^0
(2^1用2表示)；3=2+2^0；所以最后137可表示为：2(2(2)+2+2(0))+2(2+2(0))+2(0)。又如：1315=2^10+2^8+2^5+2+1；所以1315最后可表示：2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
输入：正整数(n≤20000)
输出：符合约定的n的0，2表示(在表示中不能有空格)
9.。一个正整数的数字的乘积N的定义是：这个整数中非零数字的乘积。例如，整数999的数字乘积为9*9*9，即729。729的数字乘积为7*2*9，即126。126的数字乘积为1*2*6，即12。12的数字乘积为1*2，即2。一个正整数的数字乘积根N是这样得到的：反复取该整数的数字乘积，直到得到一位数字为止。例如，在上面的例子中数字的乘积根是2。
编写一个程序，输入一个正整数（长度不超过200位数字），输出计算其数字乘积根的每一步结果。
10.输入N个字符，然后以倒序输出（用递归实现）
用递归的方法完成下列问题
1.求数组中的最大数
2.1+2+3+...+n
3.求n个整数的积
4.求n个整数的平均值
5.求n个自然数的最大公约数与最小公倍数
6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?
7.已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项.
8.计算xn。 x,n 由键盘输入。将xn写成递归函数计算N允许为正、负数和零 。
这些够简单吧
整个递归的过程是这样的
ack（m,n）=
我就举例ack(3,4)，此时m=3，n=4
1. 此时 m不等于0 ，n不等于0
所以ack(3,4)：=ack(3-1,ack(3,4-1))
^^^^^
ack(3,4-1):=ack(3-1,ack(3,3-1))
^^^^^^^^
ack(3,3-1):=ack(3-1,ack(3,2-1))
^^^^^^
ack(3,2-1):=ack(3-1,ack(3,1-1))
^^^^^
ack(3,1-1):=ack(3-1,1)
就这么算下去，直到M=0，在一步一步回头
在举个简单点的例子吧
求 ack(1,0)
此时 n=0 所以 ack(1,0)：=ack(0,1)
又 ack(0,1)：=2
所以 ack(1,0)：=2；
你慢慢理解吧。
全排列、汉诺塔、爬楼梯、N!、斐波那契、背包问题，这种题很多啊！
1. 有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2个人大2岁。问第2个人，说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大。显然，这是一个递归问题。要求第5个人的年龄，就必须先知道第4个人的年龄，而第4个人的年龄也不知道，要求第4个人的年龄必须先知道第3个人的年龄，而第3个人的年龄又取决于第2个人的年龄，第2个人的年龄取决于第1个人的年龄。而且每一个人的年龄都比其前1个人的年龄大2。
2.用递归方法求n！
3.用递归方法求斐波那契数列
4.有1*n的一个长方形，用一个1＊1、1＊2、1＊3的骨牌铺满方格。例如当n=3时为1＊3的方格。此时用1＊1，1＊2，1＊3的骨牌铺满方格，共有四种铺法。图4.4.3列出了四种铺法。
5.设s是一个具有n个元素的集合s={a1,a2,…an},现将s集合划分成k个满足下列条件的子集合s1,s2，s3。。。。；
1、si<>空；
2、si∩sj=空；
3、s1∪s2∪s3…. ∪sn=s (1<=i,j<=k,i<>j)
则称s1,s2…sn是集合s的一个划分，它相当于把集合s中的n个元素放入k个无标号的盒子中，使得没有一个盒子为空，试确定n个元素的集合放入k个无标号盒的划分数s(n,k)
6.设有一个背包，可以放入的重量为s。现有n件物品，重量分别为t1 , t2 , t3 … ti … tn ，ti (1≤ i≤n)，均为正整数。从n件物品中挑选若干件，使得放入背包的重量之和正好为s
【输入样例】 【输出样例】
the number of object:5 number:1 weight:1
total weight=10 number:3 weight: 2
1 6 2 7 5 number:4 weight:7
7.输出n个元素的无重复的全排列。N个元素有n！种不同排列
8.任何一个正整数都可以用2的幂次方表示.例如：137=2^7+2^3+2^0。同时约定次方用括号来表示，即a^b可表示为a(b)。由此可知，137可表示为：2(7)+2(3)+2(0)，进一步：7=2^2+2+2^0 (2^1用2表示)；3=2+2^0；所以最后137可表示为：2(2(2)+2+2(0))+2(2+2(0))+2(0)。又如：1315=2^10+2^8+2^5+2+1；所以1315最后可表示：2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
输入：正整数(n≤20000)
输出：符合约定的n的0，2表示(在表示中不能有空格)
9.。一个正整数的数字的乘积N的定义是：这个整数中非零数字的乘积。例如，整数999的数字乘积为9*9*9，即729。729的数字乘积为7*2*9，即126。126的数字乘积为1*2*6，即12。12的数字乘积为1*2，即2。一个正整数的数字乘积根N是这样得到的：反复取该整数的数字乘积，直到得到一位数字为止。例如，在上面的例子中数字的乘积根是2。
编写一个程序，输入一个正整数（长度不超过200位数字），输出计算其数字乘积根的每一步结果。
10.输入N个字符，然后以倒序输出（用递归实现）
求经典的递归算法以及案例（可用C#、PHP、JAVA其中一种语言来写）!
Java递归算法的小例子 [日期：2010-03-28]来源：Linux社区 作者：java爱好者1+2+3+...+100的结果：public class Test {
int sum=0;
int a=1;
public void sum()
{
sum+=a;
a+=1;
if(a<=100)
{
sum();//调用自身实现递归
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Test test=new Test();
test.sum();
System.out.println("计算结果："+test.sum+"!");
}
我用C#来写（注意，更多的请直接到我的个人博客，点击， http://www.cnblogs.com/serviceboy/archive/2009/07/19/1526590.html，收看） 【例1】有甲、乙、丙、丁四人，从甲开始到丁，一个比一个大1岁，已知丁10岁，问甲几岁？【分析】这是递归法的一道非常典型的题目——因为我们可以很显然知道：假设要计算甲的年龄，那么必须直到乙的年龄；同样，算乙的必须直到丙的，算丙的必须知道丁的，因为丁已知，自然可以往前推算了。现在假设有一个数学模型（函数）可以计算出他们各自的年龄（方便期间我们给他们编号——甲＝1，乙＝2，丙＝3，丁＝4），那么存在这一个F(X)函数，X表示某人的编号，其规律如下：F(1)=F(2)+1F(2)=F(3)+1F(3)=F(4)+1F(4)=10显然，直到X=4的时候是一个终止值，其余情况下都是返回F(X’)，F(X’’)……F(X’’……’)，且前者总是比后至大1，这也符合了X’和X总是呈现一定函数关系（设想一下，如果不是等差和等比，又怎么可能在一个递归函数中进行计算？要知道，函数本身就是一个公式表示，既然是公式，那么一定是一种函数关系Y=F(X)），此处显然X和X’的关系是X=X’+1。根据规律式，我们可以写出该递归函数：int AgeCal(int id)
{
if(id==4) return 10;
else
return (AgeCal(id+1)+1);
} 【例2】计算n！【分析】虽然这道题目不像例1一样清晰明了告诉你使用“递归”法反推，但是我们有这样一个常识——n！＝(n-1)!*n；(n-1)!=(n-2)!*(n-1)……n=0或1，返回1.显然n与n-1，n-2也是线性的递减数列（等差关系）。其规律如下：F(n)=F(n-1)*nF(n-1)=F(n-2)*(n-1)F(n-2)=F(n-3)*(n-2)……F(1)=1或者F(0)=1(防止别人直接输入0)编写其递归函数，如下：int Fac(int n)
{
if(n==1 || n==0)
{
return 1;
}
else
return Fac(n-1)*n;
} 【例3】求一组整数中的最大(小)值（整数是一个int[]数组，个数未知）。【分析】当数字只有两个的时候，我们可以使用>和
<直接比较；但是当数字超过2个的时候（假设3个），那么我们可以使用一个预订的函数（比如max(1,2)和3进行比较），由于1，2两个数比较的时候已经得到一个最大值，因此在回代到max中又变成了两个数的比较。这样，我们可以发现一个规律：f(1,2,3,4……n)＝f(1,2,3,4……n-1)和n比较f(1,2,3,4……n-1)＝f(1,2,3,4……n-2)和n-1比较……f(1,2,3)=f(1,2)和3比较f(1,2)＝结果（并回代）相应的递归函数如下(c#)：code
int Max(int[]numbers)
{
if(numbers.Length==2)
{
return (numbers[0]>numbers[1]?numbers[0]:numbers[1]);
}
else
{
int[]tempnumbers=new int[numbers.Length-1];
for(int i=0;i
<numbers.length-1;++i)
{
tempnumbers[i]=numbers[i];
}
return (Max(tempnumbers)>numbers[numbers.Length-1]? Max(tempnumbers): numbers[numbers.Length-1]
}
}
</numbers.length-1;++i)
</直接比较；但是当数字超过2个的时候（假设3个），那么我们可以使用一个预订的函数（比如max(1,2)和3进行比较），由于1，2两个数比较的时候已经得到一个最大值，因此在回代到max中又变成了两个数的比较。这样，我们可以发现一个规律：f(1,2,3,4……n)＝f(1,2,3,4……n-1)和n比较f(1,2,3,4……n-1)＝f(1,2,3,4……n-2)和n-1比较……f(1,2,3)=f(1,2)和3比较f(1,2)＝结果（并回代）相应的递归函数如下(c#)：code
什么是语法规则的递归性，请举例说明
同样的语法结构可以层层嵌套，同一条结构规则可以重复使用而不致造成结构上的混乱，借数学的术语来说，这就是语法结构规则的"递归性"。
在句法组合中，递归性有两种表现，一种是从初始结构开始，自始至终重复运用同一条语法规则。例如"计算机/我//喜欢"这个句子是主谓结构，它们的谓语( / 以后的部分)本身又是主谓结构，这里，"主语+谓语"这条语法规则不间断地使用了两次；另外一种表现是，同一条语法规则可以在一个结构上间隔地重复使用。
例如在"我/看///过//他/////写////的///散文"中，第一层使用了"主语+谓语"规则，造成了"我/看过他写的散文"这个主谓结构，第五层又使用了一次"主语+谓语"规则，造成了"他写"这个主谓结构。
递归性，也可相近地理解为层次性或有机性。是机体或系统的共性，是系统得以存在，运作和发展的基本手段。递归性不仅是转换生成语法中的一种语法属性，而且它与任意性、
线性一样是语言的根本性质之一。
语言结构层次和言语生成中相同结构成分的重复或相套。反复地使用构成句法关系的有限的几种句法规则，不断地进行同功能替换，以构成复杂的短语或句子。
在句法组合中，递归性有两种表现，一种是从初始结构开始，自始至终重复运用同一条语法规则。
例如"计算机/我//喜欢"这个句子是主谓结构，它们的谓语(
/
以后的部分)本身又是主谓结构，这里，"主语+谓语"这条语法规则不间断地使用了两次；另外一种表现是，同一条语法规则可以在一个结构上间隔地重复使用。
扩展资料：
递归性是语言的根本性质之一，语言的递归性赋予语言无限的创造性，说话者可以创造出自己从未听过或者讲过的话语。递归性是语言结构层次和言语生成中相同结构成分的重复或相套
。句子能够很好地体现语言的递归性，而通常我们认为，句子是语言中最大的句法单位，所以句法成为人们研究的核心。
人有限的记忆和无限的思维之间的矛盾促生了词的递归性，递归性在所有语言里都有表现，印欧语系的词根，词缀，缩写等即是递归性的表现。递归的最终目的是形成词素，汉语的通常意义的"字"是较完善的递归的结果。
它应称为"词素"较合适，汉语的"字"有时做词用(例"会")，即人们常说的单字词。有时做词素用(例"协会")，汉语"字"由词向词素的过渡是汉语的一场革命。
参考资料来源：搜狗百科——递归性
递归性：反复使用有限的句法规则，构成复杂的词组和句子。
参考资料：邢公畹：《现代汉语教程》，南开大学出版社，1994年，第215面
简单的说就是一句相同语法相同结构的句子可以反复的叠加。
例 从前有座山，山上有座庙，庙里有个老和尚讲故事，讲的是从前有座山，山上有座庙，庙里有个老和尚讲故事…………
将军百战死 壮士十年归
递归性，也可相近地理解为层次性或有机性。是机体或系统的共性，是系统得以存在，运作和发展的基本手段。递归性不仅是转换生成语法中的一种语法属性，而且它与任意性、 线性一样是语言的根本性质之一。
语言结构层次和言语生成中相同结构成分的重复或相套。反复地使用构成句法关系的有限的几种句法规则，不断地进行同功能替换，以构成复杂的短语或句子。
在句法组合中，递归性有两种表现，一种是从初始结构开始，自始至终重复运用同一条语法规则。
例如"计算机/我//喜欢"这个句子是主谓结构，它们的谓语( / 以后的部分)本身又是主谓结构，这里，"主语+谓语"这条语法规则不间断地使用了两次；另外一种表现是，同一条语法规则可以在一个结构上间隔地重复使用。
扩展资料：
递归性是语言的根本性质之一，语言的递归性赋予语言无限的创造性，说话者可以创造出自己从未听过或者讲过的话语。递归性是语言结构层次和言语生成中相同结构成分的重复或相套 。句子能够很好地体现语言的递归性，而通常我们认为，句子是语言中最大的句法单位，所以句法成为人们研究的核心。
人有限的记忆和无限的思维之间的矛盾促生了词的递归性，递归性在所有语言里都有表现，印欧语系的词根，词缀，缩写等即是递归性的表现。递归的最终目的是形成词素，汉语的通常意义的"字"是较完善的递归的结果。
它应称为"词素"较合适，汉语的"字"有时做词用(例"会")，即人们常说的单字词。有时做词素用(例"协会")，汉语"字"由词向词素的过渡是汉语的一场革命。
参考资料来源：百度百科——递归性
能详细点说明下递归吗，最好有现实例子说明
递归是一种重要的编程技术。该方法用于让一个函数从其内部调用其自身。一个示例就是计算阶乘。0 的阶乘被特别地定义为 1。 更大数的阶乘是通过计算 1 * 2 * ...来求得的，每次增加 1，直至达到要计算其阶乘的那个数。
下面的段落是用文字定义的计算阶乘的一个函数。
“如果这个数小于零，则拒绝接收。如果不是一个整数，则将其向下舍入为相邻的整数。如果这个数为 0，则其阶乘为 1。如果这个数大于 0，则将其与相邻较小的数的阶乘相乘。”
要计算任何大于 0 的数的阶乘，至少需要计算一个其他数的阶乘。用来实现这个功能的函数就是已经位于其中的函数；该函数在执行当前的这个数之前，必须调用它本身来计算相邻的较小数的阶乘。这就是一个递归示例。
递归和迭代（循环）是密切相关的 — 能用递归处理的算法也都可以采用迭代，反之亦然。确定的算法通常可以用几种方法实现，您只需选择最自然贴切的方法，或者您觉得用起来最轻松的一种即可。
显然，这样有可能会出现问题。可以很容易地创建一个递归函数，但该函数不能得到一个确定的结果，并且不能达到一个终点。这样的递归将导致计算机执行一个“无限”循环。下面就是一个示例：在计算阶乘的文字描述中遗漏了第一条规则（对负数的处理），并试图计算任何负数的阶乘。这将导致失败，因为按顺序计算 -24 的阶乘时，首先不得不计算 -25 的阶乘；然而这样又不得不计算 -26 的阶乘；如此继续。很明显，这样永远也不会到达一个终止点。
因此在设计递归函数时应特别仔细。如果怀疑其中存在着无限递归的可能，则可以让该函数记录它调用自身的次数。如果该函数调用自身的次数太多，即使您已决定了它应调用多少次，就自动退出。
下面仍然是阶乘函数，这次是用 JScript 代码编写的。
// 计算阶乘的函数。如果传递了
// 无效的数值（例如小于零），
// 将返回 -1，表明发生了错误。若数值有效，
// 把数值转换为最相近的整数，并
// 返回阶乘。
function factorial(aNumber) {
aNumber = Math.floor(aNumber); // 如果这个数不是一个整数，则向下舍入。
if (aNumber < 0) { // 如果这个数小于 0，拒绝接收。
return -1;
}
if (aNumber == 0) { // 如果为 0，则其阶乘为 1。
return 1;
}
else return (aNumber * factorial(aNumber - 1)); // 否则，递归直至完成。
}
在调用一个函数的过程中又出现直接或者间接地调用该函数本身，注意，是该函数本身，就叫做函数的递归（调用）。
比如
int f（int x）
{
int y，z；
z=f(y)；
return（2*z）；
}
递归，简单的说就是自己调用自己，执行递归函数降反复调用其自身，每调用一次就进入新的一层。例如，有函数f如下。
int f(int x)
{
int y;
z=f(y);
return z;
}
这个函数是一个递归函数，但是运行该函数将无休止的调用自身，这当然是不正确的，在此只是给你举个简单的例子而已。为了防止调用无休止的进行，必须加条件判断，满足某种条件后就不再做递归调用，然后逐层返回。在此举例说明递归调用的执行过程。
用递归法计算n!.
long f(int i)
{
if(n<0) printf("input error");return;
else if(i==0||i==1) return 1;
else return i*f(i-1);
}
main()
{
int n;
printf("please input n:\n");
scanf("%d",&n);
printf("%d=%id\n",n,f(n));
}
程序中的f是一个递归函数，如果n<0,n==0或者n==1时将结束函数的执行，否则就递归调用f函数自身。
假设输入3，即求3！。进入f函数i=3,不等于0或1，所以执行i*f(i-1),即
3*f（2）。然后再递归调用f(2),2不等于0或1，所以执行i*f(i-1),即2*f(1).继续调用f(1),此时1==1，结束函数的执行。
所以返回的结果是3*f(2)=3*2*f(1)=3*2*1=6.
希望你可以看懂，我感觉蛮简单的。
什么是递归和迭代？
递归和迭代都是循环的一种。
简单地说，递归是重复调用函数自身实现循环。迭代是函数内某段代码实现循环，而迭代与普通循环的区别是：循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。
递归循环中，遇到满足终止条件的情况时逐层返回来结束。迭代则使用计数器结束循环。当然很多情况都是多种循环混合采用，这要根据具体需求。
递归的例子，比如给定一个整数数组，采用折半查询返回指定值在数组中的索引，假设数组已排序，为方便描述，假设元素都为正数,数组长度为2的整数倍。
折半查询是查询的一种，比遍历所有元素要快很多。
int Find(int *ary,int index,int len,int value){ if(len==1)//最后一个元素 { if (ary[index]==value)return index;//成功查询返回索引 return -1;//失败，返回-1 } //如果长度大于1，进行折半递归查询 int half=len/2; //检查被查值是否大于上半部分最后一个值，如果是则递归查询后半部分 if(value>ary[index+half-1]) return Find(ary,index+half,half,value); //否则递归查询上半部分 return Find(ary,index,half,value);}
迭代经典例子就是实数的累加，比如计算1-100所有实数的和。
int v=1;for(i=2;i<=100;i++){ v=v+i;}
(4)递归式求解的三种方法
步骤如下：
比如我们求解，递归式T(n) = 2T(n/2)+n，
利用递归树方法求算法复杂度，其实是提供了一个好的猜测，简单而直观。在递归树中，每一个结点表示一个单一问题的代价，子问题对应某次递归函数调用。我们将树中每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次的递归调用总代价。
递归树最适合用来生成好的猜测，然后可用代入法来验证猜测是否正确。当使用递归树来生成好的猜测时，常常要忍受一点儿“不精确”，因为关注的是如何寻找解的一个上界。
根据上式我们建立递归式T(n) = 3T(n / 4) + cn^2，建立下列递归树模型
在递归树中，每一个结点都代表一个子代价，每层的代价是该层所有子代价的总和，总问题的代价就是所有层的代价总和。所以，我们利用递归树求解代价，只要知道每一层的代价和层数即可。
这些，都需要直观的找出规律，以上图为例，当递归调用到叶子T(1)时所用到的递归次数就是整棵递归树的深度。我们从图中可以得到第i层的结点的代价为n/(4 i)，当n/(4 i)=1即i = log4(n)时，递归到达了叶子，故整棵递归树的深度为log4(n)。总代价是所有层代价的总和，T(n)=cn 2+3/16*c*n 2+···结果为O(n^2)。计算过程详见算法导论。用到了一些几何级数相关的知识略微放大上界。
注意到递归树并非都是这样：每一层的结点都是相同的结构！我们在构造递归树以及计算代价的时候要特别注意。
例子如下
易语言递归算法怎么用，求高手给举个简单点的例子
递归，简单说是子程序自己调用自己。
例子：
.版本 2
.子程序 左右查找
.参数 左边值, 整数型
.参数 右边值, 整数型
.参数 查找数组, , 数组
.参数 ww, , 参考 可空 数组
.局部变量 i, 整数型
.局部变量 j, 整数型
.局部变量 中间值, 整数型
.如果真 (左边值 ≥ 右边值)
返回 ()
.如果真结束
i ＝ 左边值
j ＝ 右边值
.判断循环首 (j ≠ i)
.判断循环首 (查找数组 [左边值] ≤ 查找数组 [j] 且 i ＜ j)
j ＝ j － 1
.判断循环尾 ()
.判断循环首 (查找数组 [左边值] ≥ 查找数组 [i] 且 i ＜ j)
i ＝ i ＋ 1
.判断循环尾 ()
.如果真 (i ＜ j)
中间值 ＝ 查找数组 [j]
查找数组 [j] ＝ 查找数组 [i]
查找数组 [i] ＝ 中间值
.如果真结束
.判断循环尾 ()
中间值 ＝ 查找数组 [左边值]
查找数组 [左边值] ＝ 查找数组 [i]
查找数组 [i] ＝ 中间值
左右查找 (左边值, i － 1, 查找数组, ) ' 继续处理左边的，这里是个递归的过程
左右查找 (i ＋ 1, 右边值, 查找数组, ) ' 继续处理右边的，这里是个递归的过程
ww ＝ 查找数组
' 以上是快速排序的代码实现，核心所在是递归的过程。