递归函数

递归是一个执行流程,在此执行流程中,只要条件正确,定义的函数就会调用自身,此类函数称为递归函数。

例如:

factorial(n)= n*factorial(n-1)

以上是一个阶乘函数。
n的阶乘 = n * (n-1)的阶乘;
(n-1)的阶乘 = (n-1) * (n-1)的阶乘;
(n-2)的阶乘 = (n-2) * (n-2)的阶乘;
.
.
.
1的阶乘 = 1

你可以看到n的阶乘等于n乘以n-1的阶乘。此函数通过在一定条件下不断调用自身直到条件不满足时,停止调用。因此它一个是递归的函数。

语法:

returnType function_name(dataType input)
{
    if(condition)
    { 
         /*函数将调用自身只要条件为true*/
         output=function_name(input);
    } 
    return output;
}

递归函数执行流程

递归流程图

例如:
程序使用递归算法计算任意数的阶乘。
程序:

#include<stdio.h>

unsigned long int factorial(long int num_copy); /*函数声明*/

int main()
{
    unsigned long int num;
    unsigned long int factorial_result;

    printf("\nEnter Num :");
    scanf("%ld",&num);

    factorial_result=factorial(num); //函数调用

    printf("阶乘(%ld)=%ld\n",num,factorial_result);

    return 0;
}

unsigned long int factorial(long int num_copy)  /*函数定义 */
{
    long double fact=1;

    if((num_copy==1)||(num_copy==0))
    {
        return 1;
    }
    else if(num_copy<0)
    {
        printf("阶乘(%ld)=Not defined ,请输入正整数",num_copy);
    }
    else
    {
        fact=fact*num_copy*factorial(num_copy-1);
    }
    return fact;
}

以上的例子中,假设我们输入的值为5。程序执行步骤如下:
Step1:
factorial_result=factorial(5); //调用函数

factorial(5) 第一次从main函数跳到定义的函数体内,输入参数为5

Step2:
factorial(5-1) 函数第一次自己调用自己,输入参数为4

fact=1 x 5 x factorial(5-1);

Step3:
factorial(4-1) 函数第二次自己调用自己,输入参数为3

fact=1 x 5 x 4 x factorial(4-1);

Step4:
factorial(3-1) 函数第三次自己调用自己,输入参数为2

fact=1 x 5 x 4 x 3 x factorial(3-1);

Step5:
factorial(2-1) 函数第四次自己调用自己,输入参数为1

fact=1 x 5 x 4 x 3 x 2 x factorial(2-1);

Step6:
factorial(1) 满足条件 if(num_copy==1) 所以函数factorial(1)返回1。

fact=1 x 5 x 4 x 3 x 2 x 1;

Step7:
最终函数返回值fact赋值给facorial_result.

facorial_result=120;

以上就是程序使用递归算法计算阶乘5的全过程。

下一节