遞歸算法

釋義：在調(diào)用一個(gè)函數(shù)的過(guò)程中又出現(xiàn)直接或間接的調(diào)用該函數(shù)本身，成為函數(shù)的遞歸（recursive）調(diào)用。

直接遞歸：

間接遞歸：

這兩種遞歸調(diào)用，在形式上都是無(wú)終止的自身調(diào)用（實(shí)際解決問(wèn)題時(shí)，可通過(guò)設(shè)置判斷條件來(lái)跳出遞歸循環(huán)）

遞歸求解要點(diǎn)：

1.方法：

.列出遞歸方程/思路

.寫(xiě)出遞歸函數(shù)

.調(diào)用遞歸函數(shù)

2.舉例：

數(shù)學(xué)歸納法

證明一個(gè)與自然數(shù)n有關(guān)的命題P(n)，有如下步驟：

1.證明當(dāng)n取第一個(gè)值a時(shí)命題成立（a對(duì)于一般數(shù)列取值為0或1）

2.假設(shè)當(dāng)n=k(k>=a，k為自然數(shù))時(shí)命題成立，證明當(dāng)n=k+1時(shí)命題也成立。

例：對(duì)于求n的階乘

可分為以上兩種思路：階乘和遞歸

代碼示例：

#include <stdio.h>#include <stdlib.h>/*這個(gè)程序用來(lái)測(cè)試通過(guò)遞歸計(jì)算n的階乘*/long fact(int);//因?yàn)榻Y(jié)束時(shí)返回值可能會(huì)十分巨大，所以使用long作為返回值數(shù)據(jù)類(lèi)型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)//通過(guò)判斷n的值決定是否遞歸，避免無(wú)限循環(huán)        f=1;    else        f=n*fact(n-1);//調(diào)用自身，形成遞歸    return f;}結(jié)果：
解析：
程序中用if語(yǔ)句來(lái)控制，只有在某一條件成立時(shí)才繼續(xù)執(zhí)行遞歸調(diào)用，否則就不再繼續(xù)，這樣，不會(huì)出現(xiàn)無(wú)終止的遞歸調(diào)用。
遞歸技巧
代碼示例1：
#include <stdio.h>#include <stdlib.h>/*這個(gè)程序用來(lái)測(cè)試遞歸的技巧*//*輸入一個(gè)整數(shù)m,要求輸出其反序數(shù)以及正序數(shù)*/void f1(int);//輸出反序數(shù)void f2(int);//輸出正序數(shù)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);    }}
結(jié)果：
解析：
1.如上，改變遞歸的位置，得到的結(jié)果將是完全相反的。深刻理解這個(gè)例子的原理，即可理解遞歸的規(guī)律。
代碼示例2：
#include <stdio.h>#include <stdlib.h>/*用遞歸實(shí)現(xiàn)二分查找*/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("輸入希望查找的數(shù),輸入-1結(jié)束:/n");        scanf("%d",&k);        if(k==-1)            break;        int i=r_search(arr,low,high,k);        if(i>=0)            printf("在數(shù)組的第%d位找到該數(shù)，該數(shù)為：%d!/n",i,arr[i]);        else            printf("未找到該數(shù)!/n");    }while(1);    return 0;}int r_search(int arr[],int low,int high,int k){    int i,mid;    if(low>high)        i=-1;//如果已經(jīng)例遍了整個(gè)數(shù)組    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;}結(jié)果：
解析：
遞歸可以取代循環(huán)完成很多功能，而遞歸的代碼往往更加簡(jiǎn)潔。
代碼示例3：
#include <stdio.h>#include <stdlib.h>/*這個(gè)程序用遞歸思想來(lái)解決漢諾塔問(wèn)題*//*漢諾塔問(wèn)題有三根相鄰的柱子，標(biāo)號(hào)為A,B,C，A柱子上從下到上按金字塔狀疊放著n個(gè)不同大小的圓盤(pán)，要把所有盤(pán)子一個(gè)一個(gè)移動(dòng)到柱子B上，并且每次移動(dòng)同一根柱子上都不能出現(xiàn)大盤(pán)子在小盤(pán)子上方，請(qǐng)問(wèn)至少需要多少次移動(dòng)?*/static long count=0;//計(jì)數(shù)變量void move(int,char,char,char);//核心函數(shù)int main(){    char a='A',b='B',c='C';//三根柱子    printf("輸入漢諾塔層數(shù)：");    int n;    scanf("%d",&n);    move(n,a,b,c);    printf("/n總共使用了%ld步",count);    return 0;}/*注意！move函數(shù)中用到的所有a,b,c都是形參！在遞歸過(guò)程中，a代表的可能是字符A也可能是字符B、C！b和c也同理*//*如要理解這個(gè)函數(shù)，可通過(guò)單步調(diào)試，設(shè)置n為4以?xún)?nèi)的較小的數(shù)進(jìn)行測(cè)試*/void move(int n,char a, char b,char c){    if(n==1)    {        count++;        printf("%c-->%c/n",a,c);//如果現(xiàn)在的問(wèn)題時(shí)把一個(gè)盤(pán)子從a移動(dòng)到c，那么直接做就行了。不需要進(jìn)一步分化問(wèn)題        return;    }    move(n-1,a,c,b);//要把n個(gè)盤(pán)子經(jīng)過(guò)b從a移動(dòng)到c，首先要把最底下最大的那個(gè)盤(pán)子之上的n-1個(gè)盤(pán)子經(jīng)過(guò)c從a移動(dòng)到b。    count++;    printf("%c-->%c/n",a,c);//現(xiàn)在a上只有一個(gè)盤(pán)子了，直接將他移動(dòng)到c即可    move(n-1,b,a,c);//現(xiàn)在情況是，a上沒(méi)有盤(pán)子，且要把剩下的盤(pán)子從b移動(dòng)到c。（類(lèi)比b上沒(méi)有盤(pán)子，要把盤(pán)子從a移動(dòng)到c。可以進(jìn)入下一次遞歸）}結(jié)果：
解析：
1.漢諾塔問(wèn)題是遞歸的經(jīng)典應(yīng)用，通過(guò)這個(gè)問(wèn)題也能更加深刻的理解遞歸。但遞歸并不是解決這個(gè)問(wèn)題的最佳方案。
2.如果要輸出每一步移動(dòng)的軌跡，應(yīng)當(dāng)使用遞歸。但如果只要輸出移動(dòng)所需步數(shù)，則應(yīng)當(dāng)使用迭代！
以下是使用迭代計(jì)算漢諾塔、麥子問(wèn)題的代碼示例，與本篇主旨無(wú)關(guān)。
代碼示例：
#include <stdio.h>#include <stdlib.h>/*麥子問(wèn)題舍罕王打算獎(jiǎng)賞國(guó)際象棋的發(fā)明人──宰相西薩·班·達(dá)依爾。國(guó)王問(wèn)他想要什么，他對(duì)國(guó)王說(shuō)：“陛下，請(qǐng)您在這張棋盤(pán)的第1個(gè)小格里賞給我一粒麥子，在第2個(gè)小格里給2粒，第3個(gè)小格給4粒，以后每一小格都比前一小格加一倍。請(qǐng)您把這樣擺滿(mǎn)棋盤(pán)上所有64格的麥粒，都賞給您的仆人吧！”國(guó)王覺(jué)得這個(gè)要求太容易滿(mǎn)足了，就命令給他這些麥粒。當(dāng)人們把一袋一袋的麥子搬來(lái)開(kāi)始計(jì)數(shù)時(shí)，國(guó)王才發(fā)現(xiàn)：就是把全印度甚至全世界的麥粒全拿來(lái)，也滿(mǎn)足不了那位宰相的要求。請(qǐng)計(jì)算共需要多少麥子才能滿(mǎn)足其要求。*//*麥子問(wèn)題和漢諾塔問(wèn)題是相似的。用這個(gè)程序同樣可以計(jì)算n層漢諾塔的移動(dòng)總需步數(shù)*//*比如輸入5,便是5層漢諾塔總共所需移動(dòng)步數(shù)*/int main(){    /*難點(diǎn)在于如何表達(dá)一個(gè)這么大的數(shù)，C語(yǔ)言中l(wèi)ong long也不足以做到這一點(diǎn)，但unsigned long long 卻剛剛好能做到*/    unsigned long long totol=0,now=1;//這幾乎是C語(yǔ)言能表達(dá)數(shù)字最大的基礎(chǔ)數(shù)據(jù)類(lèi)型了。    int n;    scanf("%d",&n);    while(n--)    {        totol+=now;        now*=2;    }    printf("%llu",totol);//輸出的格式字符串也和一般情況下有所不同    return 0;}結(jié)果：
解析：
1.如上，如果用遞歸來(lái)算64層漢諾塔或者64格棋盤(pán)的話，需要幾天幾夜才可能得到結(jié)果。而用迭代只需要1秒多一點(diǎn)。
2.unsigned long long 的輸出格式字符串是%llu或%I64u(后者的I是大寫(xiě)的i，且后者原用于輸出_int64型數(shù)據(jù)，如今也可用于輸出unsigned long long),long long的輸出格式字符串是%lld。