C语言 函数的递归调用

C语言允许函数递归调用。递归就是一个函数的函数体内直接或间接地出现了调用自身的语句。这样的函数称为递归函数。

递归调用可以使递归函数使用不同参数的值重复执行。某些情况下，递归过程类似于循环，所以有时可以做循环的替代方法。

递归调用中，递归函数既是主调函数又是被调函数。递归执行时，每调用一次就进入新的一层。 

例如：

#include <stdio.h>

f(int x)

{

  if(x/2>0)

    f(x/2);

  printf("%d ", x);

}

main()

{

    f(10);

    printf("\n");

}

可以看到，f()函数体内出现了调用自身的语句f(x/2);,所以f()函数是一个递归函数。

分析这个程序的执行过程：

①当main()函数调用f()函数时，将实参的值10,传递给形参x。

②第一次f()函数的执行：执行f()函数，形参x为10，因为x/2的值为5，大于0，所以再次调用f()函数，此次将表达式x/2的值5作为实参传递给下一次调用。

③第一次递归调用：形参x得到实参的值5，判断x/2的值，仍然大于0，所以继续递归调用f()函数，此次调用函数，传递过去的实参的值将是x/2，即5/2，实参为2。

④第二次递归调用：形参x的得到实参传递过来的2，判断x/2的值，结果为1，仍然大于0，继续递归调用f()函数，传递过去的实参的值将是x/2，即2/2，实参为1。

⑤第三次递归调用：形参x得到实参传递过来的1,判断x/2的值，结果为0，不再大于0，if语句的条件表达式不成立，执行if后面的语句，输出x的值1。函数执行结束，返回调用处，调用处为第二次递归调用处。

⑥当返回第二次递归调用处时，if语句已经执行完毕，继续执行if后面的语句，输出x的值，此时的x是2，输出。函数执行结束返回调用处。调用处为第一次递归调用。

⑦回到第一次递归调用，此处的if语句也执行完毕，执行if后面的语句，输出x的值，此时x的值为5，输出。函数执行结束返回调用处。

⑧此次返回第一次执行f()函数处，同样执行if后面的语句，输出x的值10,并返回调用处main()函数。具体执行过程如图所示：

C语言中的递归分为两种，一种是直接递归，另一种是间接递归。

直接递归就是函数直接调用自身。上例就是一个直接递归的过程。

间接递归是函数f1()调用f2(),而f()函数中又调用了fl(),过程如图所示。递归函数设计过程中，注意不要出现无休止地调用其自身的情况，例如：

#include <stdio.h> 

f(int x)

{

    f(x+1);

}

调用过程如图所示。

因为递归在内存中使用堆栈的方式，如果无终止递归，最终会导致栈溢出。为了防止递归调用无终止地进行，函数内必须有终止递归调用的手段。常用的办法是用一个条件进行判断，满足某种条件后就不再作递归调用，然后逐层返回。