## 灵感

最近在做配置模块，然后整个配置的参数是非常多的，层级结构也很深。可能有几百个参数，三、四层的层级关系，想要捋顺所有的类和参数，太繁琐了，而且 Visual Studio 的类视图只能看到属性，却看不出层级关系来，所以花费些许精力，写一个控制台小程序，展示类结构。



原理就是通过反射得到所有属性，遍历展示，有层级关系的递归展示。

代码如下：

```csharp
public static void PrintProperties(object obj, int indentLevel, ref StringBuilder sb)
{
    try
    {
        var type = obj.GetType();

        var properties = type.GetProperties(BindingFlags.Public | BindingFlags.Instance);

        foreach (var property in properties)
        {
            string[] arr = new string[] { "", "", "" };

            if (property.PropertyType.IsClass && property.PropertyType != typeof(string))
            {
                var value = property.GetValue(obj);

                if (value == null && !property.PropertyType.IsArray)
                {
                    value = Activator.CreateInstance(property.PropertyType);
                }
                // 判断属性的类型是否为泛型类型
                if (property.PropertyType.IsGenericType)
                        {

                            // 获取属性的泛型类型定义
                            var typeDefinition = property.PropertyType.GetGenericTypeDefinition();

                            Type[] typeArgs = value.GetType().GetGenericArguments();

                            var temp = Activator.CreateInstance(typeArgs[0]);

                            // 判断泛型类型是否为 IEnumerable<T>
                            if (typeDefinition == typeof(IEnumerable<>))
                            {
                                arr[0] = "IEnumerable<";
                                arr[1] = typeArgs[0].Name;
                                arr[2] = "> ";
                            }
                            else if (typeDefinition == typeof(List<>))
                            {
                                arr[0] = "List<";
                                arr[1] = typeArgs[0].Name;
                                arr[2] = "> ";
                            }

                            // 判断泛型类型是否为 ICollection<T>
                            else if (typeDefinition == typeof(ICollection<>))
                            {
                                arr[0] = "ICollection<";
                                arr[1] = typeArgs[0].Name;
                                arr[2] = "> ";
                            }
                            else if (typeDefinition == typeof(Dictionary<,>))
                            {
                                arr[0] = "Dictionary<";
                                arr[1] = string.Join(",", typeArgs.Select(t => t.Name));
                                arr[2] = "> ";

                            }

                            sb.Append(new string(' ', indentLevel * 4));
                            sb.AppendLine("- " + string.Join("", arr) + property.Name);

                            PrintProperties(temp, indentLevel + 1, ref sb);
                        }
                else
                {
                    arr[0] = "";
                    arr[1] = property.PropertyType.Name;
                    arr[2] = " ";

                    sb.Append(new string(' ', indentLevel * 4));
                    sb.AppendLine("- " + string.Join("", arr) + property.Name);
                    //如果是数组，就不需要在递归
                    if (!property.PropertyType.IsArray)
                        PrintProperties(value, indentLevel + 1, ref sb);
                }
            }
            else
            {
                arr[0] = "";
                arr[1] = property.PropertyType.Name;
                arr[2] = " ";

                sb.Append(new string(' ', indentLevel * 4));
                sb.AppendLine("- " + string.Join("", arr) + property.Name);
            }
        }
    }
    catch (Exception ex)
    {

        throw;
    }
}


```

实例图：

![image.png](https://niuery.com/static/img/d6b1eb9278d8f80dd56f22d2e43e5b32.image.png)

小工具 --- 树形展示多属性复杂结构类

## 引言
按照时间复杂度，将一些常见排序算法进行分类，分为以下三类：
- $O(n^2)$：冒泡排序，插入排序，选择排序。

- $O(nlogn)$：快速排序，归并排序。

- $O(n)$：桶排序，计数排序，基数排序。

本篇文章讨论以下第一类：冒泡排序，插入排序，选择排序。


上一篇[数据结构与算法 --- 如何分析排序算法](https://niuery.com/post/53)提到，从三个方面分析排序算法：

- 排序算法的执行效率 - 时间复杂度

- 排序算法的内存消耗 -  原地排序算法/非原地排序算法

- 排序算法的稳定性 - 稳定排序算法/不稳定排序算法


那么，下面讨论一下这三种排序算法。

## 冒泡算法
**冒泡排序（bubble sort）过程包含多次冒泡操作，每一次冒泡操作都会遍历整个数组，依次比较相邻元素，不符合大小关系则互换位置，直到无元素需要交换。**

### 算法图解
那来看一下排序过程，假设有一组数据：1、6、9、3、7、2，按照从小到大的排序顺序排序，则第一轮的冒泡操作如下图：


![image.png](https://niuery.com/static/img/d34290c2a34afa51fdccb3f288a1b817.image.png)

这样，最大的数已经排在最后一个了，在完成其他五个数的排序，在进行五次这样的冒泡操作就排序完成，如下图：

![image.png](https://niuery.com/static/img/3f67c77d1cc4f3257696af4bee6ba044.image.png)

但是从上图也可以看出，在第四次冒泡的时候就已经排序完成，其实可以进行优化。当某一次冒泡操作已经没有数据交换时，说明已经排序完成，可以结束排序。

那么，使用C#实现一个冒泡排序如下：

```csharp
public void BubbleSort(int[] arr)
{
    if (arr == null || arr.Length == 0)
        return;

    var length = arr.Length;
    //提前结束排序的标志
    bool flag = false;

    for (int i = 0; i < length; i++)
    {
        for (int j = 0; j < length - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                //交换元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

                flag = true;
            }
        }
        //如果没有数据交换，则提前退出
        if (!flag)
            break;
    }
}

```

### 算法分析
1. 稳定性
   
   冒泡排序只涉及到相邻数据交换，只需要常量级的临时空间，空间复杂度为$O(1)$，是一个原地排序算法。
2. 内存消耗

   冒泡排序中，只有交换才可以改变两个元素的前后顺序，为了保证冒泡排序的稳定性，在冒泡过程中，我们对两个大小相等的相邻的元素不做交换，这就保证了相同大小的元素顺序在排序后不会改变。因此冒泡排序是一个稳定排序算法。
3. 时间复杂度
   
   最好的情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，所以最好时间复杂度为$O(1)$。
   
   最坏的情况下，要排序的数据是倒序排列的，则需要 $n$ 次冒泡操作，因此最坏时间复杂度为$O(n^2)$。
   
   对于平均时间复杂度，假设有 $n$ 个数据的集合，有 $n!$ 种不同的排列方式，所以很难直接计算时间复杂度。
   
所以计算排序算法的时间复杂度，需要另外一种思路：通过“有序度”和“无序度”这两个概念来进行分析：

- 有序度
    
    **有序度是指数组中具有有序关系的元素对的个数**，如果用数学式表达出来，就是：
    $$
    a[i] \leq a[j], \quad i<j
    $$
                              
- 逆序度
                              
    **逆序度则跟有序度定义相反，是指数组中逆序元素对的个数（假设从小到大为有序）** ，如果用数学式表达出来，就是：
    $$
    a[i] > a[j], \quad i<j  
    $$   

有序度和你序度使用图片表示出来如下图：  
   
![image.png](https://niuery.com/static/img/6e4452e5f75d8064836f72df22037693.image.png)
   
 还有一个概念，当数组是一个倒叙（假设从小到大的为有序）的排列的数组时，有序度为0，逆序度为$\frac{n(n-1)}{2}$（该公式为排列组合公式），也就是15，当它时一个完全有序的数组时，有序度为$\frac{n(n-1)}{2}$，逆序度为0，像这种完全有序的数据的有序度称之为满有序度（$\frac{n(n-1)}{2}$）。
   
从上述定义中，也可以看出，数组的有序度，逆序度，满有序度存在一定关系：**逆序度 \= 满有序度 \- 有序度**>。排序的过程就是增加有序度，减少逆序度的过程。当最终有序度达到满有序度时，说明已经排序完成。

所以补充上述排序过程中有序度变化如下图：

      
![image.png](https://niuery.com/static/img/c8d8da1634fac0a70be2c3d63fb5bc57.image.png)
可以看到冒泡排序只有比较和交换两个操作，因为交换只会交换相邻两个元素，所以每一次交换，有序度就增加1。无论冒泡算法如何改进，它的总交换数是固定的，这个数也是逆序度，所以上图排序过程中的满排序度是15（$\frac{6(6-1)}{2}$），初始有序度为8，所以上述排序过程共进行了7次交换操作。

那么，有了有序度和逆序度两个概念后，对于包含$n$个数据的数组进行冒泡排序，平均交换次数是多少呢？
    
最坏情况下，初始有序度为0，因此要进行 $\frac{n(n-1)}{2}$ 次交换。

最好情况下，初始有序度为 $\frac{n(n-1)}{2}$ ，不需要交换。
    
我们可以取中间值 $\frac{n(n-1)}{4}$ ，意味着要进行交换操作的量级是 $n^2$ 。而比较操作肯定要比交换操作多，复杂度的上限是 $O(n^2)$ （最坏时间复杂度），因此比较操作的量级也是 $n^2$ ，综合比较和交换两部分操作，冒泡排序的平均情况下的时间复杂度为 $O(n^2)$。
    

:::warning{title="注意"}
该方式推导平均时间复杂度其实并不严格，但是概率论的定量分析太复杂，这样的方式在一定程度上是实用的。
:::

## 插入排序
    
先思考一下，对于一个有序数组（假设数组从小到大），往里边添加一个数后，如何让数组仍然保持有序？

答案其实简单，遍历数组，直到找到比它大的，站在它前边就好了，往后的都退一步都往后稍一稍就行，哈哈。
像这样：

这样的方案其实就是维护一个动态数组有序的方法，即动态的往有序集合中添加数据。

对于一个静态数据，也可以使用这种插队的方式来进行排序，于是就有了插入排序算法（insertion sort）。

那么如何实现插入排序：首先，可以将数组中的元素分为两个区间，已排序区间和未排序区间，初始已排序区间只有一个元素，就是数组的第一个元素，插入排序的核心思想是取未排序区间的元素，在已排序区间中找合适的位置插入，并保证已排序区间一直有序，重复该过程，直到未排序区间中元素未空。

### 算法图解
    
如下图：

![image.png](https://niuery.com/static/img/892c86dce9d719428839d399529622ca.image.png)


插入排序过程包含两种基本操作：元素的比较和移动。当我们需要将一个数据 a 插入到已排序区间时，需要用数据 a 与已排序区间的数据依次比较大小，找到合适的插入点。在找到插入点之后，我们还需要将插入点之后的数据顺序往后移动一位，这样才能腾出位置给数据 a 插入。对于不同的查找插入点方法(从头到尾、从尾到头)，总的比较次数是有区别的。但对于一个给定的初始序列，移动操作的总次数是固定的，就等于数组的逆序度。


为什么说移动次数就等于逆序度呢？

如下图所示，满有序度为 $\frac{n(n-1)}{2}=15$，初始有序度为8，逆序度为7，在下图中移动元素的个数之和也等于7（$2+1+4=7$） 

![image.png](https://niuery.com/static/img/d70f66340129601e74a117db5097ab5e.image.png)
与冒泡排序算法一样，我们再来回答下面 3 个问题。
通过原理介绍和代码实现，我们可以很明显地看出，插入排序的运行过程并不需要额外的存储空间，因此，它是原地排序算法。同时，它的空间复杂度也是 $O(1)$。

那么，使用C#实现一个插入排序如下：

```csharp
public static void InsertionSort(int[] arr)
{
    if (arr == null || arr.Length == 0) return;

    var length = arr.Length;

    //从第二个元素开始比较（未排序区间）
    for (int i = 1; i < length; i++)
    {
        var val = arr[i];

        //遍历已排序区间
        for (int j = i - 1; j >= 0; j--)
        {
            //按从小到大排序，所以如果目标元素比已排序元素小，则已排序区间往后移动一位
            if (arr[j] > val)
            {
                arr[j + 1] = arr[j];
            }
            else
            {
                arr[j + 1] = val;
                break;
            }
        }
    }
}

```
### 算法分析
接下来分析一下插入排序算法：

第一，插入排序是原地排序算法吗？

插入排序的过程只有移动元素，并不会创建额外存储空间，因此，它是原地排序算法，且空间复杂度为$O(1)$。


第二，插入排序是稳定排序算法吗？

对于未排序区间的某个元素，如果在已排序区间存在与它值相同的元素，我们选择将它插入到已排序区间值相同元素的后面，这样就可以保持值相同元素原有的前后顺序不变，因此插入排序是稳定排序算法。

第三，插入排序的时间复杂度是多少？

如果要排序的数据已经是有序的，我们就不需要移动任何数据。如果我们选择从尾到头在已排序区间里查找插入位置，那么每次只需要比较一个数据就能确定插入位置。因此，综合元素移动和比较的次数，最好时间复杂度为 $O(n)$。

如果数组是倒序的，那么每次插入都相当于在数组的第一个位置插入新的数据。因此，需要移动大量的数据，最坏时间复杂度为 $O(n^2)$。

还记得我们在数组中插入一个数据的平均时间复杂度是多少吗? 

没错，是 $O(n)$ 。因此对于插入排序，每次插入操作都相当于在数组中插入一个数据，循环执行 $n$ 次插入操作，因此，平均时间复杂度为  $O(n^2)$。
    
## 选择排序

选择排序 (selection sort) 的实现思路类似插入排序，也将整个数组划分为已排序区间和未排序区间。两者的不同点在于: 选择排序每次从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

### 算法图解

选择排序图解如下：

![image.png](https://niuery.com/static/img/31636599a2e60bc3b41d92de7e039210.image.png)

使用C#实现一个选择排序如下：

```csharp
public static void SelectionSort(int[] arr)
{
    if (arr == null || arr.Length == 0) return;

    var length = arr.Length;
    //只需循环length - 1次
    for (int i = 0; i < length - 1; i++)
    {
        int minPos = i;
        //找出最小值的索引
        for (int j = i; j < length; j++)
        {
            if (arr[j] < arr[minPos])
            {
                minPos = j;
            }
        }
        //交换元素
        int temp = arr[i];
        arr[i] = arr[minPos];
        arr[minPos] = temp;
    }
}    
```
                                     
### 算法分析
                                     
这里不再做详细分析，首先，它排序过程中没有产生额外存储空间，空间复杂度为 $O(1)$，是一种原地排序算法。
                                     
选择排序的最好时间复杂度、最坏时间复杂度、平均时间复杂度都为 $O(n^2)$。

那么选择排序是稳定排序算法吗？
                                     
选择排序是不稳定排序算法。从图解中可以看出，选择排序每次要找剩余未排序元素中的最小值，然后与前面的元素交换位置。这里的交换操作破坏了排序算法的稳定性。例如5、8、5、2、9这样一组数据，使用选择排序来排序的话，第一次找到最小的元素是 2，与第一个元素 5 交换位置，那么第一个 5 和中间的 5 的原有的先后顺序就改变了，因此，选择排序就是不稳定的了。
                           
> 参考资料
> 
> [1] 数据结构与算法之美 / 王争 著. --北京：人民邮电出版社，2021.6

数据结构与算法 --- 排序算法（一）

## 引言
排序算法是最基础的算法，对于排序算法，除学习算法原理，代码实现之外，更重要的是学习每个算法的特点，知道在什么场景下选择那种算法。

那一定是选择时间复杂度最低的排序算法就是最优的吗？

可以从以下几个方面分析一下。



## 排序算法的执行效率

对于排序算法的执行效率，一般从以下几个方面来分析：
1. 最好时间复杂度，最坏时间复杂度，平均时间复杂度。
   
    在分析排序算法的时间复杂度时，我们要分别给出最好，最坏，平均情况下的时间复杂度，以及这些不同的复杂度对应的待排序数据的特点。对于排序算法，原始数据的**序度（接近有序的程度）**，对排序的执行时间有很大影响（尤其极端情况）。
    
2. 时间复杂度的系数，常数和低阶。
   
   时间复杂度反映的是算法的执行时间随数据规模n的增长趋势，再用大O表示法表示复杂度的时候，通常会省略掉系数，常数和低阶。但是当数据规模很小的时候，系数，常数和低阶的占比很大，也需要考虑。
   
3. 比较次数或交换（或移动）次数。
    
   常用的排序算法，如冒泡排序、插入排序、选择排序、快速排序和归并排序等，是基于比较的排序算法，这类排序算法的执行过程设计两个操作：比较元素大小和交换（或移动）元素位置。而这两个操作的耗时是不同的，比较元素大小的耗时要少于交换（或移动）元素位置。所以，在对排序算法的执行效率进行精细化分析时，要把比较次数和交换（或移动）次数区分开来统计。
   
## 排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。除空间复杂度分析之外，根据排序算法是否需要额外的非常量级的数据存储空间，可以分为 **原地排序算法（在原数据存储空间上完成排序操作）** 和 **非原地排序算法（需要额外的非常量级的数据存储空间才能完成排序）**。

特别注意的是，原地排序并不与 $O(1)$ 空间复杂度划等号。

一个排序算法是原地排序算法，可能它的空间复杂度并不是 $O(1)$ ，但是，一个排序算法的空间复杂度是 $O(1)$ ，那么它肯定是原地排序算法。

## 排序算法的稳定性

对于大部分算法，只分析执行效率和内存消耗就足够了，不过，**排序算法还有一个特有的分析维度：稳定性，根据稳定性，可以把排序算法分为稳定排序算法和不稳定排序算法。**

如果带排序的数据中存在值相等的元素，经过稳定排序算法排序之后，相等元素之间原有的先后顺序不变。经过不稳定排序算法排序之后，相等元素之间原有的先后顺序可能会被改变。 

例如，有这样一组数据：2、5、9、3、8、5，按照从小到大的的排序之后就变成了2、3、5、5、8、9。

其中数据中有两个5，那么当经过某种排序算法排序之后，两个5的前后顺序无变化，则该排序算法为稳定排序算法，反之，两个5的前后顺序发生变化，则为不稳定排序算法。

那么就产生了疑问，两个5不是一样的吗？

实际上，为了简化对算法的讲解，我们一般是用整数或字符串这些基本数据类型的数据做算法对象演示，但是在真正开发过程中，要排序的对象往往是复杂的数据类型“对象”，按照“对象”的某个属性（称为算法的Key值）进行排序。因此，尽管两个对象的Key值相同，但他们并不是相同的对象。

例如：现在要对电商系统中的“订单”排序，订单有两个属性，“下单时间”和“订单金额”，如果有10万条数据，我们按照金额从小到大排序，对于金额相同的订单，则按照下单时间从早到晚排序。在怎么做？

最先想到的处理方法：首先按照金额对订单进行排序，然后遍历排序之后的订单，对于每个金额相同的小区间在按照下单时间排序，这种排序思路理解起来很直接，符合常规思维，但是实现起来很繁琐。

再来看看借助稳定排序算法的处理思路。我们先按照下单时间给订单排序，注意是按照下单时间而不是金额。在排序完成之后，在利用稳定排序算法，按照订单金额重新排序。在两遍排序后，就达到了预期要求，但是可能理解需要仔细琢磨。

稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变，在第一次排序之后，所有的订单按照下单时间从早到晚排序，在第二次排序中，我们用稳定排序算法按照金额排序，相同金额的订单原有的先后顺序不变，仍然保持按照下单时间从早到晚排序，如下图：


![image.png](https://niuery.com/static/img/5dd7103d2a8519bee1031aa7334ebac8.image.png)

可以看出第一次按下单时间排序后，金额为23元的三个订单ID按顺序分别是3、1、6，经过第二次排序之后他们的订单ID按顺序依旧是3、1、6。

> 参考资料
> 
> [1] 数据结构与算法之美 / 王争 著. --北京：人民邮电出版社，2021.6

数据结构与算法 --- 如何分析排序算法

## 引言

上文[数据结构与算法 --- 递归（一）](https://niuery.com/post/51) 讲述了什么是递归算法，如何编写递归算法及如何写好递归算法，本文着重讲述一下如何避免递归过深导致的堆栈溢出问题。




## 探究产生堆栈溢出的原因

函数调用采用**函数调用栈**来保存当前“快照”（局部变量，返回地址等）。函数调用栈是内存中开辟的一块存储空间，它被组织成“栈”这种数据结构，数据先进后出。

递归的过程包含大量的函数调用，如果递归求解的数据规模很大，函数调用层次很深，那么函数调用栈中的数据（栈帧）会越来越多，而函数调用栈空间一般不大，堆栈空间不足以存储所有的调用信息，从而导致堆栈溢出。

以计算阶乘举例，代码如下：

```csharp
public int Factorial(uint n)
{
    if (n <= 1) return 1;

    return n * Factorial(n - 1);
}
```
当 `Factorial(n)` 执行到 `Factorial(n - 1)` 是，编译器将局部变量，`n` 和 `Factorial(n - 1)` 的返回地址封装为一个栈帧，保存在函数调用栈内，然后再跳转到 `Factorial(n - 1)` 函数体内。

在 `Factorial(n - 1)` 执行完成之后，返回结果（假设是 `result` ），编译器就从函数调用栈中取出之前保存的栈帧（局部变量 `n` 和`Factorial(n - 1)` 的返回地址）。通过返回地址，编译器就知道之前执行到了哪条语句（即 `return n * Factorial(n - 1)` 这条语句），就可以接着从这条语句继续往下执行：将栈帧中保存的 `n` 的值，与 `Factorial(n - 1)` 的结果（即 `result` ）相乘后将结果返回。

那如果不在函数调用栈中存储局部变量，返回地址等信息，是否可行呢？

答案肯定是不行。

- 若不存储返回地址，那么 `Factorial(n - 1)` 执行完之后，编译器就不知道该从哪里继续执行。
- 若不存储局部变量，那么 `Factorial(n - 1)` 执行完之后，编译器即使知道该从哪里执行，但不知道 `n` 的值，也就无法计算 `n * Factorial(n - 1)` 并返回了。 

## 讨论尾递归避免堆栈溢出

什么是尾递归？

**尾递归是指一个递归函数的最后一个操作是递归调用自身，并且该调用的返回值直接返回给函数的调用者，而不进行任何其他的计算或处理。这种形式的递归称为尾递归**。

在尾递归中，递归调用是函数的最后一步操作，因此不需要再次回到递归调用之前的位置来执行其他操作。这意味着尾递归可以被优化为循环，从而避免了递归调用带来的栈空间开销和性能问题。

例如将上述阶乘代码转化为尾递归代码如下：

```csharp
public int Factorial(uint n, int res)
{
    if (n <= 1) return res;
    return Factorial(n - 1, (int)(n * res));
}
```


从理论上来说，尾递归是又可能解决堆栈溢出的问题的。

上文说到，函数调用栈中保存局部变量和返回地址，而对于尾递归代码，递归代码出现在最后一行中，返回之后不需要继续往下执行，因此，返回地址可以不用保存；而局部变量 `n` 也被移动到新的函数 `Factorial(n - 1, n * res)` 中，也不需要保存到栈中。所以对于尾递归代码，不需要想栈里压入数据，也就不存在堆栈溢出的问题。

但是在实际开发过程中，尾递归其实并没有太大作用，不能期望它来规避递归导致的堆栈溢出问题，主要表现在：

- 并不是所有编程语言都支持尾递归优化
- 并不是所有的递归都可以改成尾递归
- 能改成尾递归的代码也就都可以改成迭代方式
- 尾递归代码的可读性差

> 参考资料
> 
> [1] 数据结构与算法之美 / 王争 著. --北京：人民邮电出版社，2021.6

数据结构与算法 --- 递归（二）

## 什么是递归？
**递归（Recursion)** 是一种解决问题的方法，它将问题分解为更小的子问题，并逐层解决这些子问题。递归算法的核心思想是：**一个函数可以直接或间接地调用自身**。通过这种自我调用，我们可以用简洁的代码来解决复杂问题。



##  满足递归的条件
一般来说，满足下面三个条件就可以使用递归：
- 待求解问题的解可以分解为多个子问题的答案。子问题就是数据规模更小的问题。
- 待求解问题与分解之后的问题，只有数据规模不同，求解思路完全相同。
- 存在递归终止的条件。递归问题必须得有终止条件，否则将会无限循环。


## 如何编写递归代码

编写递归代码的关键是将符合递归条件的问题公式化，将问题变成递推公式，寻找终止条件，然后根据公式“翻译”为代码。

例如[斐波那契数列](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97)的问题：数列的前两项为1，从第三项开始，每一项都等于前两项之和，那么求解斐波那契数列的第$n$项则有：
- $n$为正整数 $n$∈N 
- 当$n=1$或$n=2$，值为1
- 当$n>2$时，则$f(n)=f(n-1)+f(n-2)$

则有

$$
 f(x) =
\begin{cases}
1 & 0< x\leq 2 \\
f(x-1)+f(x-2) & x>2
\end{cases}\qquad x∈N
$$

然后将上述公式“翻译”为代码，如下所示：


```csharp
public int Fibonaci(uint n)
{
    if (n > 0 && n <= 2) return 1;

    return Fibonaci(n - 1) + Fibonaci(n - 2);
}
```

所以，编写递归代码的关键就是找到将大问题分解为小问题的规律，并且基于此写出递推公式，然后找出终止条件，最后将公式"翻译"成代码。

## 递归的堆栈溢出问题

在函数调用会使用栈来保存临时变量，每调用一个新的函数，都会将临时变量封装为栈帧，压入内存栈，等函数执行完成后，再将栈帧出栈，所以，如果递归求解的数据规模很大，调用层次很深，一直往函数栈里添加数据，就会塞满函数栈，导致堆栈溢出。

如何避免出现堆栈溢出呢？**可以通过在代码中限制递归调用的最大深度**。

假设限制递归深度为1000，则修改后代码：

```csharp
static int depth = 0;

public static int Fibonaci(uint n)
{
    depth++;

    if (depth > 1000) throw new Exception("超出递归范围！");

    if (n > 0 && n <= 2) return 1;

    return Fibonaci(n - 1) + Fibonaci(n - 2);
}
```
## 递归的重复计算问题

除堆栈溢出问题外，编写递归还会出现重复计算的问题，例如上述斐波那契数列的递归，在执行时就有重复计算的问题。

例如，当计算 `Fibonaci(5)` 的时候，需要计算 `Fibonaci(4)` 和 `Fibonaci(3)`，而计算 `Fibonaci(4)` 又需要计算 `Fibonaci(3)` 和 `Fibonaci(2)`，以此类推。因此，`Fibonaci(3)` 这个值就被计算了两次，`Fibonaci(2)` 这个值就被计算了三次。

为了避免重复，可以使用字典将计算过的值存储下来，当递归调用到已经计算过的值时，直接从字典中取值并返回，这样就省掉了重复计算。

将上文中的代码再进行优化：

```csharp
static int depth = 0;

static Dictionary<uint, int> ValuePairs = new Dictionary<uint, int>();

public static int Fibonaci(uint n)
{
    depth++;

    if (depth > 1000) throw new Exception("超出递归范围！");

    if (n > 0 && n <= 2) return 1;

    if (ValuePairs.ContainsKey(n))
    {
        return ValuePairs[n];
    }

    var res = Fibonaci(n - 1) + Fibonaci(n - 2);

    ValuePairs.Add(n, res);

    return res;
}
```

## 将递归代码改写为非递归代码

使用递归编程有利有弊，递归编程的好处是使用递归编写的代码的表达能力强，写起来简洁，而递归编程的劣势是空间复杂度高，且存在堆栈溢出和重复计算的问题，因此，在实际开发过程中，可以根据实际情况来决定是是否使用递归实现，例如可以将上述的斐波那契数列的代码改为非递归代码，如下所示：

```csharp
public static int Fibonaci(uint n)
{

    if (n > 0 && n <= 2) return 1;

    int prev = 1;

    int prev_prev = 1;

    int result = 0;
    
    for (int i = 2; i < n; i++)
    {
        result = prev + prev_prev;

        prev_prev = prev;

        prev = result;
    }

    return result;
}

```

所有递归算法都可以改写为迭代循环的非递归写法吗？

是，理论上所有递归算法都可以改写为迭代循环的非递归写法。这是因为递归算法本质上是一个函数在自己内部不断调用自己，而迭代循环可以通过变量的更新来达到相同的效果。

具体来说，可以通过使用一个栈或队列等数据结构来模拟递归函数的调用过程。每当递归函数需要调用自身时，将当前的参数值和程序计数器等信息保存到栈或队列中，然后继续执行下一个语句。当递归函数返回时，从栈或队列中弹出保存的信息，恢复之前的状态，并继续执行之前被中断的语句。

虽然理论上可以将所有递归算法改写为迭代循环的非递归写法，但实际上有些算法可能更适合使用递归实现，而另一些算法则更适合使用迭代循环实现。例如，递归算法通常在树形结构的遍历和图形搜索等算法中使用，而迭代循环则更适合处理数值计算等需要大量循环迭代的算法。


## 总结 

递归式一种高效，简洁的编码模式，只要满足递归的3个条件，就可以使用递归算法去实现。不过，递归代码比较难写，难理解。编写递归代码的关键是不要试图去模拟计算机递归调用的过程，正确的编写方式是写出递推公式，找出终止条件，然后"翻译"为代码。

递归也有它自己的弊端，比如堆栈溢出，重复计算，函数调用耗时多和空间复杂度高，所以在编写递归算法代码时，要避免出现这些问题。


> 参考资料
> 
> [1] 数据结构与算法之美 / 王争 著. --北京：人民邮电出版社，2021.6