「递回只应天上有，凡人该当用回圈。」 　　是如此一句浪漫的话语，激起高中几位朋友追逐递回最终奥义的热情。犹记得当年， 趁着夕阳将影子拉至最长的短暂片刻，在校园操场我们共同用黑影在草地上画出了象徵青 春与冒险的字样：Recursion。（故事後来写成小说，详见维基 http://0rz.tw/0a4Yf） 　　再说下去就太拖戏了。 　　　　　　　　　　　　　　　　　　－ 　　首先先来谈函式，一个特定的函式用来解决特定的问题。像是以下函数的功能即为读 入两个整数 a 和 b，将两者相加後再减去两者两减，并回传给呼叫他的人： int fun1(int a,int b){ return (a+b)-(a-b); } main(){ int c; c=fun1(38,19); } 结束後 c 的值为 38。当然啦，函数非常的有用，再多举几个请自行判断其用途： int fun2(int a,int b){ int fun3(int x){ void fun4(int num){ if(a>b) if(x>0) printf("Hello, I'm "); return a; return x; printf("%d ",num); return b; return -x; printf("years old."); } } } 　　　　　　　　　　　　　　　　　　－ 　　递回则是在函数尚未结束之前，又在函数内部呼叫了函数自己。原则上递回用来解决 结构类似的问题，许多情况下也可以看作把一个大问题切割成许多小问题并分别解决。 　　直接看例子帮助了解，拿最简单的来讲，要计算 1+2+3+...+n 的值。 方法一（回圈）： #include <cstdio> #include <cstdlib> main(){ int n,sum,i; scanf("%d",&n); sum=0; for(i=1;i<=n;i++) sum+=i; printf("sum=%d\n",sum); system("PAUSE"); } 方法二（递回）： 　　先来观察我们的问题，要求的东西是从 1 累加到 n 的值。因此可以定义一个函式， 用来计算我们要的答案（即 1+2+...+n），而影响这个函式的是究竟要加到多少才停止， 也就是输入中的 n，於是我们传入函数的参数为 n。 int calc(int n){ //不会写... } 再来，考虑要如何解决 1+2+...+n 的问题。 { 1+2+3+...+(n-1)+n } = { 1+2+3+...+(n-1) } + n 原谅我的表达能力。我的意思是，要求 1 加到 n，我们可以先算出 1 加到 n-1 的 值，最後再多加一个 n 就是答案了，因此函式为： int calc(int n){ int ans; //先用 calc(n-1) 算出 1+...+n-1，最後再加 n ans=calc(n-1)+n; //在这里你可以假设 calc(n-1) 会正确算出结果 return ans; //回传答案 } 还没结束，得再继续努力。试试看计算 1+2+3 会发生什麽事： calc(3) = calc(2)+3 = calc(1)+2+3 = calc(0)+1+2+3 = calc(-1)+1+2+3 = ... 递回不会结束！这里带出了递回非常重要的一件事情，那就是结束条件。加总问题的 结束条件其实很容易，即当 n = 1 时代表 1+...+1 答案为 1，这样递回就完成了。 #include <cstdio> #include <cstdlib> int calc(int n){ if(n==1) return 1; return calc(n-1)+n; } main(){ int n,sum; scanf("%d",&n); printf("sum=%d\n",calc(n)); system("PAUSE"); } 故事告诉我们，递回有两件非常重要的事情： ‧递回式 ：本例中 f(n) = f(n-1) + n ‧结束条件：本例中 f(n) = 1，当 n = 1 事实上，只要能写出递回式和结束条件，要写好递回函数就不是件困难的事情。国中 或高中时有个有名的数列叫 Fibonacci 数列，接下来以此为例： ‧递回式 ：fib(n) = fib(n-1) + fib(n-2) ‧结束条件：fib(1) = fib(2) = 1 写完两大要素後，马上就能完成相对应的 code（请别输入太大的 n）： #include <cstdio> #include <cstdlib> int fib(int n){ if(n==1 || n==2) //这里是结束条件 return 1; return fib(n-1)+fib(n-2); //这里是递回式 } main(){ int n; scanf("%d",&n); printf("The n-th Fibonacci number is %d\n",fib(n)); system("PAUSE"); } 甚至求组合数也是轻而易举： ‧递回式 ：C(n,k) = C(n-1,k) + C(n-1,k-1) ‧结束条件：C(n,k) = 0，当 n < k C(1,k) = 1 C(n,0) = 1 #include <cstdio> #include <cstdlib> int Combi(int n,int k){ if(n<k) return 0; if(n==1 || k==0) return 1; return Combi(n-1,k)+Combi(n-1,k-1); } main(){ int n,k; scanf("%d %d",&n,&k); printf("C(%d,%d) = %d\n",n,k,Combi(n,k)); system("PAUSE"); } 　　　　　　　　　　　　　　　　　　－ 最後再强调一次，递回通常用来解决结构相似的问题。而递回确实是比较不容易了解 的概念，多试几次，并拿不同的东西写写看（例如求阶乘）或许就能够体会了。 实际练习一题不简单但也不会太难的问题。答案下一篇再讲，休息一下。 Question：将一正 n 边形分割成 n-2 个三角形，有几种分割方法？ Sample Input Sample Output 4 2 分割方法见图： 5 5 6 14 http://0rz.tw/cb4TF 7 42 8 132 9 429 10 ???? -- 没有仔细校稿也没有套色，请多见谅。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.242.109