5.5 KiB

Raw Permalink Blame History

C 语言中的递归函数

原文：https://overiq.com/c-programming-101/recursive-function-in-c/

最后更新于 2020 年 7 月 27 日

在 C 语言中，一个函数可以自己调用。这个过程被称为递归。

调用自身的函数称为递归函数。起初，递归可能会显得有些棘手。让我们举一个简单的例子:

int main()
{
    callme();
    ...
    return 0;
}

void rec()
{
    statement 1;
    ...
    rec();
}

一开始main()函数调用rec()，然后在rec()函数内部，它又调用了自己。正如你所猜测的，这个过程会无限期地重复下去。因此，在递归函数中，必须有终止条件来停止递归。这种情况称为基本情况。

int main()
{
    callme();
}

void callme()
{
    if(base_condition)
    {
        // terminating condition
    }
    statement 1;
    ...
    callme();
}

在可以使用循环的地方，经常可以使用递归。一般来说，递归解决方案是优雅的，但不如循环解决方案有效。那么为什么要使用递归呢？因为使用像 quicksort 这样的递归可以更清楚、更容易地实现一些算法。

递归函数分两个阶段工作:

绕组相位。
展开阶段。

**绕线阶段:**在绕线阶段，递归函数不断调用自己。当达到基本条件时，此阶段结束。

**解套阶段:**当达到基础条件时，解套阶段开始，控制返回初始调用。

让我们举个例子:

例 1:

#include<stdio.h>
void rec();

int main()
{
     rec(1);

    // signal to operating system program ran fine
    return 0;
}

void rec(int n)
{
    printf("Winding phase: Level = %d\n", n);

    if(n<3)
    {
        rec(n+1);
    }

    printf("Unwinding phase: Level = %d\n", n);
}

预期输出:

Winding phase: Level = 1
Winding phase: Level = 2
Winding phase: Level = 3
Unwinding phase: Level = 3
Unwinding phase: Level = 2
Unwinding phase: Level = 1

工作原理:

绕组阶段 1:

首先，main()调用实际参数为 1 的rec()函数。因此，rec()函数的形式参数被初始化为1的值。在第 14 行中，执行printf()语句并打印n的值。

"Winding phase: Level = 1"

然后测试 if 条件(n < 3)即(1 < 3)，因为是真的，rec()1 级称为rec()2 级，实际参数为 2。

绕组阶段 2:

现在，控制再次传递到第 2 级rec()函数，其形式参数为2。第 14 行的printf()语句再次执行并打印。

"Winding phase: Level = 2"

如果条件(n < 3)即(2 < 3)再次被测试，由于是真的，第二级rect()以3的实际论证称为第三级rec()。

绕组阶段 3:

一旦控制传递到第 3 级rec()函数，其形式参数为3。第 14 行的printf()语句再次执行并打印。

"Winding phase: Level = 3"

如果条件(n < 3)即(3 < 3)被检查，但这次是假的，结果，对rec()的呼叫被跳过。现在我们的程序已经达到了基础条件。这就完成了缠绕阶段。

展开阶段 1:

在这个三级调用中，第一次执行并打印第 21 行的printf()语句。

"Unwinding phase: Level = 3"

一旦缠绕阶段 3 中的rec()功能结束，控制就传递回其调用者(即 2 级调用)，并从那里恢复执行。

展开阶段 2:

由于在第 2 级调用中执行的最后一条语句是对 if 语句中第 3 级rec()函数的调用，因此，第 2 级rec()函数继续执行以下语句，并打印出来。

"Unwinding phase: Level = 2"

然后 2 级rec()功能结束，将控制传递给 1 级rec()功能。

展开阶段 3:

就像在第 2 级rec()调用中一样，第 1 级 rec()中的执行继续执行 if 语句之后的语句，该语句会打印出来。

"Unwinding phase: Level = 1"

然后 1 级 rec()结束，控制返回到main()功能。

例 2:

下面的程序使用递归计算一个数的阶乘。

#include<stdio.h>
int factorial(int n);

int main()
{
    int n;

    printf("Enter a number: ");
    scanf("%d", &n);

    printf("%d! = %d", n, factorial(n));

    // signal to operating system program ran fine
    return 0;
}

int factorial(int n)
{
    if(n == 0) // base condition
    {
        return 1;
    }

    else
    {
        return n * factorial(n-1);
    }
}

预期输出:

Enter a number: 5
5! = 120

工作原理:

假设我们要计算5的阶乘。

main()自5 != 0唤factorial(5) -factorial(5)自factorial(4)唤自4 != 0 - factorial(4)唤factorial(3) 自3 != 0 - factorial(3)唤factorial(2) 自2 != 0 - factorial(2)唤factorial(1)自1 != 0 - factorial(1)唤factorial(0)

当用n = 0调用factorial()时，如果条件变为真，递归停止，控制返回到factorial(1)。从现在开始，每个被调用的函数都将按照与函数调用相反的顺序返回一个值给前一个函数。

例 3:

使用递归计算一个数的幂的程序。

#include<stdio.h>
int power(int base, int exp);
int main()
{
    int base, exp;

    printf("Enter base: ");
    scanf("%d", &base);

    printf("Enter exponent: ");
    scanf("%d", &exp);

    printf("%d ^ %d = %d", base, exp, power(base, exp));

    // signal to operating system everything works fine
    return 0;
}

int power(int base, int exp)
{
    if(exp == 0) // base condition
    {
        return 1;
    }

    else
    {
        return base * power(base, exp - 1);
     }
}

预期输出:

Enter base: 4
Enter exponent: 3
4 ^ 3 = 64

5.5 KiB Raw Permalink Blame History

C 语言中的递归函数

5.5 KiB

Raw Permalink Blame History