递归

递归你知道吗？递归就是函数自己调用自己。这里有4道题目，一起来挑战一下吧！有需要的同学，可以收藏下哟。

递归

• 4.二叉树遍历
  • 题目：已知一棵二叉树（1为根），分别求它的先序编历，中序编历、后序编历（结点数N<=100）
  • 输入输出描述： 输入： 第一行树结点个数，从第二行开始，每行三个数，第一个数是结点，第二个数是左孩子，第三个数是右孩子，0表示不存在左孩子或者右孩子。 输出： 第一行先序编历，第二行中序编历，第三行后序编历，数与数之间有一个空格
  • 样例： 输入： 5 1 2 3 2 4 5 3 0 0 4 0 0 5 0 0 输出： 1 2 4 5 3 4 2 5 1 3 4 5 2 3 1
  • 思路：定义三个void函数，分别输出先序、中序、后序遍历。
  • 代码演示： #include <bits/stdc++.h> using namespace std; int a[101][2]; void dfs1(int u) { if (u == 0) { return ; } printf("%d ",u); dfs1(a[u][0]); //利用递归 dfs1(a[u][1]); } void dfs2(int u) { if (u == 0) { return ; } dfs2(a[u][0]); //利用递归 printf("%d ",u); dfs2(a[u][1]); } void dfs3(int u) { if (u == 0) { return ; } dfs3(a[u][0]); //利用递归 dfs3(a[u][1]); printf("%d ",u); } int main() { int n; scanf("%d",&n); for(int i = 1;i <= n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); a[x][0] = y; a[x][1] = z; //0表示左孩子，1表示右孩子 } dfs1(1); printf("\n"); dfs2(1); printf("\n"); dfs3(1); return 0; }
• 3.组合输出
  • 题目：输入正整数N，输出由1到N这N个数取出K个（1<=N<=10,1<=k<=N）的所有组合，每行一个组合，数与数之间有一个空格，从左到右按升序，两个组合中，第一个数小的优先输入，第一个数相同，比较第二个数，后面以此类推。
  • 输入输出描述：输入正整数N和K，输出所有组合。
  • 样例： 输入： 3 2 输出： 1 2 1 3 2 3
  • 思路：用递归解决。当现在的数大于n，输出，定义数组，把现在的数赋给数组。
  • 代码演示： #include <bits/stdc++.h> using namespace std; int a[11]; int n,k; void dfs(int cnt,int now) { if (now == n + 1) { if (cnt == k) { for(int i=0;i<k;i++) { printf("%d ",a[i]); } printf("\n"); } return ; } a[cnt] = now; dfs(cnt+1,now+1); dfs(cnt,now+1); } int main() { scanf("%d%d",&n,&k); dfs(0,1); return 0; }
• 2.递归求斐波那契数
  • 题目： 第1个斐波那契数是1 第2个斐波那契数是1 第3个斐波那契数是2 后面每一个斐波那契数都等于前两个斐波那契数相加。 求第n个斐波那契数
  • 输入输出描述：输入一个整数n，n≤30。输出一个整数，表示答案。
  • 样例：输入：6 输出：8
  • 思路：一样，可以转换成f(n-1)+f(n-2)，当n是1或2时，return 1.
  • 代码演示： #include <bits/stdc++.h> using namespace std; int f(int n) { if (n <= 2) return 1; else return f(n - 1) + f(n - 2); //递归 } int main() { int n; cin >> n; cout << f(n); return 0; }
• 1.n阶乘
  • 题目：用递归算法，输出n的阶乘 。
  • 输入输出描述： 输入：输入一个整数n，n≤10 输出：输出一个整数,答案在int范围内
  • 样例：输入：3 输出：6
  • 思路：用for循环大家都会，递归怎么做呢？可以转换成n×(n-1)！(感叹号是阶乘的意思)，直到最后是1的时候 return 1 就可以了。
  • 代码演示： #include <bits/stdc++.h> using namespace std; int f(int n) { if (n == 1) return 1; else return n * f(n - 1); //递归 } //递归就是函数自己调用自己 int main() { int n; cin >> n; cout << f(n); return 0; }