胡思亂想說遞歸-上

原來在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的時候,學(xué)習(xí)到遞歸侧戴,當(dāng)時覺得遞歸就是一種自己調(diào)用自己的方法嘛,只要控制好遞歸的結(jié)束條件就可以了跌宛⌒锼危可是在工作之后才發(fā)現(xiàn),對于很多問題疆拘,采用遞歸的思想可以大大降低實現(xiàn)的難度(暫時先不考慮效率)蜕猫,所以決定好好的研究一下遞歸。

什么是遞歸

遞歸方法對應(yīng)于數(shù)學(xué)上的歸納法哎迄,把一個想要解決的問題轉(zhuǎn)化為解決他的子問題回右,子問題又可以繼續(xù)轉(zhuǎn)化為子問題的子問題,這些子問題與原問題有著相同的結(jié)構(gòu)或者說有著相同的模型漱挚。當(dāng)然了這些子問題并不是可以無限分解的翔烁,使的問題不能繼續(xù)分解下去的條件被我們稱為遞歸結(jié)束條件。

遞歸從大的方面旨涝,分為兩個步驟:遞和歸蹬屹。把問題分解為子問題的過程屬于"遞",到達(dá)了遞歸結(jié)束條件,使得子問題出棧的過程屬于"歸"

一般的遞歸都分為:

  1. 結(jié)束條件
  2. 直接求解表達(dá)式慨默。就是在到達(dá)結(jié)束條件的時候贩耐,我們可以直接用來求解的表達(dá)式
  3. 步進(jìn)表達(dá)式和歸納項。之所以把這兩個合為一個厦取,是因為這兩個經(jīng)常會一起用潮太。步進(jìn)表達(dá)式是可以使得遞歸可以繼續(xù)向下分解的表達(dá)式。歸納項是只在這一次遞歸過程中蒜胖,我們對于該子問題的處理邏輯消别。

一般遞歸的形式如下:

public void fun(factor){
    if(end){
        //end就是遞歸的結(jié)束條件
        //directResolve()就是直接求解表達(dá)式抛蚤,在很多時候我們僅僅是想要終止遞歸台谢,并不需要子問題返回值,所以這時候可以沒有直接求解表達(dá)式岁经,直接return
        directResolve();
    }else{
        //這就是歸納項朋沮,對于本次遞歸我們要處理的邏輯
        doSomething(factor);
        //這個就是不進(jìn)表達(dá)式,通過不斷改變factor的值來使遞歸向著終止條件靠近
        factor=move(factor);
        //調(diào)用自身缀壤,實現(xiàn)遞歸
        fun(factor);
    }
}

遞歸的例子

舉個最簡單的例子樊拓,那就不得不說求N的階乘


public static int factorial(int n){
    //n就是步進(jìn)因子
    if(n == 1){
        //n==1是遞歸終止條件
        //return 1是直接求解表達(dá)式
        return 1;
    }
    //以下這一句n-1是步進(jìn)表達(dá)式
    //n*factorial(n-1)是歸納項
    //這就是為什么上面說歸納項和步進(jìn)表達(dá)式經(jīng)常在一起
    return n * factorial(n - 1);
}

通過上面的例子,我們可以總結(jié)出來可以使用遞歸處理的問題的一些共同特征:

  1. 可以把該問題逐步分解為一個個的小問題塘慕,而且這些小問題與原問題有相同的結(jié)構(gòu)或者說表述
  2. 存在某種條件筋夏,使得問題不能繼續(xù)分解,并且在該條件下問題可以得到非常容易的解決图呢。

只要滿足著兩個條件条篷,就可以采用遞歸的辦法來解決

接下來舉一個比較復(fù)雜的問題:

有這么一個數(shù)據(jù),全部由數(shù)字構(gòu)成蛤织,比如字符串"123456",或者整形123456赴叹,甚至可以是數(shù)組[1,2,3,4,5,6](為了演示的方便,我把他當(dāng)做字符串)指蚜。任意刪除其中的T位乞巧,比如刪除其中的兩位,剩余的數(shù)字按照原來的順序排列摊鸡,求一個算法绽媒,使得刪除之后的數(shù)字的值最小。
比如"123456",可以刪除3和6,得到"1245",也可以刪除1和2免猾,得到"3456"是辕,我們要求得刪除之后最小的那個數(shù),這里為"1234"掸刊。

就這樣一個問題免糕,網(wǎng)上有很多的解法,這里我說一下遞歸的解法。

這個問題可以概括為:一個N位數(shù)字石窑,刪除T位牌芋,剩余的按原來的順序求值,求剩余數(shù)字的最小值松逊。
按照遞歸的思路躺屁,求N位數(shù)字,刪除T位经宏,可以先求出N-1位數(shù)字刪除T-1位犀暑,求出最小值,然后N-2位刪除T-2位烁兰,求出最小值耐亏,一次類推,當(dāng)N=0或者T=0的時候結(jié)束遞歸沪斟。

按照上面思路給出代碼:

public static String findMin(String value, int T){
    final int N = value.lenght();
    if(N<=T||N<=0||T<=0){
        //這是遞歸終止條件
        return value;
    }

    String result = value;
    for(int i = 0;i<N;i++){
        //一次刪除value中的每一位广辰,其余的位數(shù)按原來的順序組合,得到一個N-1位的數(shù)字主之,然后遞歸求出這N-1位刪除T-1的最小值
        String tmp = value.subString(0,i)+value.subString(i+1,N);
        String temResult = findMin(tmp,T-1);
        if(Integer.valueOf(result)>Integer.valueOf(tmpResult)){
            result = tmpResult;
        }
    }
    return result;
}

這個的思想是每次遞歸都找到最小的择吊,當(dāng)T減小到0的時候就正好可以求出刪除T位的時候最小數(shù)字。
比如槽奕,當(dāng)value為"312456",T為2時几睛,返回"1245"

這也是遞歸和循環(huán)結(jié)合使用的一個比較不錯的例子

有一個二分查找法,也是遞歸比較經(jīng)典的使用粤攒。

題目就不說了所森,現(xiàn)在來說一下它的解法思想:把已經(jīng)排序好的要查找的數(shù)字二分,比較中間數(shù)字與目標(biāo)的大小琼讽,如果中間數(shù)字比目標(biāo)大必峰,則說明要查找的在前一部分,然后繼續(xù)對前一部分使用相同的辦法钻蹬,下面來寫一下方法吼蚁。

//假設(shè)data已經(jīng)排序過了,如果找到了,就返回該key第一次出現(xiàn)的位置问欠,否則返回-1
    public static int binarySearch(int[] data, int start, int end, int key){
        int mid = (start+end)/2;
        final int N = data.length;
        if(end<=start){
            //遞歸終止條件
            if(data[start] == key){
                return mid;
            }else{
                return -1;
            }
        }

        //歸納項
        if(data[mid]>key){
            return binarySearch(data,start,mid,key);
        }else if(data[mid]<key){
            return binarySearch(data,mid+1,end,key);
        }else{
            return mid;
        }
    }
}

上半部分就說到這里肝匆。下一部分說一下 遞歸,迭代和循環(huán)顺献,以及尾遞歸的問題

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末旗国,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子注整,更是在濱河造成了極大的恐慌能曾,老刑警劉巖度硝,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異寿冕,居然都是意外死亡蕊程,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進(jìn)店門驼唱,熙熙樓的掌柜王于貴愁眉苦臉地迎上來藻茂,“玉大人,你說我怎么就攤上這事玫恳”娲停” “怎么了?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵京办,是天一觀的道長掀序。 經(jīng)常有香客問我,道長臂港,這世上最難降的妖魔是什么森枪? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任视搏,我火速辦了婚禮审孽,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘浑娜。我一直安慰自己佑力,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布筋遭。 她就那樣靜靜地躺著打颤,像睡著了一般。 火紅的嫁衣襯著肌膚如雪漓滔。 梳的紋絲不亂的頭發(fā)上编饺,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天,我揣著相機(jī)與錄音响驴,去河邊找鬼透且。 笑死,一個胖子當(dāng)著我的面吹牛豁鲤,可吹牛的內(nèi)容都是我干的秽誊。 我是一名探鬼主播,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼琳骡,長吁一口氣:“原來是場噩夢啊……” “哼锅论!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起楣号,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤最易,失蹤者是張志新(化名)和其女友劉穎怒坯,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體藻懒,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡敬肚,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了束析。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片艳馒。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖员寇,靈堂內(nèi)的尸體忽然破棺而出弄慰,到底是詐尸還是另有隱情,我是刑警寧澤蝶锋,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布陆爽,位于F島的核電站,受9級特大地震影響扳缕,放射性物質(zhì)發(fā)生泄漏慌闭。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一躯舔、第九天 我趴在偏房一處隱蔽的房頂上張望驴剔。 院中可真熱鬧,春花似錦粥庄、人聲如沸丧失。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽布讹。三九已至,卻和暖如春训堆,著一層夾襖步出監(jiān)牢的瞬間描验,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工坑鱼, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留膘流,地道東北人。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓姑躲,卻偏偏與公主長得像睡扬,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子黍析,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容