递归
当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);
}
}
可以使用递归的情形
- 链表和树等递归定义的数据结构相关的算法
