递归算法_asp.net吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：16,698贴子：
递归算法收藏
1.1.2.3.5 求第30位数 c=0 a=1 b=1 用for循环套for循环那个怎么写来着 大神告诉告诉想不起来了
福利不只是穿多穿少，还要有迷人的微笑!
static void Main(string[] args)
int c = 0;
int a = 1;
int b = 1;
for (int i = 0; i & 30; i++)
int tempc =
int tempa =
int tempb =
Console.WriteLine(b);
典型的递归。getNum（n）{if（n==1 || n==2）{return 1;}else{return getNum（n-1）+getNum（n-2）;}}
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或梦想破碎是没有声音的，它只是缓慢又沉默地离开了。 by 苏更生
题图：递归
在数学与计算机科学中，递归是指在函数的定义中使用函数自身的方法。
递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
递归算法解决问题的特点：
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。在实际编程中尤其要注意栈溢出问题。
借助递归方法，我们可以把一个相对复杂的问题转化为一个与原问题相似的规模较小的问题来求解，递归方法只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。但在带来便捷的同时，也会有一些缺点，也即：通常用递归方法的运行效率不高。
递归算法实例
1.Fibonacci函数
讲到递归，我们最先接触到的一个实例便是斐波那契数列。
斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
特别指出：第0项是0，第1项是第一个1。
这个数列从第二项开始，每一项都等于前两项之和。
斐波那契数列递归法实现：
int Fib(int n)
return -1;
if(n == 1|| n == 2)
return Fib(n-1)+Fib(n-2);
123456789101112
int Fib(int n){&&&&if(n&1)&&&&{&&&&&&&&return -1;&&&&}&&&&if(n == 1|| n == 2)&&&&{&&&&&&&&return 1;&&&&}&&&&return Fib(n-1)+Fib(n-2);}
2.汉诺塔问题
汉诺塔示意图
汉诺塔是根据一个传说形成的数学问题：
有三根杆子A，B，C。A杆上有N个(N&1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：
每次只能移动一个圆盘；
大盘不能叠在小盘上面。
提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。
问：如何移？最少要移动多少次？
最早发明这个问题的人是法国数学家爱德华·卢卡斯。
传说印度某间寺院有三根柱子，上串64个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题(Tower of Brahma puzzle)。但不知道是卢卡斯自创的这个传说，还是他受他人启发。
若传说属实，僧侣们需要264 ? 1步才能完成这个任务；若他们每秒可完成一个盘子的移动，就需要5849亿年才能完成。整个宇宙现在也不过137亿年。
这个传说有若干变体：寺院换成修道院、僧侣换成修士等等。寺院的地点众说纷纭，其中一说是位于越南的河内，所以被命名为“河内塔”。另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定。
佛教中确实有“浮屠”（塔）这种建筑；有些浮屠亦遵守上述规则而建。“河内塔”一名可能是由中南半岛在殖民时期传入欧洲的。
以下是汉诺塔问题的递归求解实现：
: main.cpp
* Date & Time : Sat Oct 06 21:01:55 2012
#include &iostream&
#include &cstdio&
void hannoi (int n, char from, char buffer, char to)
if (n == 1)
cout && "Move disk " && n && " from " && from && " to " && to &&
hannoi (n-1, from, to, buffer);
cout && "Move disk " && n && " from " && from && " to " && to &&
hannoi (n-1, buffer, from, to);
int main()
hannoi (n, 'A', 'B', 'C');
12345678910111213141516171819202122232425262728293031323334
/* * Project&&&& : hannoi * File&&&&&&&&: main.cpp * Author&&&&&&: iCoding * * Date & Time : Sat Oct 06 21:01:55 2012
* */using namespace std;#include &iostream&#include &cstdio& void hannoi (int n, char from, char buffer, char to){&&&&if (n == 1)&&&&{&&&&&&&&cout && "Move disk " && n && " from " && from && " to " && to && endl; &&&&}&&&&else&&&&{&&&&&&&&hannoi (n-1, from, to, buffer);&&&&&&&&cout && "Move disk " && n && " from " && from && " to " && to && endl;&&&&&&&&hannoi (n-1, buffer, from, to);&&&&}} int main(){&&&&int n;&&&&cin && n;&&&&hannoi (n, 'A', 'B', 'C');&&&&return 0;}
更详细解析请参考：
3.二叉树遍历
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
一颗简单的二叉树
二叉树的遍历分为三种：前(先)序、中序、后序遍历。
设L、D、R分别表示二叉树的左子树、根结点和遍历右子树，则先(根)序遍历二叉树的顺序是DLR，中(根)序遍历二叉树的顺序是LDR，后(根)序遍历二叉树的顺序是LRD。还有按层遍历二叉树。这些方法的时间复杂度都是O(n)，n为结点个数。
假设我们有一个包含值的value和指向两个子结点的left和right的树结点结构。我们可以写出这样的过程：
先序遍历(递归实现)：
visit(node)
print node.value
if node.left
!= null then visit(node.left)
if node.right != null then visit(node.right)
visit(node)&&&&print node.value&&&&if node.left&&!= null then visit(node.left)&&&&if node.right != null then visit(node.right)
中序遍历(递归实现)：
visit(node)
if node.left
!= null then visit(node.left)
print node.value
if node.right != null then visit(node.right)
visit(node)&&&&if node.left&&!= null then visit(node.left)&&&&print node.value&&&&if node.right != null then visit(node.right)
后序遍历(递归实现)：
visit(node)
if node.left
!= null then visit(node.left)
if node.right != null then visit(node.right)
print node.value
visit(node)&&&&if node.left&&!= null then visit(node.left)&&&&if node.right != null then visit(node.right)&&&&print node.value
4.字符串全排列
写一个函数返回一个串的所有排列。
对于一个长度为n的串，它的全排列共有A(n, n)=n!种。这个问题也是一个递归的问题， 不过我们可以用不同的思路去理解它。为了方便讲解，假设我们要考察的串是”abc”， 递归函数名叫permu。
我们可以把串“abc”中的第0个字符a取出来，然后递归调用permu计算剩余的串“bc” 的排列，得到{bc, cb}。然后再将字符a插入这两个串中的任何一个空位(插空法)， 得到最终所有的排列。比如，a插入串bc的所有(3个)空位，得到{abc,bac,bca}。 递归的终止条件是什么呢？当一个串为空，就无法再取出其中的第0个字符了， 所以此时返回一个空的排列。代码如下：
typedef vector&string&
vs permu(string s){
if(s == ""){
result.push_back("");
string c = s.substr(0, 1);
vs res = permu(s.substr(1));
for(int i=0; i&res.size(); ++i){
string t = res[i];
for(int j=0; j&=t.length(); ++j){
string u =
u.insert(j, c);
result.push_back(u);
//调用result的拷贝构造函数，返回它的一份copy，然后这个局部变量销毁(与基本类型一样)
1234567891011121314151617181920
typedef vector&string& vs; vs permu(string s){&&&&vs result;&&&&if(s == ""){&&&&&&&&result.push_back("");&&&&&&&&return result;&&&&}&&&&string c = s.substr(0, 1);&&&&vs res = permu(s.substr(1));&&&&for(int i=0; i&res.size(); ++i){&&&&&&&&string t = res[i];&&&&&&&&for(int j=0; j&=t.length(); ++j){&&&&&&&&&&&&string u = t;&&&&&&&&&&&&u.insert(j, c);&&&&&&&&&&&&result.push_back(u);&&&&&&&&}&&&&}&&&&return result; //调用result的拷贝构造函数，返回它的一份copy，然后这个局部变量销毁(与基本类型一样)}
我们还可以用另一种思路来递归解这个问题。还是针对串“abc”， 我依次取出这个串中的每个字符，然后调用permu去计算剩余串的排列。 然后只需要把取出的字符加到剩余串排列的每个字符前即可。对于这个例子， 程序先取出a，然后计算剩余串的排列得到{bc,cb}，然后把a加到它们的前面，得到 {abc,acb}；接着取出b，计算剩余串的排列得到{ac,ca}，然后把b加到它们前面， 得到{bac,bca}；后面的同理。最后就可以得到“abc”的全序列。代码如下：
vs permu1(string s){
if(s == ""){
result.push_back("");
for(int i=0; i&s.length(); ++i){
string c = s.substr(i, 1);
string t =
vs res = permu1(t.erase(i, 1));
for(int j=0; j&res.size(); ++j){
result.push_back(c + res[j]);
12345678910111213141516
vs permu1(string s){&&&&vs result;&&&&if(s == ""){&&&&&&&&result.push_back("");&&&&&&&&return result;&&&&}&&&&for(int i=0; i&s.length(); ++i){&&&&&&&&string c = s.substr(i, 1);&&&&&&&&string t = s;&&&&&&&&vs res = permu1(t.erase(i, 1));&&&&&&&&for(int j=0; j&res.size(); ++j){&&&&&&&&&&&&result.push_back(c + res[j]);&&&&&&&&}&&&&}&&&&return result;}
更详细讲解请参考：
5.八皇后问题
经典的八皇后问题，即在一个8*8的棋盘上放8个皇后，使得这8个皇后无法互相攻击( 任意2个皇后不能处于同一行，同一列或是对角线上)，输出所有可能的摆放情况。
8皇后是个经典的问题，如果使用暴力法，每个格子都去考虑放皇后与否，一共有264 种可能。所以暴力法并不是个好办法。由于皇后们是不能放在同一行的， 所以我们可以去掉“行”这个因素，即我第1次考虑把皇后放在第1行的某个位置， 第2次放的时候就不用去放在第一行了，因为这样放皇后间是可以互相攻击的。 第2次我就考虑把皇后放在第2行的某个位置，第3次我考虑把皇后放在第3行的某个位置， 这样依次去递归。每计算1行，递归一次，每次递归里面考虑8列， 即对每一行皇后有8个可能的位置可以放。找到一个与前面行的皇后都不会互相攻击的位置， 然后再递归进入下一行。找到一组可行解即可输出，然后程序回溯去找下一组可靠解。
我们用一个一维数组来表示相应行对应的列，比如c[i]=j表示， 第i行的皇后放在第j列。如果当前行是r，皇后放在哪一列呢？c[r]列。 一共有8列，所以我们要让c[r]依次取第0列，第1列，第2列……一直到第7列， 每取一次我们就去考虑，皇后放的位置会不会和前面已经放了的皇后有冲突。 怎样是有冲突呢？同行，同列，对角线。由于已经不会同行了，所以不用考虑这一点。 同列：c[r]==c[j]; 同对角线有两种可能，即主对角线方向和副对角线方向。 主对角线方向满足，行之差等于列之差：r-j==c[r]-c[j]; 副对角线方向满足， 行之差等于列之差的相反数：r-j==c[j]-c[r]。 只有满足了当前皇后和前面所有的皇后都不会互相攻击的时候，才能进入下一级递归。
代码如下：
#include &iostream&
int c[20], n=8, cnt=0;
void print(){
for(int i=0; i&n; ++i){
for(int j=0; j&n; ++j){
if(j == c[i]) cout&&"1 ";
else cout&&"0 ";
void search(int r){
if(r == n){
for(int i=0; i&n; ++i){
int ok = 1;
for(int j=0; j&r; ++j)
if(c[r]==c[j] || r-j==c[r]-c[j] || r-j==c[j]-c[r]){
if(ok) search(r+1);
int main(){
search(0);
cout&&cnt&&
123456789101112131415161718192021222324252627282930313233343536
#include &iostream&using namespace std; int c[20], n=8, cnt=0;void print(){&&&&for(int i=0; i&n; ++i){&&&&&&&&for(int j=0; j&n; ++j){&&&&&&&&&&&&if(j == c[i]) cout&&"1 ";&&&&&&&&&&&&else cout&&"0 ";&&&&&&&&}&&&&&&&&cout&&endl;&&&&}&&&&cout&&endl;}void search(int r){&&&&if(r == n){&&&&&&&&print();&&&&&&&&++cnt;&&&&&&&&return;&&&&}&&&&for(int i=0; i&n; ++i){&&&&&&&&c[r] = i;&&&&&&&&int ok = 1;&&&&&&&&for(int j=0; j&r; ++j)&&&&&&&&&&&&if(c[r]==c[j] || r-j==c[r]-c[j] || r-j==c[j]-c[r]){&&&&&&&&&&&&&&&&ok = 0;&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&}&&&&&&&&if(ok) search(r+1);&&&&}}int main(){&&&&search(0);&&&&cout&&cnt&&endl;&&&&return 0;}
or分享 (0)二次元同好交流新大陆
扫码下载App
温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
假设数组含有n个元素，则提取数组中的每一个元素做一次头元素，然后全排列除数组中除第一个元素之外的所有元素，这样就达到了对数组中所有元素进行全排列的得目的。把数组无限缩小（不断调用函数自身）反复运用上诉思想，则实现了所谓的全排列。注意：一次循环过后，数组又返回原来的样子（这是相对的，注意理解，可以以当n为3时进行跟踪程序，这样就很容易理解了）还有对于在一个for循环内，每一次循环中index和num的值总是相同的，不会发生变化，注意理解。#include&iostream&const int LENGTH=5;void permutation(int values[], int index, int num){ int i = 0; if(num == 0)//显示输出 {
for(i=0; i&LENGTH;++i)
cout&&values[i]&&" ";
} for(i=0; i& i++) {
swap(values[index+i], values[index]);//第index个整数和第index+i个数字交换，进行排列
permutation(values, index+1, num-1);//对从index+1到数组最末端的元素进行全排列
swap(values[index], values[index+i]);//for循环中第一条语句的逆操作，其目的是使数组倒回原来的样子，在本例中为8，2，10，0，6
//这样做的目的是使排列不会产生重复的结果。 } }int main(){ int values[]={8,2,10,0,6};
permutation(values,0,5); cout&&endl&& for(int i=0;i&5;++i) {
cout&&values[i]&&' '; } cout&&endl&&
return 0;}
阅读(7328)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_082070',
blogTitle:'全排列递归算法',
blogAbstract:'本题型为全排列，其解题思路是：假设数组含有n个元素，则提取数组中的每一个元素做一次头元素，然后全排列除数组中除第一个元素之外的所有元素，这样就达到了对数组中所有元素进行全排列的得目的。把数组无限缩小（不断调用函数自身）反复运用上诉思想，则实现了所谓的全排列。注意：一次循环过后，数组又返回原来的样子（这是相对的，注意理解，可以以当n为3时进行跟踪程序，这样就很容易理解了）还有对于在一个for循环内，每一次循环中index和num的值总是相同的，不会发生变化，注意理解。#include&iostream&',
blogTag:'递归算法,分而治之算法',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:9,
publishTime:7,
permalink:'blog/static/',
commentCount:1,
mainCommentCount:1,
recommendCount:0,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'',
hmcon:'1',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}C#递归算法_百度知道
C#递归算法
static void Main(string[] args)
&#47.+100的值
if (i == 0) return 0. 计算1+2+3+4+;
public static int Process2(int i)
/计算1+2+3+4+;
C&#47..ReadLine();/
}比如当i=3时..1.WriteLine(Process2(100)).;如何执行的
return Process2(i - 1) + i
提问者采纳
ublic static int Sum(int n){
return 1，Process2(1)=1+Process2(0).得到3+2+Process2(1);
}}比如当i=3时,Process2(2)=2+Process2(1)，所以最后的结果就是3+2+1+0;
return n+Sum(n-1)，得到3+2+1+Process2(0)，由函数可得Process2(0)=0，得到3+Process2(2)
提问者评价
谢谢，现在这个搞懂了！
其他类似问题
为您推荐：
其他3条回答
return Process2()public int i=3;public static int Process2(){if (i == 0) public int sum=0;i--;sum+=i
这就是递归的用法啊如：i=3时，return Process2(2)+3,而Process2(2)=Process2(1)+2,Process2(1)=Process2(0)+1;所以当i=3时，返回的值为：3+2+1+0啦
你这不是做得挺好的吗？你这没错啊
递归算法的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁