遞歸

alphahans 發布于2019-08-20 12:14 / 1119人閱讀

摘要：遞歸概念遞歸是一種針對簡單循環難以編程實現的問題，通過函數調用自身，提供優雅解決方案的技術。擁有基礎情況或終止條件來停止遞歸。這個稱之為遞歸調用。為了避免重新創建字符串，使用遞歸輔助方法來進行改良。

遞歸概念

遞歸是一種針對簡單循環難以編程實現的問題，通過函數調用自身，提供優雅解決方案的技術。

遞歸都具有以下三個要點：

使用 if-else 或 switch 語句來引導不同的情況。

擁有基礎情況（base case）或終止條件（stopping condition）來停止遞歸。

每次遞歸調用都會簡化原始問題，讓它不斷接近基礎情況，所以可以用不同的參數調用自身方法，直到它變為這種基礎情況。這個稱之為遞歸調用（recursive call）。

示例，計算階乘

if(n == 0){ // base case
  return 0;
}else { // recursive call
  return n * factorial(n-1)
}

遞歸的優勢－－斐波那契數列

計算階乘很容易使用循環改寫，某些情況下，用循環不容易解決的問題可以利用遞歸給出一個直觀簡單的解法。

斐波那契數列從 0 到 1 開始，之后的每個數都是序列中的前兩個數之和，通過遞歸可以簡單的實現出來。

var count = 0;

function fib(n) {
    count++;
    if(n == 0){
        return 0;
    }else if(n == 1){
        return 1;
    }else {
        return fib(n-1) + fib(n-2);
    }
}

const result = fib(10);

console.log("result",result);
console.log("count",count);
// result 55
// count 177

程序中會出現很多重復調用，求第 10 個斐波那契數，就調用了 177 次自身函數，如果嘗試求出更大的斐波那契數，那么相應的調用次數就會急劇的增加。

優化遞歸調用

將計算過的斐波那契值存起來，可以優化遞歸調用。通過改良，求第 10 個斐波那契數，只調用的 11 次自身函數。而且調用自身函數的次數永遠是，n + 1 次，n 代表第 n 個需求的斐波那契數。

var count = 0;
const calculated = [];

function fib(n) {
    count++;

    if(n == 0){
        return 0;
    }else if(n == 1){
        return 1;
    }else {
        if(!calculated[n-1]){
            calculated[n-1] = fib(n-1);
        }

        if(!calculated[n-2]){
            calculated[n-2] = fib(n-2);
        }
        return calculated[n-1] + calculated[n-2];
    }

}

const result = fib(10);

console.log("result",result);
console.log("count",count);
// result 55
// count 11

遞歸輔助方法

有時候可以通過找到一個要解決的初始問題的類似問題，來找到初始問題的解決方案。這個類似的方法稱之為遞歸輔助方法。

舉例，如果一個字符串從左讀和從右讀都是一樣的，那么他就是一個回文串（palindrome）。可以通過下面的函數判斷。

function palindrome(str) {
    if(str.length <= 1 ){
        return true;
    }else if(str[0] !== str[str.length - 1]){
        return false;
    }else {
        return palindrome(str.slice(1,-1));
    }
}

const result = palindrome("ffffdffffd");

console.log(result); // ture

每次調用 palindrome 方法時，都會使用 str.slice 來創建一個新的字符串。
為了避免重新創建字符串，使用遞歸輔助方法 isPalindrome 來進行改良。

function isPalindrome(str) {
    return palindrome(str,0,str.length-1);
}

function palindrome(str,low,high) {

    if(low >= high){
        return true;
    }else if(str[low] !== str[high]){
        return false;
    }else {
        low ++;
        high --;
        return palindrome(str,low,high);
    }
}

const result = isPalindrome("ffffdaaaerffffd");

console.log(result); // false

云服務器 GPU云服務器樹形遞歸遞歸編程遞歸打印遞歸訪問

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/80873.html

js算法入門（3）--遞歸

摘要：在遞歸過程中，未完成計算的函數將會掛起壓入調用堆棧，不然遞歸結束的時候沒辦法進行回溯。這就引出了回溯法回溯法就是在達到遞歸邊界前的某層，由于一些事實導致已經不需要前往任何一個子問題遞歸，就可以直接返回上一層。 1簡介遞歸在前端開發中應用還是非常廣泛的，首先DOM就是樹狀結構，而這種結構使用遞歸去遍歷是非常合適的。然后就是對象和數組的深復制很多庫也是使用遞歸實現的例如jquery中的e...

jzman 2019-08-22 16:31 評論0 收藏0
數據結構與算法之精講「遞歸系列」

摘要：終止條件遞推公式遞歸的分類通過做大量的題，根據遞歸解決不同的問題，引申出來的幾種解決和思考的方式。我們通過層與層之間的計算關系用遞推公式表達出來做計算，經過層層的遞歸，最終得到結果值。 showImg(https://segmentfault.com/img/remote/1460000019222330); 前言幾個月之前就想寫這樣一篇文章分享給大家，由于自己有心而力不足，沒有把真...

zhichangterry 2019-08-26 13:50 評論0 收藏0
【C語言】玩轉遞歸——學好遞歸，你需要掌握的知識！

摘要：所以，遞歸在編程中同樣是很重要的一個知識點。舉個例子用遞歸實現求第個斐波那契數。總結起來四個字大事化小繼續舉斐波那契數的例子三遞歸是怎樣運行的我們通過一道題目來講解。 ...

Donne 2021-09-09 09:33 評論0 收藏0
對于遞歸的傲慢與偏見

摘要：對于函數調用開銷，可以利用尾遞歸來解決，不過目前的引擎并沒有實現對尾遞歸的優化，所以最開始我以為遞歸沒有理由比非遞歸更快。遞歸與堆棧非遞歸的算法使用一個堆棧來實現。最近刷leetcode 79題 Word Search需要用到DFS算法，由于是刷leetcode，心想不能用遞歸，影響效率，于是利用stack完成。之后又利用遞歸（使用cache）實現了一次，結果竟然是遞歸的算法比非遞歸...

Labradors 2019-08-23 12:58 評論0 收藏0
遞歸，就是這么簡單

摘要：簡而言之，遞歸就是自己調用自己，但是這個調用它是有一定條件的，比如子問題須與原始問題為同樣的事，且更為簡單。當時，這層遞歸返回，也就是返回到的這層遞歸。這時，至此，遞歸結束，返回結果給調用方。 showImg(https://segmentfault.com/img/bVbvZRe?w=1242&h=735); 什么是遞歸？維基百科給出了如下定義：程序調用自身的編程技巧稱為遞歸.遞...

woshicixide 2019-08-19 10:21 評論0 收藏0
遞歸函數的執行

摘要：遞歸一個函數可以指向并調用自身。這是的一個獨特的用法，在這個結構下無法替代，出錯但我們可以用下面這種方式，把遞歸函數賦值給一個變量遞歸(Recursion) 一個函數可以指向并調用自身(call itself)。有三種方法可以達到這個目的：函數名 arguments.callee 作用域下的一個指向該函數的變量名上述概念引用自MDN，對遞歸概念不清楚的可以自行查看；遞歸函數...

tomato 2019-08-21 11:37 評論0 收藏0