一、何为递归

①在C语言中，递归就是函数自己调用自己。递是指递推，归是指回归。

②递归的思想：将复杂的问题简单化。

③递推的两个必要条件。

a: 递归存在限制条件,当满足限制条件时，递归便不再继续

b：每一次递归都要越来越接近限制条件

<code>/*用递归的方式求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：

<code>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;

}

四、递归与迭代该怎么选呢

a. 如果一个问题用递归的方式求解非常简单，而且没有太大的问题，就可以选择用递归的方式

b. 但如果用递归的方式可能导致栈溢出，或者由于递归的层次太深，导致计算量太大时，就选择迭代的方式