递归函数

一个自定义的函数可以被main函数和其它函数调用，如果自定义函数在函数体内调用它自身，我们就称为递归函数(recursion)。

例1：输入一个数n，求n+(n-1)+(n-2)…..1的和?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include<iostream>
using namespace std;
int f(int a){
    if(a==1)return 1;
    else return a+f(a-1);
    
}
int main(){
    int n;
    cout<<"please input a number:";
    cin>>n;
    cout<<f(n);
    
}

递归调用的终止条件

每一个递归函数都应该只进行有限次的递归调用，否则它就会进入死胡同，永远也不能退出了，这样的程序是没有意义的。
要想让递归函数逐层进入再逐层退出，需要解决两个方面的问题：
1、存在终止条件，当符合这个条件时递归便不再继续。
2、每次递归调用之后越来越接近这个终止条件。

递归函数的几种形式

1、尾递归，也就是递归调用位于函数体的结尾处 ；
2、中间递归：发生递归调用的位置在函数体的中间；
3、多层递归：在一个函数里面多次调用自己。

递归函数的优缺点

优点

1. 代码简洁明了：递归函数通常比等效的非递归实现更加简洁，更易于理解和维护，尤其是在处理复杂问题时。
2. 问题分解：递归提供了一种自然的方法来分解问题，将复杂问题分解为更小、更易于管理的子问题。
3. 适合解决某些类型的问题：对于像树遍历、图搜索等自然具有递归结构的问题，递归方法特别有效和直观。
4. 减少代码量：在某些情况下，使用递归可以减少代码量，使代码更加紧凑。

缺点

1. 性能问题：递归函数可能会导致额外的函数调用开销，尤其是在深度递归的情况下。每次函数调用都会消耗栈空间，导致性能下降。
2. 栈溢出的风险：深度递归可能导致调用栈过大，从而引发栈溢出错误。这是因为每个函数调用都会在栈上占用一定的空间，而栈的大小是有限的。
3. 调试困难：递归逻辑有时可能难以理解和跟踪，特别是对于复杂的递归函数，这可能使得调试变得更加困难。
4. 非最优性能解：对于某些问题，递归解决方案可能不是最高效的。例如，使用循环代替递归可以避免函数调用的开销，从而提高性能。

所有递归都可以用循环实现