递归算法经典实例小结(C#实现)

递归算法经典实例小结(C#实现)

递归算法是一种在函数定义中使用函数自身的方法，在计算机科学中被广泛应用于解决复杂问题。本文将通过Fibonacci数列、阶乘计算、汉诺塔问题和排列组合等经典实例，深入剖析递归算法的实现原理和应用场景。

一、递归算法简介

在数学与计算机科学中，递归是指在函数的定义中使用函数自身的方法。递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。

递归算法解决问题的特点：

• (1) 递归就是在过程或函数里调用自身。
• (2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
• (3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
• (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。在实际编程中尤其要注意栈溢出问题。

借助递归方法，我们可以把一个相对复杂的问题转化为一个与原问题相似的规模较小的问题来求解，递归方法只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。但在带来便捷的同时，也会有一些缺点，也即：通常用递归方法的运行效率不高。

二、Fibonacci数列和阶乘

1. Fibonacci数列

提到递归，我们可能会想到的一个实例便是斐波那契数列。斐波那契数列就是如下的数列：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …，总之，就是第N(N > 2)个数等于第(N - 1)个数和(N - 2)个数的和。用递归算法实现如下：

public static int Fibonacci(int n)
{
    if (n < 0) return -1;
    if (n == 0) return 0;
    if (n == 1) return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

2. 阶乘

还有就是求一个数的阶乘，也会用到递归，这个比较简单，直接给出实现代码：

三、汉诺塔问题

汉诺塔是根据一个传说形成的数学问题：

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

1. 每次只能移动一个圆盘；
2. 大盘不能叠在小盘上面。
   提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。
   问：如何移？最少要移动多少次？

下面是汉诺塔的递归求解实现(C#代码)：

public static void hannoi(int n, string from, string buffer, string to)
{
    if (n == 1)
    {
        Console.WriteLine("Move disk " + n + " from " + from + " to " + to);
    }
    else
    {
        hannoi(n - 1, from, to, buffer);
        Console.WriteLine("Move disk " + n + " from " + from + " to " + to);
        hannoi(n - 1, buffer, from, to);
    }
}

其运行结果如图(大家可以跟上面的gif图片对比一下)：

四、排列组合

1. 输出任意个数字母、数字的全排列

对于一个长度为n的串或者n个字符(数字、节点)组成的字符串数组，它的全排列共有A(n, n)=n!种。这个问题也是一个递归的问题。如1,2,3，全排列可得到：{123,132,213,231,312,321}。

用递归算法实现代码如下：

public static void Permutation(string[] nums, int m, int n)
{
    string t;
    if (m < n - 1)
    {
        Permutation(nums, m + 1, n);
        for (int i = m + 1; i < n; i++)
        {
            //可抽取Swap方法
            t = nums[m];
            nums[m] = nums[i];
            nums[i] = t;
            Permutation(nums, m + 1, n);
            //可抽取Swap方法
            t = nums[m];
            nums[m] = nums[i];
            nums[i] = t;
        }
    }
    else
    {
        for (int j = 0; j < nums.Length; j++)
        {
            Console.Write(nums[j]);
        }
        Console.WriteLine();
    }
}

调用代码如下：

static void Main(string[] args)
{
    Nums = new string[] { "a", "b", "c" };
    Permutation(Nums, 0, Nums.Length);
    Console.ReadKey();
}

这里传入一个string数组，abc三个字母来测试，输出如下图：

2. 将全排列结果保存到链表中

有时候，我们需要将全排列的结果保存，然后做其他的处理，我们可以将结果保存到一个链表中。我们定义如下类作为链表的节点，代码如下：

public class Node
{
    public string value { get; set; }
    public Node nextNode { get; set; }
    public Node(string value)
    {
        this.value = value;
        this.nextNode = null;
    }
}

此时声明全局变量，如下：

public static List<Node> NodeList = new List<Node>();

这个时候，我们修改Permutation方法，如下：

public static void Permutation(string[] nums, int m, int n)
{
    string t;
    if (m < n - 1)
    {
        Permutation(nums, m + 1, n);
        for (int i = m + 1; i < n; i++)
        {
            //可抽取Swap方法
            t = nums[m];
            nums[m] = nums[i];
            nums[i] = t;
            Permutation(nums, m + 1, n);
            //可抽取Swap方法
            t = nums[m];
            nums[m] = nums[i];
            nums[i] = t;
        }
    }
    else
    {
        Node root = null;
        Node currentNode;
        for (int j = 0; j < nums.Length; j++)
        {
            currentNode = new Node(nums[j]);
            currentNode.nextNode = root;
            root = currentNode;
        }
        NodeList.Add(root);
    }
}

这样，我们执行了Permutation方法后，就将结果保存到链表中了。用的时候，我们只要遍历NodeList就可以了。如图：

递归算法就先说到这里了。谈到算法，就必需提数据结构，看来真的要“学到老了”~~