递归与回溯法

递归

---

 

引入

　　什么是递归？先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说……。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之为递归。

　　一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。

递归的概念

• 递归过程是借助于一个递归工作栈来实现的
• 问题向一极推进，这一过程叫做递推；
• 问题逐一解决，最后回到原问题，这一过程叫做回归。
• 递归的过程正是由递推和回归两个过程组成。

　　用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。

递归的应用及实现

　　递归算法在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。就递归算法而言并不涉及高深数学知识，只不过初学者要建立起递归概念不十分容易。

　　我们先从一个最简单的例子导入。

　　求斐波那契数列的第n位（C++代码）：

#include 
using namespace std;

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

int main() {
    int n ;
    cin >> n ;
    printf("斐波那契数列前 %d 项为：\n", n);
    for (int i = 1; i <= n; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");
    return 0;
}

---

回溯法

---

 

回溯法的概念与模板

　　回溯法是一种常用的算法，它主要用于解决一些组合优化问题，例如八皇后问题、0/1背包问题等。回溯法的基本思想是：从问题的某一种状态开始，搜索所有可能的情况，直到找到符合要求的解为止。

　　回溯法的实现过程通常采用递归的方式，每次递归都会尝试一种可能的情况，如果这种情况不符合要求，就回溯到上一层递归，尝试其它的情况。在回溯的过程中，需要记录已经尝试过的情况，以避免重复计算。

　　回溯法的时间复杂度通常比较高，因为它需要搜索所有可能的情况。但是，在一些特殊的情况下，回溯法可以通过剪枝等优化技巧来提高效率。

　　回溯法是一种常用的算法思想，可以用于解决很多问题，比如八皇后问题、0/1背包问题等。下面是一个用C语言实现回溯法的模板：

#include 

#define MAX_N 100 // 最大的问题规模

int n; // 问题规模
int a[MAX_N]; // 存储解的数组

// 检查当前解是否合法
int check(int cur) {
    // TODO: 根据具体问题实现
}

// 回溯函数
void backtrack(int cur) {
    if (cur == n) { // 找到一个解
        // TODO: 处理解的代码
        return;
    }
    for (int i = 0; i < n; i++) { // 枚举当前位置的所有可能取值
        a[cur] = i; // 尝试将当前位置设为i
        if (check(cur)) { // 如果当前解合法
            backtrack(cur + 1); // 继续搜索下一个位置
        }
    }
}

int main() {
    // TODO: 读入问题规模n和其它必要的输入
    backtrack(0); // 从第0个位置开始搜索
    return 0;
}

在实际使用中，需要根据具体问题实现check函数和处理解的代码。

八皇后问题

　　下面是一个八皇后问题的回溯法实现：

#include 
using namespace std;

const int N = 8;
int queen[N]; // 存放每一行皇后所在的列号

bool check(int row, int col) // 判断当前位置是否可以放置皇后
{
    for (int i = 0; i < row; i++)
    {
        if (queen[i] == col || abs(row - i) == abs(col - queen[i]))
            return false;
    }
    return true;
}

void backtrack(int row) // 回溯函数
{
    if (row == N) // 找到一组解
    {
        for (int i = 0; i < N; i++)
            cout << queen[i] << " ";
        cout << endl;
        return;
    }

    for (int col = 0; col < N; col++) // 枚举当前行所有可能的列
    {
        if (check(row, col)) // 如果当前位置可以放置皇后
        {
            queen[row] = col; // 记录当前皇后所在的列号
            backtrack(row + 1); // 继续搜索下一行
        }
    }
}

int main()
{
    backtrack(0);
    return 0;
}

　　在上面的代码中，check函数用于判断当前位置是否可以放置皇后，backtrack函数用于搜索所有可能的情况。在搜索过程中，queen数组用于记录每一行皇后所在的列号。

　　回溯法是一种非常实用的算法，它可以解决很多组合优化问题。但是，由于回溯法的时间复杂度较高，因此在实际应用中需要注意优化。

 

                                                                        码字不易，点个赞呗§(*￣▽￣*)§

---

如果您觉得阅读本文对您有帮助，请点一下“推荐”按钮，您的“推荐”将是我最大的写作动力！欢迎各位转载，但是未经作者本人同意，转载文章之后必须在文章页面明显位置给出作者和原文连接，否则保留追究法律责任的权利。

• 递归
•  
•     引入
•     递归的概念
•     递归的应用及实现
• 回溯法
•  
•     回溯法的概念与模板
•     八皇后问题

__EOF__