遞歸算法

釋義：在調用一個函數的過程中又出現直接或間接的調用該函數本身，成為函數的遞歸（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。