一、何为递归
①在C语言中,递归就是函数自己调用自己。递是指递推,归是指回归。
②递归的思想:将复杂的问题简单化。
③递推的两个必要条件。
a: 递归存在限制条件,当满足限制条件时,递归便不再继续
b:每一次递归都要越来越接近限制条件
/*用递归的方式求n! (n>=0)*/
int Fact(int n)
{
if (n <= 1)/*限制条件*/
{
return 1;
}
else
{
return n * Fact(n - 1);/*容易发现每一次递归都越来越接近限制条件*/
}
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fact(n);
printf("%d的阶乘是%d\n", n, ret);
return 0;
}
④递归的层次不能太深。
每一次递归都是一次函数调用,需要向内存的栈区申请空间(这块空间被称为运行时堆栈,也叫函数栈帧),存放函数调用期间各种局部变量的值,当递归的次数足够多时,就会将栈区的空间占满,出现栈溢出(statck overflow)
⑤递归的思想(大事化小)
把⼀个⼤型复杂问题层层转化为⼀个与原问题相似,但规模较⼩的⼦问题来求解;直到⼦问题不能再被拆分,递归就结束了
二、递归的示例
/*输⼊⼀个正整数m,按照顺序打印正整数的每⼀位。
⽐如:
输⼊:1234 输出:1 2 3 4*/
/*方法1*/
void print(int m)
{
/*若m是一位数,直接打印m */
if (m <=9)
{
printf("%d ", m);
}
else/*如果m不是一位数,则先按顺序打印个位数之外的每一位,最后打印个位上的数*/
{
print(m / 10);
printf("%d ", m % 10);
}
}
/*方法一中的print函数稍稍有些繁琐,下面通过方法二将print函数进行简化*/
/*方法二: */
void print(int m)
{
/*如果m不是一位数,则先按顺序打印个位数之外的每一位,再打印个位上的数
如果m是一位数,则直接打印m
*/
if (m > 9)/*递归的限制条件*/
{
print(m / 10);/*容易发现每一次递归都越来越接近限制条件*/
}
printf("%d ", m % 10);
}
int main()
{
int m = 0;
scanf("%d", &m);
print(m);
return 0;
}
三、不适合用递归的示例
(有些问题如果使用递归的方法求解,可能会由于递归的层次太深,导致计算量太大,使得程序在运行时需要耗费很长的时间才能得出最终的结果。这类问题使用递归的方法效率就很低)
示例如下:
那么像这类不适合用递归的方式求解的问题,该如何解决呢?
可以采用迭代的方式(通常指循环) 循环一定是迭代,但迭代不一定是循环
方法1:
int F(int n)
{
int a = 1, b = 1, c = 0;
if (n <= 2)
{
return 1;
}
else
{
for (int i = 1; i <= n - 2; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = F(n);
printf("%d\n", ret);
return 0;
}
方法1中的F(n)函数稍稍有些复杂,下面用通过另外一种方法对F(n)函数进行简化。
int F(int n)
{
int a = 1, b = 1, c = 1;
/*n=3时循环一次
n=4时循环两次
依此类推
*/
while (n > 2)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}