递归思想

观察递归，我们会发现，递归的数学模型其实就是归纳法，这个在高中的数列里面是最常用的了。回忆一下归纳法。

归纳法适用于想解决一个问题转化为解决他的子问题，而他的子问题又变成子问题的子问题，而且我们发现这些问题其实都是一个模型，也就是说存在相同的逻辑归纳处理项。当然有一个是例外的，也就是递归结束的哪一个处理方法不适用于我们的归纳处理项，当然也不能适用，否则我们就无穷递归了。这里又引出了一个归纳终结点以及直接求解的表达式。

如果运用列表来形容归纳法就是：

步进表达式：问题蜕变成子问题的表达式
结束条件：什么时候可以不再是用步进表达式
直接求解表达式：在结束条件下能够直接计算返回值的表达式
逻辑归纳项：适用于一切非适用于结束条件的子问题的处理，当然上面的步进表达式其实就是包含在这里面了。
这样其实就结束了，递归也就出来了。

递归算法的一般形式：

void func( mode){   
    if(endCondition){
        constExpression       //基本项  
    }
    else{
        accumrateExpreesion /归纳项
        mode=expression //步进表达式
        func(mode) / /调用本身，递归
    }
}

一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进;当边界条件满足时，递归返回。
注意：

(1) 递归就是在过程或函数里调用自身;
(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。

递归应用

递归算法一般用于解决三类问题：

(1)数据的定义是按递归定义的。（Fibonacci函数）
(2)问题解法按递归算法实现。（回溯）
(3)数据的结构形式是按递归定义的。（树的遍历，图的搜索）

递归的缺点

递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
停止的位置称为基线条件（base case）。基线条件是递归程序的最底层位置，在此位置时没有必要再进行操作，可以直接返回一个结果。所有递归程序都必须至少拥有一个基线条件，而且必须确保它们最终会达到某个基线条件；否则，程序将永远运行下去，直到程序缺少内存或者栈空间。

颠倒栈

题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。
我们再来考虑怎么递归。我们把栈{1, 2, 3, 4, 5}看成由两部分组成：栈顶元素1和剩下的部分{2, 3, 4, 5}。如果我们能把{2, 3, 4, 5}颠倒过来，变成{5, 4, 3, 2}，然后在把原来的栈顶元素1放到底部，那么就整个栈就颠倒过来了，变成{5, 4, 3, 2, 1}。
接下来我们需要考虑两件事情：一是如何把{2, 3, 4, 5}颠倒过来变成{5, 4, 3, 2}。我们只要把{2, 3, 4, 5}看成由两部分组成：栈顶元素2和剩下的部分{3, 4, 5}。我们只要把{3, 4, 5}先颠倒过来变成{5, 4, 3}，然后再把之前的栈顶元素2放到最底部，也就变成了{5, 4, 3, 2}。
至于怎么把{3, 4, 5}颠倒过来……很多读者可能都想到这就是递归。也就是每一次试图颠倒一个栈的时候，现在栈顶元素pop出来，再颠倒剩下的元素组成的栈，最后把之前的栈顶元素放到剩下元素组成的栈的底部。递归结束的条件是剩下的栈已经空了。

这种思路的代码如下：

template<typename T> void ReverseStack(std::stack<T>& stack)
{
    if(!stack.empty())
    {
        T top = stack.top();
        stack.pop();
        ReverseStack(stack);
        AddToStackBottom(stack, top);
    }
}

我们需要考虑的另外一件事情是如何把一个元素e放到一个栈的底部，也就是如何实现AddToStackBottom。这件事情不难，只需要把栈里原有的元素逐一pop出来。当栈为空的时候，push元素e进栈，此时它就位于栈的底部了。然后再把栈里原有的元素按照pop相反的顺序逐一push进栈。
注意到我们在push元素e之前，我们已经把栈里原有的所有元素都pop出来了，我们需要把它们保存起来，以便之后能把他们再push回去。我们当然可以开辟一个数组来做，但这没有必要。由于我们可以用递归来做这件事情，而递归本身就是一个栈结构。我们可以用递归的栈来保存这些元素。

基于如上分析，我们可以写出AddToStackBottom的代码：

// Add an element to the bottom of a stack:
template<typename T> void AddToStackBottom(std::stack<T>& stack, T t)
{
    if(stack.empty())
    {
        stack.push(t);
    }
    else
    {
        T top = stack.top();
        stack.pop();
        AddToStackBottom(stack, t);
        stack.push(top);
    }
}

素数

返回100以内的素数个数问题

struct prime_number_node
{
    int prime_number;
    prime_number_node* next;
};
int calc_prime_number()
{
    prime_number_node* list_head = new prime_number_node();
    list_head->next = NULL;
    list_head->prime_number = 2;
    prime_number_node* list_tail = list_head;
    for(int number = 3 ; number < 100 ; number++)
    {
        int remainder;
        prime_number_node* cur_node_ptr = list_head;
        while(cur_node_ptr != NULL)
        {
            remainder = number%cur_node_ptr->prime_number;
            if(remainder == 0)
            {
                //1 break;
            }
            else
            {
                //2 cur_node_ptr = cur_node_ptr->next;
            }
        }
        if(remainder != 0)
        {
            prime_number_node* new_node_ptr = new prime_number_node();
            new_node_ptr->prime_number = number;
            new_node_ptr->next = NULL;
            list_tail->next = new_node_ptr;
            //3 list_tail = list_tail->next;
        }
    }
    int result = 0;
    while(list_head != NULL)
    {
        result++;
        prime_number_node* temp_ptr = list_head;
        list_head = list_head->next;
        //4 delete temp_ptr;
    }
    return result;
}

这里直接求 list_head 和 list_tail 的差即可

字符串的排列

题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
我们以三个字符abc为例来分析一下求字符串排列的过程。首先我们固定第一个字符a，求后面两个字符bc的排列。当两个字符bc的排列求好之后，我们把第一个字符a和后面的b交换，得到bac，接着我们固定第一个字符b，求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍然是和原先处在第一位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处在第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列。

既然我们已经知道怎么求三个字符的排列，那么固定第一个字符之后求后面两个字符的排列，就是典型的递归思路了。

void Permutation(char* pStr, char* pBegin)
{
      if(!pStr || !pBegin)
            return;
      // if pBegin points to the end of string,
      // this round of permutation is finished,
      // print the permuted string
      if(*pBegin == '\0')
      {
            printf("%s\n", pStr);
      }
      // otherwise, permute string
      else
      {
            for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)
            {
                  // swap pCh and pBegin
                  char temp = *pCh;
                  *pCh = *pBegin;
                  *pBegin = temp;
                  Permutation(pStr, pBegin + 1);
                  // restore pCh and pBegin
                  temp = *pCh;
                  *pCh = *pBegin;
                  *pBegin = temp;
            }
      }
}

字符串的组合

题目：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。
假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；而是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。

下面是这种思路的参考代码：

void Combination(char* string)
{
   if(string == NULL)
       return;
   int length = strlen(string);
   vector<char> result;
   for(int i = 1; i <= length; ++ i)
   {
       Combination(string, i, result);
   }
}
void Combination(char* string, int number, vector<char>& result)
{
   if(number == 0)
   {
       vector<char>::iterator iter = result.begin();
       for(; iter < result.end(); ++ iter)
           printf("%c", *iter);
           printf("\n");
           return;
   }
   if(*string == '\0')
       return;
   result.push_back(*string);
   Combination(string + 1, number - 1, result);
   result.pop_back();
   Combination(string + 1, number, result);
}

由于组合可以是1个字符的组合，2个字符的字符……一直到n个字符的组合，因此在函数void Combination(char* string)，我们需要一个for循环。另外，我们一个vector来存放选择放进组合里的字符。

memcpy默认实现

void *memcpy1(void *desc, const void *src, size_t size)
{
    if((desc == NULL) && (src == NULL))
    {
        return NULL;
    }
    unsigned char *desc1 = (unsigned char*)desc;
    unsigned char *src1 = (unsigned char*)src;
    while(size-- >0)
    {
        *desc1 = *src1;
        desc1++;
        src1++;
    }
    return desc;
}

memcpy升级版本-处理重叠

标准memcpy()的解释：

1 2	void memcpy(void dst, const void *src, size_t n); //If copying takes place between objects that overlap, the behavior is undefined.

注意下面的注释，对于地址重叠的情况，该函数的行为是未定义的。

另外，标准库也提供了地址重叠时的内存拷贝函数：memmove()，那么为什么还要考虑重写memcpy()函数呢?

因为memmove()函数的实现效率问题，该函数把源字符串拷贝到临时buf里，然后再从临时buf里写到目的地址，增加了一次不必要的开销。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void *Memcpy(void *dst, const void *src, size_t size);
int main(int argc, char *argv[])
{
    char buf[100] = "abcdefghijk";
    //memcpy(buf+2, buf, 5);
    Memcpy(buf+2, buf, 5);
    printf("%s\n", buf+2);
}
void *Memcpy(void *dst, const void *src, size_t size)
{
    char *psrc;
    char *pdst;
    if(NULL == dst || NULL == src)
    {
        return NULL;
    }
    if((src < dst) && (char *)src + size > (char *)dst) // 自后向前拷贝
    {
        psrc = (char *)src + size - 1;
        pdst = (char *)dst + size - 1;
        while(size--)
        {
            *pdst-- = *psrc--;
        }
    }
    else
    {
        psrc = (char *)src;
        pdst = (char *)dst;
        while(size--)
        {
            *pdst++ = *psrc++;
        }
    }
    return dst;
}

使用Memcpy()的结果:

abcdehijk

使用memcpy()的结果:

abadehijk