沈阳市和平区网站建设百度旧版本

一、递归定义

定义：递归是一种解决问题的一种方法（函数的应用），即函数自己调用自己。
补充知识：
迭代：通常是使用循环结构。

二、递归思想

把一个复杂问题层层转化为一个个与原问题相同的小问题。递即递推，归即回归。

三、递归的限制条件及注意事项

限制条件：

1. 存在限制条件，即满足一定的条件就不再递归了。
2. 每递归一次，就逐步接近限制条件。

注意事项：
1.有重复运算的情况下，不要使用递归，而是使用迭代。
2.递归的深度不能太深。

四、递归的例子

1. 输入一个整数，然后按顺序打印

#include <stdio.h>
void Print(int num)
{if (num < 9){printf("%d ", num);}else{Print(num / 10);printf("%d ", num % 10);}
}
int main()
{int input = 0;//输入整数while (scanf("%d", &input) != EOF){Print(input);printf("\n");}return 0;
}

2.实现n的阶乘（使用递归）

#include <stdio.h>
int Fact(int n)
{if (0 == n){return 1;}else{return n * Fact(n - 1);}}
int main()
{int n = 0;while (scanf("%d", &n) != EOF){int ret = Fact(n);printf("%d\n", ret);}return 0;
}

使用for语句实现n的阶乘（使用迭代）

int main()
{int n = 0;while (scanf("%d", &n) != EOF){int ret = 1;if (0 == n){printf("%d", ret);}else{for (int i = 1; i <= n; i++){ret *= i;}printf("%d\n", ret);}}return 0;
}

五、跳台阶问题

（1）爬楼梯，小明一次可以爬一个，两个或三个台阶。计算小明爬上楼梯的方法。
使用递归方法：

int climpstairs(int n)
{if (n <= 2){return n;}else if (3 == n){return 4;}//4+2+1elsereturn climpstairs(n - 1) + climpstairs(n - 2) + climpstairs(n - 3);
}
int main()
{int n = 0;printf("请输入台阶数:");scanf("%d", &n);int ret =climpstairs(n);printf("小明爬上台阶n的方法有%d种\n", ret);return 0;
}

使用非递归方法：

int climpstairs(int n)
{if (n <= 2){return n;}int arr[100];arr[1] = 1;arr[2] = 2;arr[3] = 4;for (int i = 4; i <=n; i++){arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];}return arr[n];
}int main()
{int n = 0;printf("请输入台阶数:");scanf("%d", &n);int ret =climpstairs(n);printf("小明爬上台阶n的方法有%d种\n", ret);return 0;
}

（2）小明一次可以爬一个，两个，三个或四个台阶。计算他爬台阶n有多少种方法。

int climpstairs(int n)
{if (n <= 2){return n;}else if (3 == n){return 4;}else if (4 == n){//4+2+1+1return 8;}//n=5  8+4+2+1elsereturn climpstairs(n - 1) + climpstairs(n - 2) + climpstairs(n - 3)+climpstairs(n-4);
}
int main()
{int n = 0;printf("请输入台阶数:");scanf("%d", &n);int ret = climpstairs(n);printf("小明爬上台阶n的方法有%d种\n", ret);return 0;
}

使用非递归方法。

int climpstairs(int n)
{if (n <= 2){return n;}int arr[100] = { 0 };arr[1] = 1;//1arr[2] = 2;//2arr[3] = 4;//2+1+1arr[4] = 8;//4+2+1+1for (int i = 5; i <= n; i++){arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3] + arr[i - 4];}return arr[n];
}
int main()
{int n = 0;printf("请输入小明要爬的台阶数：", n);scanf("%d", &n);int ret = climpstairs(n);printf("小明爬上台阶n的方法有%d种\n", ret);return 0;
}