算法篇--递归

递归

一、算法思想：

1、定义 ：在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。简单来说，递归表现为函数调用函数本身。

2、特点：

递归有两个显著的特征,终止条件和自身调用:

• 自身调用：原问题可以分解为子问题，子问题和原问题的求解方法是一致的，即都是调用自身的同一个函数。
• 终止条件：递归必须有一个终止的条件，即不能无限循环地调用本身。

二、典型例题：求n！的递归函数

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int Factorial(int n)
 6 {
 7     if (n == 0)
 8         return 1;
 9     else
10     {
11         return n * Factorial(n - 1);
12     }
13 
14 }
15 
16 
17 int main()
18 {
19     int sum = Factorial(3);
20     cout << sum << endl;
21     return 0;
22 }

递归解题思路

解决递归问题一般就三步曲，分别是：

• 第一步，定义函数功能
• 第二步，寻找递归终止条件
• 第二步，递推函数的等价关系式

1.定义函数功能

定义函数功能，就是说，你这个函数是干嘛的，做什么事情，换句话说，你要知道递归原问题是什么呀？比如你需要解决阶乘问题，定义的函数功能就是n的阶乘，如下：

//求n的阶乘（n为大于0的自然数）
int factorial (int n){
 
}

2.寻找递归终止条件

递归的一个典型特征就是必须有一个终止的条件，即不能无限循环地调用本身。所以，用递归思路去解决问题的时候，就需要寻找递归终止条件是什么。比如阶乘问题，当n=1的时候，不用再往下递归了，可以跳出循环啦，n=1就可以作为递归的终止条件，如下：

//n的阶乘（n为大于0的自然数）
int factorial (int n){
    if(n==1){
      return 1;
    }
}

3.递推函数的等价关系式

递归的本义，就是原问题可以拆为同类且更容易解决的子问题，即原问题和子问题都可以用同一个函数关系表示。递推函数的等价关系式，这个步骤就等价于寻找原问题与子问题的关系，如何用一个公式把这个函数表达清楚。阶乘的公式就可以表示为 f(n) = n * f(n-1), 因此，阶乘的递归程序代码就可以写成这样，如下：

int factorial (int n){
    if(n==1){
      return 1;
    }
    return n * factorial(n-1);
}

递归与栈的关系

其实，递归的过程，可以理解为出入栈的过程的，为了更容易理解一些，我们来看一下 函数Factorial（n=5）的递归执行过程，如下：

递归的经典应用场景

哪些问题我们可以考虑使用递归来解决呢？即递归的应用场景一般有哪些呢？

• 阶乘问题
• 二叉树深度
• 汉诺塔问题
• 斐波那契数列
• 快速排序、归并排序（分治算法也使用递归实现）
• 遍历文件，解析xml文件