[IMUDGES内部培训]递归

发布于 2018-11-04  49 次阅读


今天我们主要介绍深度优先搜索和广度优先搜索这两种算法,在此之前我们要先了解递归,栈和队列. 
栈和队列上节课已经讲过了.

栈(Stack)是支持 push 和 pop 两种操作的数据结构。 push 是在栈的顶端放入一组数据的操作。反之, pop 是从其顶端取出一组数据的操作。因此,最后进入栈的一组数据可以最先被取出(这种行为被叫做LIFO: Last In First Out,即后进先出)。

队列

队列(Queue)与栈一样支持 push 和 pop 两个操作。但与栈不同的是, pop 完成的不是取出最顶端的元素,而是取出最底端的元素。也就是说最初放入的元素能够最先被取出(这种行为被叫做FIFO:First In First Out,即先进先出)。

用stl实现即可

什么是递归

什么是递归呢? 要理解递归,就得先了解什么是递归,实际上这句话就是一个递归.

在一个函数中再次调用该函数自身的行为叫做递归,这样的函数被称作递归函数。例如,我们想要编写一个计算阶乘的函数 int fact(int n) ,当然,用循环来实现也是可以的。但是根据阶乘的递推式n!=n×(n-1)!,我们可以写成如下形式:

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

我们再来试试编写计算斐波那契数列的函数 int fib(int n) 
大家自己写一下

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
int memo[MAX_N + 1];
int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

这种方法是出于记忆化搜索或者动态规划的想法

讲点原理

函数的递归调用和普通函数调用是一样的。当程序执行到某个函数时,将这个函数进行入栈操作,在入栈之前,通常需要完成三件事。 
  1、将所有的实参、返回地址等信息传递给被调函数保存。 
  2、为被调函数的局部变量分配存储区。 
  3、将控制转移到北调函数入口。 
当一个函数完成之后会进行出栈操作,出栈之前同样要完成三件事。 
  1、保存被调函数的计算结果。 
  2、释放被调函数的数据区。 
  3、依照被调函数保存的返回地址将控制转移到调用函数。 
递归太深会栈溢出

顺带讲个技巧:一些大数组开在函数外面,作为全局变量

经典例题

八皇后 IMUDGES OJ 1905

#include<iostream>
using namespace std;
int flag[3][30],sum,n;
void find(int a)
{
    if (a == n)
    {
        sum++;
        return;
    }
    for (int i = 0; i < n; i++)
    {
        if (flag[0][i] || flag[1][a + i] || flag[2][a - i + n]) continue;
            flag[0][i] = flag[1][a + i] = flag[2][a - i + n] = 1;
            find(a + 1);
            flag[0][i] = flag[1][a + i] = flag[2][a - i + n] = 0;
    }
}
int main()
{
    cin >> n;
    find(0);
    cout << sum;
}