递归算法

2025年3月17日 | 阅读 14 分钟

递归问题在竞技编程中很常见。在尝试使用各种编程范式解决这些问题之前，您将首先为它们开发递归逻辑。递归思维是编程中一个至关重要的部分。它帮助您将复杂的任务分解为更简单的任务。因此，它几乎在所有编程语言中都得到广泛使用。

什么是递归？

递归是函数直接或间接调用自身的行为，相关的函数称为递归函数。递归方法可以相对轻松地解决某些问题。汉诺塔（TOH）、树的前序/中序/后序遍历、图的深度优先搜索（DFS）等就是这些问题的一些例子。递归函数通过调用自身的副本来解决特定问题，并解决原始问题的较小子问题。在需要时，可以产生许多额外的递归调用。重要的是要明白，我们必须提供一个特定的情况来停止这个递归过程。因此，每次函数调用自身时，都是原始问题的一个简化版本。

递归算法用较小的输入值调用自身，并在对较小输入的返回值执行基本操作后，为当前输入提供结果。如果一个问题的较小版本可以通过应用解决方案来解决，并且这些较小版本会减少到易于解决的例子，那么就可以用递归方法解决这个问题。

为了构建一个递归算法，您需要将给定的问题陈述分成两部分。第一部分是基本情况，第二部分是递归步骤。

基本情况：这是问题最简单的可能解决方案，仅由一个终止递归函数的条件组成。当满足特定条件时，结果会在这个基本情况中被评估。
递归步骤：它通过重复调用同一函数，但使用更小或更简单的输入来计算结果。

为什么需要递归

递归是一种出色的方法，可以让我们缩短代码并简化理解和编写。与迭代方法相比，它有一些优势，稍后将介绍。对于可以通过其相关子任务描述来完成的工作，递归是最好的方法之一。例如，一个数的阶乘。

递归的特点

递归的特点包括

对不同的输入重复相同的操作。
为了在每个阶段使问题变小，我们尝试使用更小的输入。
必须有一个基本条件来停止递归；否则，会导致无限循环。

算法中的步骤

在函数中实现递归使用以下算法步骤

步骤 1：建立一个基本情况。选择最简单的情况，其答案是显而易见或微不足道的。这是递归的停止条件，防止函数无限调用自身。
步骤 2：定义一个递归情况。用其较小版本来描述问题。递归调用函数将允许您通过将问题分解为更小的自身版本来解决每个子问题。
步骤 3：验证递归会终止。确保递归代码不会进入无限循环，并最终达到基本情况。
步骤 4：组合解决方案。要解决主要问题，需要将子问题的解决方案组合起来。

一个数学解释

让我们看一个程序员需要求前n个自然数之和的情况。有几种方法可以实现这一点，但最简单的方法是将从1到n的整数相加。因此，该函数在数学上表示如下：方法(1) - 简单地一次加一个 f(n) = 1 + 2 + 3 + ........ + n 但是还有另一种描述方式：方法(2) - 递归加法 f(n) = 1 当n=1时 f(n) = n + f(n-1) 当n>1时

方法(1)和(2)之间的唯一区别在于，在方法(2)中，函数“f()”在函数内部被调用。这种现象称为递归，包含递归的函数称为递归函数。最终，这对程序员来说是一个很好的工具，可以更直接、更有效地编写某些问题的代码。

递归函数在内存中是如何存储的？

递归会消耗额外的内存，因为每次调用递归函数都会增加到栈中，并在那里存储项目，直到调用结束。与栈数据结构一样，递归函数使用LIFO（后进先出）结构。

什么定义了递归的基本条件？

在递归程序中，给出了基本情况的解决方案，而更宏大问题的解决方案则是用更小的问题来表示的。

int fact(int n)
{
    if (n < = 1) // base case
        return 1;
    else    
        return n*fact(n-1);    
}

在前面提到的例子中，描述了 n = 1 的基本情况，而一个数的更大值可以通过将其缩小直到达到基本情况来解决。

递归如何用于解决特定问题？

目标是将一个更大的问题分解成一个更小的问题，然后添加一个或多个基本条件来停止递归。例如，如果我们知道 (n-1) 的阶乘，我们就可以计算 n 的阶乘。阶乘的基本情况是 n = 0。如果 n 等于 0，我们返回 1。

为什么递归会导致堆栈溢出错误？

如果基本情况没有达到或没有定义，可能会发生堆栈溢出问题。为了进一步理解这一点，让我们看一个例子。

int fact(int n)
{
    // wrong base case (it may cause
    // stack overflow).
    if (n == 100) 
        return 1;

    else
        return n*fact(n-1);
}

如果调用 fact(10)，那么 fact(9)、fact(8)、fact(7) 等也将被调用，但总数将始终是 100。基本情况仍未达到。如果栈上的这些函数填满了所有可用内存，将会发生堆栈溢出错误。

直接递归和间接递归有什么区别？

如果一个函数调用另一个名为 fun 的函数，那么该函数被称为直接递归。如果一个函数 fun 调用另一个函数，比如 fun_new，而 fun_new 直接或间接地调用 fun，那么该函数被称为间接递归。表1展示了直接递归和间接递归之间区别的示例。

// An example of direct recursion
void directRecFun()
{
    // Some code...

    directRecFun();

    // Some code...
}

// An example of indirect recursion
void indirectRecFun1()
{
    // Some code...

    indirectRecFun2();

    // Some code...
}
void indirectRecFun2()
{
    // Some code...

    indirectRecFun1();

    // Some code...
}

尾递归和非尾递归有什么区别？

当递归调用是函数的最后一个动作时，它被称为尾递归。有关更多信息，请参阅关于尾递归的文章。

递归如何为不同的函数调用分配内存？

任何函数从 main() 调用时都会在栈上分配内存。每当递归函数调用自身时，都会创建局部变量的新副本，并且在为调用函数分配的内存之上为被调用函数分配内存。当函数达到基本情况时，内存被释放，过程继续，将其值传递给调用它的函数。

让我们用一个简单的函数来演示递归是如何工作的。

递归方法的内存分配

每次递归调用时，函数都会在新的栈内存副本中生成。一旦操作返回一些数据，该副本就会从存储中移除。因为函数内部指定的所有参数和其他变量都保留在栈上，所以每个递归调用都保留一个独立的栈。在从适当的函数返回值后，栈被移除。

在解决和跟踪每个递归调用的值方面，递归相当复杂。因此，您必须跟踪栈的内容和变量的值。检查以下示例以了解有关递归函数如何分配内存的更多信息。

//Fibonacci program recursive Function
int Fib(int num)
{
   if ( num == 0 )
      return 0;
   else if ( num == 1 )
      return 1;
   else
      return ( Fib(num-1) + Fib(num - 2) );
} 
//Let's say we want to calculate the Fibonacci number for n=5
Fib(5)

现在考虑以下针对 n = 5 的递归斐波那契算法。首先保存所有栈，直到 n 等于零，然后打印 n 的相应值。一旦通过返回 0 到调用栈满足终止条件，栈将逐个被消除。查看下图以理解调用栈的层次结构。

C++

// A C++ program to demonstrate the working of
// recursion
#include <bits/stdc++.h>
using namespace std;

void printFun(int test)
{
	if (test < 1)
		return;
	else {
		cout << test << " ";
		printFun(test - 1); // statement 2
		cout << test << " ";
		return;
	}
}

// Driver Code
int main()
{
	int test = 3;
	printFun(test);
}

输出

3 2 1 1 2 3

说明

上述代码从给定的正数打印到零（0），然后再次从零（0）打印到给定的数。

时间复杂度： O(1)

辅助空间： O(1)

Java

// A Java program to demonstrate the working of
// recursion
class GFG {
	static void printFun(int test)
	{
		if (test < 1)
			return;
		else {
			System.out.printf("%d ", test);
			printFun(test - 1); // statement 2
			System.out.printf("%d ", test);
			return;
		}
	}

	// Driver Code
	public static void main(String[] args)
	{
		int test = 3;
		printFun(test);
	}
}

输出

3 2 1 1 2 3

说明

上述代码从给定的正数打印到零（0），然后再次从零（0）打印到给定的数。

时间复杂度： O(1)

辅助空间： O(1)

Python

# A Python 3 program to
# demonstrate the working of
# recursion


def printFun(test):

	if (test < 1):
		return
	else:

		print(test, end=" ")
		printFun(test-1) # statement 2
		print(test, end=" ")
		return

# Driver Code
test = 3
printFun(test)

输出

3 2 1 1 2 3

说明

上述代码从给定的正数打印到零（0），然后再次从零（0）打印到给定的数。

时间复杂度： O(1)

辅助空间： O(1)

C#

// A C# program to demonstrate
// working of recursion
using System;

class GFG {

	// function to demonstrate
	// working on recursion
	static void printFun(int test)
	{
		if (test < 1)
			return;
		else {
			Console.Write(test + " ");

			// statement 2
			printFun(test - 1);

			Console.Write(test + " ");
			return;
		}
	}

	// Driver Code
	public static void Main(String[] args)
	{
		int test = 3;
		printFun(test);
	}
}

输出

3 2 1 1 2 3

说明

上述代码从给定的正数打印到零（0），然后再次从零（0）打印到给定的数。

时间复杂度： O(1)

辅助空间： O(1)

PHP

<?php
// PHP program to demonstrate
// working of recursion

// function to demonstrate
// working of recursion
function printFun($test)
{
	if ($test < 1)
		return;
	else
	{
		echo("$test ");
		
		// statement 2
		printFun($test-1);
		
		echo("$test ");
		return;
	}
}

// Driver Code
$test = 3;
printFun($test);
?>

输出

3 2 1 1 2 3

说明

上述代码从给定的正数打印到零（0），然后再次从零（0）打印到给定的数。

时间复杂度： O(1)

辅助空间： O(1)

Javascript

<script>

// JavaScript program to demonstrate the working of
// recursion

function printFun(test)
	{
		if (test < 1)
			return;
		else {
			document.write(test + " ");
			printFun(test - 1); // statement 2
			document.write(test + " ");
			return;
		}
	}

// Driver code
	let test = 3;
	printFun(test);

</script>

输出

3 2 1 1 2 3

说明

上述代码从给定的正数打印到零（0），然后再次从零（0）打印到给定的数。

时间复杂度： O(1)

辅助空间： O(1)

当从 main() 调用 printing(3) 时，一个局部变量 test 被初始化为 3，并且语句 1 到 4 被压入栈中，如下图所示。首先打印 '3'。语句 2 调用 printFun(2)，为 printFun(2) 分配内存，将局部变量 test 初始化为 2，并将语句 1 到 4 压入栈。printFun(2) 以类似方式调用 printFun(1)，printFun(1) 调用 printFun(0)。在 if 语句之后，printFun(0) 返回到 printFun(1)。完成 printFun(1) 的剩余语句后，它继续到 printFun(2) 等等。输出中首先写入从 3 到 1 的值，然后是从 1 到 3 的值。

递归是一种强大的方法，在编程和计算机科学中有多种用途。以下是递归的一些典型用途

树和图的遍历：在搜索和遍历树和图等数据结构时，递归被广泛使用。递归算法可用于系统地探查树或图的每个节点或顶点。
排序算法：快速排序和归并排序等排序算法也采用递归算法。在这些技术中，数据被分成较小的子数组或子列表，进行排序，然后使用递归进行合并。
分治算法：许多算法，如二分搜索算法，采用分治策略，使用递归将较大的问题分解为较小的子问题。
分形生成：递归算法可以创建分形形状和图案。例如，曼德博集合是通过将复数不断应用于一个递归算法来创建的。
回溯算法：回溯算法用于解决涉及一系列决策的问题，其中每个决策都依赖于先前的决策。递归可用于创建这些算法，以检查所有可能的途径，并在找不到解决方案时回溯。
记忆化：这种策略包括缓存昂贵函数调用的结果，并在再次提供相同输入时返回它们。递归函数可用于计算和存储子问题的结果以实现记忆化。

这些只是编程和计算机科学中递归的众多应用中的一小部分。递归是一种灵活而有效的方法，可以解决各种问题。

解释：这是一个实际的递归例子

编程中的递归利用了函数调用自身的思想。它可以有效地解决具有挑战性的问题，但需要精心设计以防止无限循环和堆栈溢出。

以下是不同编程语言中递归算法的实现

C++

#include <iostream>
using namespace std;
int factorial(int n)
{
   
    // Base case: if n is 0 or 1, return 1
    if (n == 0 || n == 1) {
        return 1;
    }
 
    // Recursive case: if n is greater than 1,
  // call the function with n-1 and multiply by n
    else {
        return n * factorial(n - 1);
    }
}
 
int main()
{
   
    // Call the factorial function and print the result
    int result = factorial(5);
       cout << result <<endl; // Output: 120
    return 0;
}

输出

说明

上面提到的程序提供了一个输出给定数字阶乘的函数。

Java

import java.util.*;
 
class Main {
    public static int factorial(int n)
    {
        // Base case: if n is 0 or 1, return 1
        if (n == 0 || n == 1) {
            return 1;
        }
 
        // Recursive case: if n is greater than 1,
        // call the function with n-1 and multiply by n
        else {
            return n * factorial(n - 1);
        }
    }
 
    public static void main(String[] args)
    {
        // Call the factorial function and print the result
        int result = factorial(5);
        System.out.println(result); // Output: 120
    }
}

输出

说明

上面提到的程序提供了一个输出给定数字阶乘的函数。

Python

def factorial(n):
    # Base case: if n is 0 or 1, return 1
    if n == 0 or n == 1:
        return 1
 
    # Recursive case: if n is greater than 1, call the function with n-1 and multiply by n
    else:
        return n * factorial(n-1)
 
# Call the factorial function and print the result
result = factorial(5)
print(result)  # Output: 120

输出

说明

上面提到的程序提供了一个输出给定数字阶乘的函数。

C#

using System;
 
class MainClass {
    public static int factorial(int n)
    {
        // Base case: if n is 0 or 1, return 1
        if (n == 0 || n == 1) {
            return 1;
        }
 
        // Recursive case: if n is greater than 1,
        // call the function with n-1 and multiply by n
        else {
            return n * factorial(n - 1);
        }
    }
 
    public static void Main (string[] args) {
        // Call the factorial function and print the result
        int result = factorial(5);
        Console.WriteLine(result); // Output: 120
    }
}

输出

说明

上面提到的程序提供了一个输出给定数字阶乘的函数。

Javascript

function factorial(n) {
  // Base case: if n is 0 or 1, return 1
  if (n === 0 || n === 1) {
    return 1;
  }
 
  // Recursive case: if n is greater than 1, call the function with n-1 and multiply by n
  else {
    return n * factorial(n - 1);
  }
}
 
// Call the factorial function and print the result
const result = factorial(5);
console.log(result); // Output: 120

输出

说明

上面提到的程序提供了一个输出给定数字阶乘的函数。

在这个例子中，我们定义了 factorial 函数，它接受数字 n 作为参数。该函数使用递归计算 n 的阶乘，即所有小于等于 n 的正整数的乘积。

n 的主要情况是 0 和 1。因此，factorial 函数首先测试它们。由于 0! 和 1! 都是 1，如果 n 是 0 或 1，该方法返回 1。

如果 n 大于 1，函数进入递归情况。它用输入 n-1 调用自身，并将结果乘以 n。这通过迭代计算 (n-1)! 来计算 n!。

必须记住，如果处理不当，递归可能会效率低下并导致堆栈溢出。每次函数调用，调用栈都会增加一帧；因此，如果递归太深，栈可能会变得无法管理。递归还可能使理解和调试代码变得更加困难，因为它需要考虑多层函数调用。

递归也可能是处理复杂问题的有效方法，特别是在将一个大问题细分为多个小问题时。如果使用得当，递归可以提高代码的优雅性和可读性。

递归编程和迭代编程之间有哪些缺点？

注意，每个递归程序都可以迭代地构建，反之亦然。这意味着递归程序和迭代程序具有相同的问题解决能力。由于所有函数都会保留在栈上直到达到基本情况，递归程序比迭代程序需要更多的存储空间。由于函数调用和返回的开销，它也需要更多的时间。

此外，由于代码更短，它们更难理解，在创建时需要更加小心。如果递归调用没有得到充分验证，机器可能会耗尽内存。

递归编程技术相比迭代编程有哪些好处？

递归提供了一种简洁明了的构建代码的方法。一些问题，如树的遍历、汉诺塔等，本质上是递归的。对于解决这类问题，推荐使用递归编码。这类程序也可以使用栈数据结构重复创建。迭代汉诺塔和无递归的中序树遍历就是例子。

递归的特点是两种情况：递归情况和基本情况。

当情况有效时，基本情况会终止递归函数。
每次递归调用时，该方法都会在栈内存中复制一份。
如果使用无限递归，栈内存最终可能会耗尽。
归并排序、快速排序、汉诺塔、斐波那契数列、阶乘问题等都是递归算法的一些例子。

结论

通过这篇关于递归算法的教程，您了解了什么是编程中的递归算法。然后您了解了多种递归类型和相关的函数调用结构。您还研究了如何在编程中实现 n 个自然数的和。最后，您还理解了递归过程如何在内存栈内分配内存。

如果您正在寻求超越数据结构的更深入的指导，并希望了解开发交互式应用程序的基础知识，Simplilearn的全栈Web开发研究生课程将非常适合您。这个国际知名的课程与加州理工学院CTME合作提供，旨在通过帮助您成为该领域的专家来增加您成为软件开发人员的机会。所以，现在就开始您的探索之旅吧！

下一个主题滑动窗口算法

递归算法

什么是递归？

为什么需要递归

递归的特点

算法中的步骤

一个数学解释

递归函数在内存中是如何存储的？

什么定义了递归的基本条件？

递归如何用于解决特定问题？

为什么递归会导致堆栈溢出错误？

直接递归和间接递归有什么区别？

尾递归和非尾递归有什么区别？

递归如何为不同的函数调用分配内存？

递归方法的内存分配

C++

Java

Python

C#

PHP

Javascript

C++

Java

Python

C#

Javascript

递归编程和迭代编程之间有哪些缺点？

递归编程技术相比迭代编程有哪些好处？

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

DAA 教程

渐进分析

复发

排序分析

分而治之

排序

下界理论

线性时间排序

哈希

二叉搜索树

红黑树

动态规划

贪婪算法

回溯

最小生成树

最短路径

所有对最短路径

最大流

排序网络

复杂度理论

近似算法

字符串匹配

面试题

其他

递归算法

什么是递归？

为什么需要递归

递归的特点

算法中的步骤

一个数学解释

递归函数在内存中是如何存储的？

什么定义了递归的基本条件？

递归如何用于解决特定问题？

为什么递归会导致堆栈溢出错误？

直接递归和间接递归有什么区别？

尾递归和非尾递归有什么区别？

递归如何为不同的函数调用分配内存？

递归方法的内存分配

C++

Java

Python

C#

PHP

Javascript

C++

Java

Python

C#

Javascript

递归编程和迭代编程之间有哪些缺点？

递归编程技术相比迭代编程有哪些好处？

结论

相关帖子

二分搜索算法

Kosaraju 算法

Dijkstra 算法

Kosaraju 算法

贪心算法示例

滑动窗口算法

计算理论中的停机问题