递归

当n=0, 1的时候, 结果正确.
假设函数对于n是正确的, 函数对n+1结果也正确.
如果这两点是成立的，我们知道这个函数对于所有可能的n都是正确的。

你必须要示范如何解决问题的一般情况, 通过将问题切分成有限小并更小的子问题.
你必须要示范如何通过有限的步骤, 来解决最小的问题(基本用例).
如果这两件事完成了, 那问题就解决了. 因为递归每次都将问题变得更小, 而一个有限的问题终究会被解决的, 而最小的问题仅需几个有限的步骤就能解决。

汉诺塔程序：
你首先要坚信：大的问题只要能被分解为小的问题，小的问题可以被解决，那么这都不是事，只要时间足够多，问题终究还是可以被解决的。当我们有n个盘子的时候，我们试着将其分解为n-1个盘子的问题。

unsigned int Cnt = 0;

typedef enum{ A=1,B,C} ZHUZI;

void HanoiMove(ZHUZI from,ZHUZI to)
{
    printf(" Move %d to %d \n",from,to);
    Cnt++;
}

//num:移动的盘子数量
//from:盘子所在的杆子
//helper:盘子转移过程借助的杆子
//to:盘子要转移的目的杆子
void Hanoi(unsigned int num,ZHUZI from,ZHUZI helper,ZHUZI to)
{
    if(num==1)
    {
        HanoiMove(from,to);
    }
    else
    {
        Hanoi(num-1,from,to,helper);
        HanoiMove(from,to);
        Hanoi(num-1,helper,from,to);
    }
}

每次只分裂单个分支

• 阶乘

int factorial(int n){
    if(n == 1)
        return 1;
    else
      return n * factorial(n - 1);
}

• 链表求和

int sum_list(struct list_node *l){
    if(l == NULL)
        return 0;
    return l.data + sum_list(l.next);
}

• 计算字符串的长度

size_t length(const char *str) {
  if (*str == 0) {
    return 0;
  }
  return length(++str) + 1;
}

• 融合链表

struct ListNode {
    int val;
    struct ListNode *next;
};
//使用递归的方法，先去头结点
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) 
{
    //任一个为空，返回另外一个
    if (l1==NULL)
    {
        return l2;
    } 

    if(l1==NULL)
    {
        return l1;
    }


    if (l1->val>l2->val)
    {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } 
    else
    {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

• 抱着抱着抱着抱着抱着小鲤鱼的我的我的我的我的我

抱着抱着抱着抱着抱着小鲤鱼的我的我的我的我的我

void GetFish(char num)
{
    printf("抱着");

    if (num==1)
    {
        printf("小鲤鱼");
    }
    else
    {
        GetFish(num-1);
    }

    printf("的我");
}

int _tmain(int argc, _TCHAR* argv[])
{   
    printf("吓得我抱起了：\n");
    GetFish(5);
    printf("\n");

    system("pause");
    return 0;
}

• 挖金游戏

//金矿数量
#define NUM_GOLD_MIND 5
UINT32 G[NUM_GOLD_MIND+1] = {0,500,300,350,300,200};
UINT32 P[NUM_GOLD_MIND+1] = {0,5,5,5,4,3};
bool GoldMindChoice[NUM_GOLD_MIND+1];

//挖金游戏
UINT32 DigGoldRecursion(UINT32 NbrOfMid,UINT32 NbfOfPerson)
{
    UINT32 Dig,unDig;

    if(NbrOfMid==0)
    {
        return 0;
    }

    if (NbfOfPerson<P[NbrOfMid])
    {
        //不挖
        GoldMindChoice[NbrOfMid] = false;
        return  DigGoldRecursion(NbrOfMid-1,NbfOfPerson);
    } 
    else
    {
        //挖
         Dig =  DigGoldRecursion(NbrOfMid-1,NbfOfPerson-P[NbrOfMid]) + G[NbrOfMid];
         unDig = DigGoldRecursion(NbrOfMid-1,NbfOfPerson);

         if(unDig<Dig)
         {
             GoldMindChoice[NbrOfMid] = true;
             return Dig;
         }
         else
         {
             GoldMindChoice[NbrOfMid] = false;
             return unDig;
         }   
    }
}

• 归并排序

ElemType HelpBuff[SIZE];

//归并
void Merge(ElemType DataBuff[],UINT32 low,UINT32 mid,UINT32 high)
{
    UINT32 i=low,j=mid+1,m = mid,n = high,k=0;

    //归并到缓冲区MergeHelpBuff
    while (i<=m&&j<=n)
    {
        if (DataBuff[i]<=DataBuff[j])
        {
            HelpBuff[k++] = DataBuff[i++];
        }
        else
        {
            HelpBuff[k++] = DataBuff[j++];
        }
    }

    //
    while (i<=m)
    {
        HelpBuff[k++] = DataBuff[i++];
    }

    while (j<=n)
    {
        HelpBuff[k++] = DataBuff[j++];
    }

    for (i=0;i<k;i++)
    {
        DataBuff[low+i] =HelpBuff[i];
    }
}

//归并排序
void MergeSort(ElemType Buff[],UINT32 low,UINT32 high)
{
    if (low<high)
    {
        UINT32 mid = (low+high)/2;
        MergeSort(Buff,low,mid);
        MergeSort(Buff,mid+1,high);
        Merge(Buff,low,mid,high);
    }
}

可以使用递归的情形

1. 链表和树等递归定义的数据结构相关的算法

尾递归