学习笔记---递归

递归算法

释义：在调用一个函数的过程中又出现直接或间接的调用该函数本身，成为函数的递归（recursive）调用。

直接递归：

间接递归：

这两种递归调用，在形式上都是无终止的自身调用（实际解决问题时，可通过设置判断条件来跳出递归循环）

递归求解要点：

1.方法：

.列出递归方程/思路

.写出递归函数

.调用递归函数

2.举例：

数学归纳法

证明一个与自然数n有关的命题P(n)，有如下步骤：

1.证明当n取第一个值a时命题成立（a对于一般数列取值为0或1）

2.假设当n=k(k>=a，k为自然数)时命题成立，证明当n=k+1时命题也成立。

例：对于求n的阶乘

可分为以上两种思路：阶乘和递归

代码示例：

#include <stdio.h>#include <stdlib.h>/*这个程序用来测试通过递归计算n的阶乘*/long fact(int);//因为结束时返回值可能会十分巨大，所以使用long作为返回值数据类型int main(){    int n;    PRintf("输入需要求阶乘的n：");    scanf("%d",&n);    printf("%d的阶乘是：%ld",n,fact(n));    return 0;}long fact(int n){    long f;    if(n==1)//通过判断n的值决定是否递归，避免无限循环        f=1;    else        f=n*fact(n-1);//调用自身，形成递归    return f;}结果：
解析：
程序中用if语句来控制，只有在某一条件成立时才继续执行递归调用，否则就不再继续，这样，不会出现无终止的递归调用。
递归技巧
代码示例1：
#include <stdio.h>#include <stdlib.h>/*这个程序用来测试递归的技巧*//*输入一个整数m,要求输出其反序数以及正序数*/void f1(int);//输出反序数void f2(int);//输出正序数int main(){    int m;    printf("输入m：");    scanf("%d",&m);    f1(m);    printf("/n");    f2(m);    printf("/n");    return 0;}void f1(int m){    if(m>0)    {        /*先输出，后递归*/        printf("%d",m%10);        f1(m/10);    }}void f2(int m){    if(m>0)    {        /*先递归，后输出*/        f2(m/10);        printf("%d",m%10);    }}
结果：
解析：
1.如上，改变递归的位置，得到的结果将是完全相反的。深刻理解这个例子的原理，即可理解递归的规律。
代码示例2：
#include <stdio.h>#include <stdlib.h>/*用递归实现二分查找*/int r_search(int[],int,int,int);int main(){    int arr[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};    int low=0,high=14,k;    do{        printf("输入希望查找的数,输入-1结束:/n");        scanf("%d",&k);        if(k==-1)            break;        int i=r_search(arr,low,high,k);        if(i>=0)            printf("在数组的第%d位找到该数，该数为：%d!/n",i,arr[i]);        else            printf("未找到该数!/n");    }while(1);    return 0;}int r_search(int arr[],int low,int high,int k){    int i,mid;    if(low>high)        i=-1;//如果已经例遍了整个数组    else    {        mid=(low+high)/2;        if(arr[mid]==k)            i=mid;//如果中间值等于期望值        else if(arr[mid]>k)            i=r_search(arr,low,mid-1,k);//如果中间值大于期望值        else            i=r_search(arr,mid+1,high,k);//如果中间值小于期望值    }    return i;}结果：
解析：
递归可以取代循环完成很多功能，而递归的代码往往更加简洁。
代码示例3：
#include <stdio.h>#include <stdlib.h>/*这个程序用递归思想来解决汉诺塔问题*//*汉诺塔问题有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动?*/static long count=0;//计数变量void move(int,char,char,char);//核心函数int main(){    char a='A',b='B',c='C';//三根柱子    printf("输入汉诺塔层数：");    int n;    scanf("%d",&n);    move(n,a,b,c);    printf("/n总共使用了%ld步",count);    return 0;}/*注意！move函数中用到的所有a,b,c都是形参！在递归过程中，a代表的可能是字符A也可能是字符B、C！b和c也同理*//*如要理解这个函数，可通过单步调试，设置n为4以内的较小的数进行测试*/void move(int n,char a, char b,char c){    if(n==1)    {        count++;        printf("%c-->%c/n",a,c);//如果现在的问题时把一个盘子从a移动到c，那么直接做就行了。不需要进一步分化问题        return;    }    move(n-1,a,c,b);//要把n个盘子经过b从a移动到c，首先要把最底下最大的那个盘子之上的n-1个盘子经过c从a移动到b。    count++;    printf("%c-->%c/n",a,c);//现在a上只有一个盘子了，直接将他移动到c即可    move(n-1,b,a,c);//现在情况是，a上没有盘子，且要把剩下的盘子从b移动到c。（类比b上没有盘子，要把盘子从a移动到c。可以进入下一次递归）}结果：
解析：
1.汉诺塔问题是递归的经典应用，通过这个问题也能更加深刻的理解递归。但递归并不是解决这个问题的最佳方案。
2.如果要输出每一步移动的轨迹，应当使用递归。但如果只要输出移动所需步数，则应当使用迭代！
以下是使用迭代计算汉诺塔、麦子问题的代码示例，与本篇主旨无关。
代码示例：
#include <stdio.h>#include <stdlib.h>/*麦子问题舍罕王打算奖赏国际象棋的发明人──宰相西萨·班·达依尔。国王问他想要什么，他对国王说：“陛下，请您在这张棋盘的第1个小格里赏给我一粒麦子，在第2个小格里给2粒，第3个小格给4粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒，都赏给您的仆人吧！”国王觉得这个要求太容易满足了，就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。请计算共需要多少麦子才能满足其要求。*//*麦子问题和汉诺塔问题是相似的。用这个程序同样可以计算n层汉诺塔的移动总需步数*//*比如输入5,便是5层汉诺塔总共所需移动步数*/int main(){    /*难点在于如何表达一个这么大的数，C语言中long long也不足以做到这一点，但unsigned long long 却刚刚好能做到*/    unsigned long long totol=0,now=1;//这几乎是C语言能表达数字最大的基础数据类型了。    int n;    scanf("%d",&n);    while(n--)    {        totol+=now;        now*=2;    }    printf("%llu",totol);//输出的格式字符串也和一般情况下有所不同    return 0;}结果：
解析：
1.如上，如果用递归来算64层汉诺塔或者64格棋盘的话，需要几天几夜才可能得到结果。而用迭代只需要1秒多一点。
2.unsigned long long 的输出格式字符串是%llu或%I64u(后者的I是大写的i，且后者原用于输出_int64型数据，如今也可用于输出unsigned long long),long long的输出格式字符串是%lld。