递归模型

将一个问通过递归来解决的思路是：

　　1. 将原问题不断分解为相同模型的子问题。

　　2. 寻找边界条件，当不满足边界条件则继续分解问题，满足则开始求解。 

eg：

　　1.求和

　　　　

 　　　　　　模型：

　　　　　　　　　　1. 将原问题不断分解为相同模型的子问题(前N项和可以分解为n加上n-1的前n-1项和 Sum(n) -> n + Sum(n-1))。

　　　　　　　　　　2. 寻找边界条件，当不满足边界条件则继续分解问题 (n > 1)，满足则开始求解 (n == 1)。 

　　　　　　实现：

unsigned int sum(unsigned int n)
{
    if(n != 1)
    {
        return (n + sum(n -1));
    }
    else
    {
        return 1;
    }
}

　　2. 求斐波那契数

　　　　

 　　　　　　模型：

　　　　　　　　　　1. 将原问题不断分解为相同模型的子问题 （一个下标对应的斐波那契数为前两个斐波那契数之和 fac(n) -> fac(n-1) + fac(n-2))。

　　　　　　　　　　2. 寻找边界条件，当不满足边界条件则继续分解问题 ，满足则开始求解 (n == 1 || n == 2)。 

 　　　　　　实现：

unsigned int fac(unsigned int n)
{
    if(n > 2)
    {
        return (fac(n - 1) + fac(n - 2));
    }
    else if((n == 1) || (n == 2))
    {
        return 1
    }
    return 0;
}

　　3. 求字符串长度

　　　　　　

  　　　　　　模型：

　　　　　　　　　　1. 将原问题不断分解为相同模型的子问题 （ 一个字符串长度分解为首字符加剩余字符长度strlen(s) -> 1 + strlen(s-1) ）。

　　　　　　　　　　2. 寻找边界条件，当不满足边界条件则继续分解问题（没有遍历到''） ，满足则开始求解 (遍历到'')。 

　　　　　　 实现：

unsigned int strlen(unsigned char* str)
{
    unsigned int len = 0; 
    if(*str != '')
    {
        return (1 + strlen(str));        
    }
    else
    {
        return 0;
    }
}

unsigned int strlen(unsigned char* str)
{
    return str ? (*str ? (1 + strlen(str)) : 0) : 0;
}

　

反转链表：

Node *list_reverse(Node *list)
{
    if(list == NULL && list->next == NULL)
    {
        return list;
    }
    else
    {
        Node *slide = list->next;
        Node *ret = list_reverse(list->next);
        list->next = NULL;
        slide->next =list;
        return ret;
    }
}

合并链表：

Node *list_merge(Node* list_1, Node* list_2)
{
    if(list_1 == NULL)
    {
        return list_2;
    }
    if(list_2 == NULL)
    {
        return list_1;
    }
    if(list_1->vlaue < list_2->value)
    {
        Node* list_1_slide = list_1->next;
        Node* ret = list_merge(list_1_slide, list_2);
        list_1->next = ret;
        return list_1;
        // return (list_1->next = list_merge(list_1->next, list_2), list_1);
    }
    else if(list_1->vlaue > list_2->value || list_1->vlaue == list_2->value)
    {
        Node* list_2_slide = list_2->next;
        Node* ret = list_merge(list_1, list_2_slide);
        list_2->next = ret;
        return list_2;
        // return (list_2->next = list_merge(list_1, list_2->next), list_2);
    }
}

　　

汉诺塔

void HanoiTower(int n, char a, char b, char c)// a:src b:mid c:dest
{
    if(n == 1)
    {
        cout << a << --> << b << endl;
    }
    else
    {
        HanoiTower(n - 1, a, c, b);
        HanoiTower(1, a, b, c);
        HanoiTower(n - 1, b, a, c;)
    }
}

全排列：

八皇后：

　　1.创建9*9的边界，边界值为2，空白值为0，放置皇后值为1.

　　2. 每一个cell检测其是否可以放置皇后的是检测(-1,-1)(0,-1)(1,-1)三个方向是否有皇后

　　3. 以检测一行哪个位置适合放置皇后为基础，当出现当前行没有皇后位则返回上一行重新寻找下一个皇后位。

 　　

template <int SIZE>
    class EightQueuen : public TopClass
{
protected:
    enum{ N = SIZE + 2};
    struct cell : public TopClass
    {
        cell(int x = 0, int y = 0) : px(x), py(y) {}
        int px;
        int py;
    };    

    int chessboard[N][N];
    LinkList<cell> m_solution;
    int m_count = 0;

    void init()
    {
        for(int x = 0; x < N; x += N - 1)
        {
            for(int y = 0; y < N ; y++)
            {
                chessboard[x][y] = 2;
                chessboard[y][x] = 2;
            }
        }
        for(int x = 1; x < N - 1; x++)
        {
            for(int y = 1; y < N - 1; y++)
            {
                chessboard[x][y] = 0;
            }
        }
    }
    
    void show_resolution()
    {
        for(m_solution.move(0); !m_solution.end(); m_solution.next())
        {
            cout << "(" << m_solution.current().px << "," << m_solution.current().py << ") " ;
        }
        cout << endl;

        for(int y = 0; y < N; y++)
        {
            for(int x = 0; x < N; x++)
            {
                cout << chessboard[x][y];
            }
            cout << endl;
        }
        cout << endl;
    }

    bool cell_check(int x, int y)
    {
        bool ret = 1, flag = 1,flag1,flag2,flag3;
        int temp_x = x, temp_y = y;
        int dir_1 = 0, dir_2 = 0, dir_3 = 0;

        do{
            temp_x = temp_x + (-1);
            temp_y = temp_y + (-1);
            flag = (chessboard[temp_x][temp_y] == 0);
        }while(flag);
        flag1 = (chessboard[temp_x][temp_y] == 2);

        temp_x = x;
        temp_y = y;
        do{
            temp_x = temp_x + (0);
            temp_y = temp_y + (-1);
            flag = (chessboard[temp_x][temp_y] == 0);
        }while(flag);
        flag2 = (chessboard[temp_x][temp_y] == 2);

        temp_x = x;
        temp_y = y;
        do{
            temp_x = temp_x + (1);
            temp_y = temp_y + (-1);
            flag = (chessboard[temp_x][temp_y] == 0);
        }while(flag);
        flag3 = (chessboard[temp_x][temp_y] == 2);

        return (flag1 && flag2 && flag3);
    }

    bool line_check(int y)
    {
        if(y <= SIZE)
        {
            for(int x = 1; x <= SIZE; x++)
            {
                if(cell_check(x,y))
                {
                    chessboard[x][y] = 1;
                    m_solution.insert(cell(x,y));
                    line_check(y + 1);
                    chessboard[x][y] = 0;
                    m_solution.remove(m_solution.length() - 1);
                }
            }
        }
        else
        {
            show_resolution();
            m_count++;
        }
    }

public:
    EightQueuen()
    {
        init();
    }

    void process()
    {
        line_check(1);
        cout << "Total Solution = " << m_count << endl;
    }
};


int main(void)
{
    EightQueuen<8> eq;
    eq.process();
    return 0;
}