什么是递归？ 函数直接或间接调用自身的过程称为递归，相应的函数称为递归函数。使用递归算法，某些问题可以很容易地解决。这类问题的例子如下： 河内大厦（TOH） , 按序/前序/后序树遍历 , 图的DFS 等
数学解释
让我们考虑一个程序员必须确定第一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（） “它本身在函数内部被调用，因此这种现象被称为递归，包含递归的函数被称为递归函数，最后，这是程序员手中的一个伟大工具，可以以更简单有效的方式编写一些问题的代码。
递归的基本条件是什么？ 在递归程序中，给出了基本情况的解，而较大问题的解用较小问题表示。
int fact(int n){ if (n < = 1) // base case return 1; else return n*fact(n-1); }
在上面的示例中，定义了n<=1的基本情况，并且可以通过转换为较小的数值来解决较大的数值，直到达到基本情况。
如何使用递归解决特定问题？ 其思想是用一个或多个较小的问题来表示问题，并添加一个或多个停止递归的基本条件。例如，我们计算阶乘n，如果我们知道（n-1）的阶乘。阶乘的基本情况是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);}
如果调用事实（10），它将调用事实（9）、事实（8）、事实（7）等等，但数字永远不会达到100。因此，基本情况尚未达到。如果堆栈上的这些函数耗尽了内存，将导致堆栈溢出错误。
直接递归和间接递归的区别是什么？ 如果函数fun调用相同的函数fun，则称其为直接递归函数。如果一个函数fun调用另一个函数say fun_new和fun_new直接或间接调用fun，则称为间接递归函数fun。直接递归和间接递归的区别如表1所示。
// An example of direct recursionvoid directRecFun(){ // Some code.... directRecFun(); // Some code...}// An example of indirect recursionvoid indirectRecFun1(){ // Some code... indirectRecFun2(); // Some code...}void indirectRecFun2(){ // Some code... indirectRecFun1(); // Some code...}
有尾递归和无尾递归的区别是什么？ 当递归调用是函数最后执行的事情时，递归函数是尾部递归的。请参考 尾部递归文章 详细信息。
在递归中，内存是如何分配给不同的函数调用的？ 从main（）调用任何函数时，都会在堆栈上为其分配内存。递归函数调用自身，被调用函数的内存分配在分配给调用函数的内存之上，并且为每个函数调用创建不同的局部变量副本。当达到基本情况时，函数将其值返回给调用它的函数，并取消分配内存，过程继续。 让我们以一个简单函数为例来说明递归是如何工作的。
CPP
// A C++ program to demonstrate 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); } |
JAVA
// A Java program to demonstrate 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); } } // This code is contributed by // Smitha Dinesh Semwal |
Python3
# A Python 3 program to # demonstrate 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) # This code is contributed by # Smitha Dinesh Semwal |
C#
// A C# program to demonstrate // working of recursion using System; class GFG { // function to demonstrate // working of 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); } } // This code is contributed by Anshul Aggarwal. |
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 ); // This code is contributed by // Smitha Dinesh Semwal. ?> |
Javascript
<script> // JavaScript program to demonstrate 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
什么时候 打印乐趣（3） 从main（）调用，内存分配给 打印乐趣（3） 局部变量测试被初始化为3，语句1到4被推送到堆栈上，如下图所示。它首先打印“3”。在声明2中， 打印乐趣（2） 调用，并将内存分配给 打印乐趣（2） 局部变量test被初始化为2，语句1到4被推送到堆栈中。同样地， 打印乐趣（2） 电话 printFun（1） 和 printFun（1） 电话 printFun（0） . printFun（0） 转到if语句并返回到 printFun（1） .委员会的其余声明 printFun（1） 执行并返回到 打印乐趣（2） 等等在输出中，打印3到1之间的值，然后打印1到3。内存堆栈如下图所示。
现在，让我们讨论几个使用递归可以解决的实际问题，并了解其基本工作原理。要了解基本情况，请阅读以下文章。 对递归有基本的理解。 问题1： 编写一个程序，求n的斐波那契级数，其中n>2。 数学方程：
n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;
递归关系：
T(n) = T(n-1) + T(n-2) + O(1)
递归程序：
Input: n = 5 Output:Fibonacci series of 5 numbers is : 0 1 1 2 3
实施：
C++
// C++ code to implement Fibonacci series #include <bits/stdc++.h> using namespace std; // Function for fibonacci int fib( int n) { // Stop condition if (n == 0) return 0; // Stop condition if (n == 1 || n == 2) return 1; // Recursion function else return (fib(n - 1) + fib(n - 2)); } // Driver Code int main() { // Initialize variable n. int n = 5; cout<< "Fibonacci series of 5 numbers is: " ; // for loop to print the fibonacci series. for ( int i = 0; i < n; i++) { cout<<fib(i)<< " " ; } return 0; } |
C
// C code to implement Fibonacci series #include <stdio.h> // Function for fibonacci int fib( int n) { // Stop condition if (n == 0) return 0; // Stop condition if (n == 1 || n == 2) return 1; // Recursion function else return (fib(n - 1) + fib(n - 2)); } // Driver Code int main() { // Initialize variable n. int n = 5; printf ( "Fibonacci series " "of %d numbers is: " , n); // for loop to print the fibonacci series. for ( int i = 0; i < n; i++) { printf ( "%d " , fib(i)); } return 0; } |
JAVA
// Java code to implement Fibonacci series import java.util.*; class GFG { // Function for fibonacci static int fib( int n) { // Stop condition if (n == 0 ) return 0 ; // Stop condition if (n == 1 || n == 2 ) return 1 ; // Recursion function else return (fib(n - 1 ) + fib(n - 2 )); } // Driver Code public static void main(String []args) { // Initialize variable n. int n = 5 ; System.out.print( "Fibonacci series of 5 numbers is: " ); // for loop to print the fibonacci series. for ( int i = 0 ; i < n; i++) { System.out.print(fib(i)+ " " ); } } } // This code is contributed by rutvik_56. |
Python3
# Python code to implement Fibonacci series # Function for fibonacci def fib(n): # Stop condition if (n = = 0 ): return 0 # Stop condition if (n = = 1 or n = = 2 ): return 1 # Recursion function else : return (fib(n - 1 ) + fib(n - 2 )) # Driver Code # Initialize variable n. n = 5 ; print ( "Fibonacci series of 5 numbers is :" ,end = " " ) # for loop to print the fibonacci series. for i in range ( 0 ,n): print (fib(i),end = " " ) |
C#
using System; public class GFG { // Function for fibonacci static int fib( int n) { // Stop condition if (n == 0) return 0; // Stop condition if (n == 1 || n == 2) return 1; // Recursion function else return (fib(n - 1) + fib(n - 2)); } // Driver Code static public void Main () { // Initialize variable n. int n = 5; Console.Write( "Fibonacci series of 5 numbers is: " ); // for loop to print the fibonacci series. for ( int i = 0; i < n; i++) { Console.Write(fib(i) + " " ); } } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // JavaScript code to implement Fibonacci series // Function for fibonacci function fib(n) { // Stop condition if (n == 0) return 0; // Stop condition if (n == 1 || n == 2) return 1; // Recursion function else return fib(n-1) + fib(n-2); } // Initialize variable n. let n = 5; document.write( "Fibonacci series of 5 numbers is: " ); // for loop to print the fibonacci series. for (let i = 0; i < n; i++) { document.write(fib(i) + " " ); } </script> |
Fibonacci series of 5 numbers is: 0 1 1 2 3
下面是input 5的递归树，它清楚地展示了如何将一个大问题转化为小问题。 fib（n）是一个斐波那契函数。给定程序的时间复杂度可能取决于函数调用。
fib（n）->level CBT（UB）->2^n-1节点->2^n函数调用->2^n*O（1）->T（n）=O（2^n）
最好的情况是。
T(n) = θ(2^n2)
工作：
![图片[2]-递归-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/20191107/geeks_fib1.jpg)
问题2： 编写一个程序，求n的阶乘，其中n>2。 数学方程：
1 if n == 0 or n == 1; f(n) = n*f(n-1) if n> 1;
递归关系：
T(n) = 1 for n = 0T(n) = 1 + T(n-1) for n > 0
递归程序： 输入： n=5 输出： 5的阶乘是：120 实施：
C++
// C++ code to implement factorial #include <bits/stdc++.h> using namespace std; // Factorial function int f( int n) { // Stop condition if (n == 0 || n == 1) return 1; // Recursive condition else return n * f(n - 1); } // Driver code int main() { int n = 5; cout<< "factorial of " <<n<< " is: " <<f(n); return 0; } |
C
// C code to implement factorial #include <stdio.h> // Factorial function int f( int n) { // Stop condition if (n == 0 || n == 1) return 1; // Recursive condition else return n * f(n - 1); } // Driver code int main() { int n = 5; printf ( "factorial of %d is: %d" , n, f(n)); return 0; } |
JAVA
// Java code to implement factorial public class GFG { // Factorial function static int f( int n) { // Stop condition if (n == 0 || n == 1 ) return 1 ; // Recursive condition else return n * f(n - 1 ); } // Driver code public static void main(String[] args) { int n = 5 ; System.out.println( "factorial of " + n + " is: " + f(n)); } } // This code is contributed by divyesh072019. |
Python3
# Python3 code to implement factorial # Factorial function def f(n): # Stop condition if (n = = 0 or n = = 1 ): return 1 ; # Recursive condition else : return n * f(n - 1 ); # Driver code if __name__ = = '__main__' : n = 5 ; print ( "factorial of" ,n, "is:" ,f(n)) # This code is contributed by pratham76. |
C#
// C# code to implement factorial using System; class GFG { // Factorial function static int f( int n) { // Stop condition if (n == 0 || n == 1) return 1; // Recursive condition else return n * f(n - 1); } // Driver code static void Main() { int n = 5; Console.WriteLine( "factorial of " + n + " is: " + f(n)); } } // This code is contributed by divyeshrabadiya07. |
Javascript
<script> // JavaScript code to implement factorial // Factorial function function f(n) { // Stop condition if (n == 0 || n == 1) return 1; // Recursive condition else return n*f(n-1); } // Initialize variable n. let n = 5; document.write( "factorial of " + n + " is: " + f(n)); // This code is contributed by probinsah. </script> |
factorial of 5 is: 120
工作：
![图片[3]-递归-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/20191108/geeks_Untitled-Diagram58.jpg)
用户输入的阶乘递归函数图5。
与迭代编程相比，递归编程有哪些缺点？ 请注意，递归和迭代程序都具有相同的问题解决能力，即每个递归程序都可以迭代编写，反之亦然。递归程序比迭代程序有更大的空间需求，因为在达到基本情况之前，所有函数都将保留在堆栈中。由于函数调用和返回开销，它还有更大的时间要求。
与迭代编程相比，递归编程有哪些优点？ 递归提供了一种简洁的代码编写方法。有些问题本质上是递归的，比如树遍历， 河内大厦 等。对于此类问题，最好编写递归代码。在堆栈数据结构的帮助下，我们也可以迭代地编写这样的代码。例如，参考 无递归的有序树遍历 , 河内大厦 .
面向初学者的基于输出的练习问题： 递归练习题|集1 递归练习题|集2 递归练习题|集3 递归练习题|集4 递归练习题|集5 递归练习题|集6 递归练习题|集7 递归测验 递归编码实践： 所有关于递归的文章 带解答的递归实践问题 本文由 奏鸣曲 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
