c语言中的递归

本文概述

• 递归函数
• C中的递归示例
• 递归方法的内存分配

递归是当函数调用自身的副本以解决较小的问题时出现的过程。调用自身的任何函数都称为递归函数，此类函数调用称为递归调用。递归涉及多个递归调用。但是，强加递归的终止条件很重要。递归代码比迭代代码短，但是很难理解。

递归不能应用于所有问题，但是它对于可以根据类似子任务定义的任务更为有用。例如，递归可以应用于排序，搜索和遍历问题。

通常，迭代解决方案比递归更有效，因为函数调用始终是开销。任何可以递归解决的问题，也可以迭代解决。但是，某些问题最适合通过递归解决，例如，河内塔，斐波那契数列，阶乘发现等。

在下面的示例中，递归用于计算数字的阶乘。

#include <stdio.h>
int fact (int);
int main()
{
    int n, f;
    printf("Enter the number whose factorial you want to calculate?");
    scanf("%d", &n);
    f = fact(n);
    printf("factorial = %d", f);
}
int fact(int n)
{
    if (n==0)
    {
        return 0;
    }
    else if ( n == 1)
    {
        return 1;
    }
    else 
    {
        return n*fact(n-1);
    }
}

输出量

Enter the number whose factorial you want to calculate?5
factorial = 120

我们可以通过下图了解上面的递归方法调用程序：

递归函数

递归函数通过将其划分为子任务来执行任务。在函数中定义了一个终止条件，该终止条件由某些特定的子任务满足。此后，递归停止并从函数返回最终结果。

函数不重复的情况称为基本情况，而函数不断调用自身以执行子任务的情况称为递归情况。可以使用此格式编写所有递归函数。

下面给出了用于编写任何递归函数的伪代码。

if (test_for_base)
{
	return some_value;
}
else if (test_for_another_base)
{
	return some_another_value;
}
else
{
	// Statements;
	recursive call;
}

C中的递归示例

让我们看一个示例来查找斐波那契数列的第n个项。

#include<stdio.h>
int fibonacci(int);
void main ()
{
    int n, f;
    printf("Enter the value of n?");
    scanf("%d", &n);
    f = fibonacci(n);
    printf("%d", f);
}
int fibonacci (int n)
{
    if (n==0)
    {
    return 0;
    }
    else if (n == 1)
    {
        return 1; 
    }
    else
    {
        return fibonacci(n-1)+fibonacci(n-2);
    }
}

输出量

Enter the value of n?12 
144

递归方法的内存分配

每个递归调用都会在内存中创建该方法的新副本。该方法返回一些数据后，副本将从内存中删除。由于在函数内部声明的所有变量和其他内容都存储在堆栈中，因此在每次递归调用时都维护一个单独的堆栈。从相应的函数返回该值后，堆栈将被破坏。递归在解析和跟踪每个递归调用中的值时涉及很多复杂性。因此，我们需要维护堆栈并跟踪堆栈中定义的变量的值。

让我们考虑以下示例，以了解递归函数的内存分配。

int display (int n)
	{
		if(n == 0)
			return 0; // terminating condition
		else 
		{
			printf("%d", n);
			return display(n-1); // recursive call
		}
	}

说明

让我们检查一下n = 4的递归函数。首先，维护所有堆栈，该堆栈将打印n的相应值，直到n变为0为止。一旦达到终止条件，则通过将其调用返回0来逐个破坏堆栈。堆。考虑以下图像，以获取有关递归函数的堆栈跟踪的更多信息。