如何思考递归

那我们怎么判断这个递归计算是否是正确的呢？Paul Graham 提到一种方法，如下：

如果下面这两点是成立的，我们就知道这个递归对于所有的 n 都是正确的。
当 n=0,1 时，结果正确；
假设递归对于 n 是正确的，同时对于 n+1 也正确。

这种方法很像数学归纳法，也是递归正确的思考方式，上述的第 1 点称为基本情况，第 2 点称为通用情况。

在递归中，我们通常把第 1 点称为终止条件，因为这样更容易理解，其作用就是终止递归，防止递归无限地运行下去。

分治法设计思想

对于一个输入规模为n的函数或问题，用某种方法把输入分割成k(1k个相似的子问题；
分别求解这k个子问题，得出k个问题的子解;再用某种方法把它们组合成原来问题的解；
若子问题还相当大，则可以反复使用分治法，直至最后所分得的子问题足够小，以至可以直接求解为止。

常见的解决问题有：斐波那契数列，汉诺塔问题等
举个例子：如绘制标尺，标出两段，找到中点并将其标出，然后同样的操作作用于标尺的左半部分和右半部分。

#include 
const int len=66;   
const int divs=6;   
void subdivide(char ar[],int low,int high,int level);   
using namespace std;   
int main()   
{   
    char ruler[len];   
    int i;   
    for(i=1;i-2;i++)   
        ruler[i]=' ';   
    ruler[len-1]='\0';   
    int max=len-2;   
    int min=0;   
    ruler[min]=ruler[max]='|';   
    cout<endl;   
    for(i=1;i<=divs;i++)   
    {   
        subdivide(ruler,min,max,i);   
        cout<endl;   
        for(int j=1;j-2;j++)   
            ruler[j]=' ';   
    }   
    return 0;   

}   

void subdivide(char ar[],int low,int high,int level)   
{   
    if(level==0)   
        return;   
    int mid=(high+low)/2;   
    ar[mid]='|';   
    subdivide(ar,low,mid,level-1);   
    subdivide(ar,mid,high,level-1);   
}

后置递归设计思想

假如某个问题的求解过程可以分成若干步进行，并且当前这一步的解可以直接求得，则先求出当前这一步的解，对于余下的问题，若问题的性质和原问题类似，则又可递归求解。

后置递归算法的典型举例:删除单链表中所有值为x的数据元素

分析:

1)单链表是一种顺序结构，必须从第一个结点起，逐个检查每个结点的数据元素;

2)从另一角度看，链表又是一个递归结构，若L是带头结点线性链表(a1,a2,¼, an)的头指针，则 L->next是线性链表(a2,¼, an)的头指针。

回溯法

回溯法是一种“穷举搜索”方法。其基本思想为:

假设问题的解为 n 元组 (x1, x2, …, xn)；
如果n 元组的部分解为 (x1, x2, …, xi) (i
对于已求得的部分解 (x1, x2, …, xi) ，若在添加 xi+1 之后仍然满足约束条件，则得到一个新的部分解 (x1, x2, …, xi+1) ；之后继续添加 xi+2并检查之；
若找不到一个xi+1满足约束条件，则从当前部分解中删去xi, 回溯到前一个部分解(x1,x2, × × ×,xi-1 ),重新添加那些尚未考察过的xi，并检查之；
如此反复进行，直至求得满足约束条件的问题的解，或者证明问题无解；

设四皇后问题的解为 (x1, x2, x3, x4), 其中:

xi (i=1,2,3,4) ，约束条件为: 其中任意两个xi 和xj不能位于棋盘的同行、同列及同对角线.

皇后问题回溯算法关键:

搜索策略: 深度优先，依次取 xi=1,2,3,4;

约束条件: xi和xj不位于棋盘的同行、同列及同对角线上；

终止条件: 找到满足条件的x1,x2 x3,x4；即:i=n

回溯条件: 在当前初始条件下无解；无解: 回溯到了起始状态,i=0；

void Trial(int i, int n) {
  // 进入本函数时，在n×n棋盘前i-1行已放置了互不攻
  // 击的i-1个棋子。现从第 i 行起继续为后续棋子选择 
  // 满足约束条件的位置。当求得(i>n)的一个合法布局
  // 时，输出之。i 的初始值为1。
  if(i=0)  无解；
  if (i>n) 输出棋盘的当前布局;                //终止
  else  for (j=1;  j<=n; ++j) {                     //试探策略
      在第 i 行第 j 列放置一个棋子;
      if (当前布局合法) Trial(i+1, n); //约束-递归
      移去第 i 行第 j 列的棋子;          //回溯
  }        
} // Trial

递归注意事项

1.先写出问题求解的递归定义,包括两项内容:

基本项:描述一个或几个递归过程的终结状态；
归纳项:描述如何从当前状态到下一状态的转换；

2 写递归函数时注意:

严格定义函数的功能和接口;
将每一个递归看成一个简单的操作;
切忌想得太深太远！

3.分析递归算法的工具是递归树，从递归树上可以得到递归函数的各种相关信息。

递归树的深度即为递归函数的递归深度
递归树上的结点数目恰为函数中的主要操作重复进行的次数；
若递归树蜕化为单支树或者递归树中含有很多相同的结点，则表明该递归函数不适用。比如fib(n) = fib(n-1)+fib(n-2)

在这种情况下会重复计算很多比n小的值得fib值，重复太多！！！
所以这种情况下用迭代会更适合一些！！！

我的实践

找到与之相连的联通域

#include "pch.h"
#include 
using namespace std;
void search_dynamic_region(int *p, int x, int y,int row,int col) {
    for (int i = -1; i < 2; i++) {
        for (int j = -1; j < 2; j++) {
            if (x + i >= 0 && x + i < row &&
                y + j >= 0 && y + j < col &&
                p[(x + i)*row + y + j] == 1) {
                p[(x + i)*row + y + j] = 2;
                search_dynamic_region(p, x + i, y + j, row, col);
            }    
        }
    }
}
int main()
{
    int ROW = 10,COL = 10;
    int s[10][10] = { {0,0,0,0,0,0,0,0,0,0},
                         {0,0,0,0,0,0,0,0,0,0},
                         {0,0,0,0,1,2,0,0,0,0},
                         {0,0,0,0,1,1,0,0,0,0},
                         {0,0,0,0,1,0,0,0,0,0},
                         {0,0,0,0,0,0,0,0,0,0},
                         {0,0,0,0,0,0,0,0,0,0},
                         {0,0,0,0,0,1,0,0,1,2},
                         {0,0,0,0,0,1,1,0,1,1},
                         {0,0,0,0,0,0,0,0,1,0} };
    int str[] = {  0,0,0,0,0,0,0,0,0,0,
                    0,0,0,0,0,0,0,0,0,0,
                    0,0,0,0,1,0,0,0,0,0, 
                    0,0,0,1,1,0,0,0,0,0, 
                    0,0,0,1,1,1,2,0,0,0, 
                    0,0,0,0,0,0,0,0,0,0, 
                    0,0,0,0,0,0,0,0,0,0, 
                    0,0,0,2,1,0,0,1,1,0, 
                    0,0,0,0,1,0,0,1,1,2, 
                    0,0,0,0,0,0,0,0,0,2};

    for (int i = 0; i < ROW; i++)
    {
        for (int j = 0; j < COL; j++)
        {
            //一维数组的方式
            //if (str[i*ROW + j] == 2)
            //    search_dynamic_region(str, i, j,ROW,COL);
            //二维数组的方式
            if(s[i][j]==2)
                search_dynamic_region((int*)s, i, j, ROW, COL);
        }
    }
}

输出结果如下：

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 2 2 0 0 0 0
0 0 0 0 2 2 0 0 0 0
0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 2 2
0 0 0 0 0 1 1 0 2 2
0 0 0 0 0 0 0 0 2 0