遞歸

alphahans 發(fā)布于2019-08-20 12:14 / 1163人閱讀

摘要：遞歸概念遞歸是一種針對(duì)簡(jiǎn)單循環(huán)難以編程實(shí)現(xiàn)的問(wèn)題，通過(guò)函數(shù)調(diào)用自身，提供優(yōu)雅解決方案的技術(shù)。擁有基礎(chǔ)情況或終止條件來(lái)停止遞歸。這個(gè)稱之為遞歸調(diào)用。為了避免重新創(chuàng)建字符串，使用遞歸輔助方法來(lái)進(jìn)行改良。

遞歸概念

遞歸是一種針對(duì)簡(jiǎn)單循環(huán)難以編程實(shí)現(xiàn)的問(wèn)題，通過(guò)函數(shù)調(diào)用自身，提供優(yōu)雅解決方案的技術(shù)。

遞歸都具有以下三個(gè)要點(diǎn)：

使用 if-else 或 switch 語(yǔ)句來(lái)引導(dǎo)不同的情況。

擁有基礎(chǔ)情況（base case）或終止條件（stopping condition）來(lái)停止遞歸。

每次遞歸調(diào)用都會(huì)簡(jiǎn)化原始問(wèn)題，讓它不斷接近基礎(chǔ)情況，所以可以用不同的參數(shù)調(diào)用自身方法，直到它變?yōu)檫@種基礎(chǔ)情況。這個(gè)稱之為遞歸調(diào)用（recursive call）。

示例，計(jì)算階乘

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

遞歸的優(yōu)勢(shì)－－斐波那契數(shù)列

計(jì)算階乘很容易使用循環(huán)改寫(xiě)，某些情況下，用循環(huán)不容易解決的問(wèn)題可以利用遞歸給出一個(gè)直觀簡(jiǎn)單的解法。

斐波那契數(shù)列從 0 到 1 開(kāi)始，之后的每個(gè)數(shù)都是序列中的前兩個(gè)數(shù)之和，通過(guò)遞歸可以簡(jiǎn)單的實(shí)現(xiàn)出來(lái)。

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

程序中會(huì)出現(xiàn)很多重復(fù)調(diào)用，求第 10 個(gè)斐波那契數(shù)，就調(diào)用了 177 次自身函數(shù)，如果嘗試求出更大的斐波那契數(shù)，那么相應(yīng)的調(diào)用次數(shù)就會(huì)急劇的增加。

優(yōu)化遞歸調(diào)用

將計(jì)算過(guò)的斐波那契值存起來(lái)，可以優(yōu)化遞歸調(diào)用。通過(guò)改良，求第 10 個(gè)斐波那契數(shù)，只調(diào)用的 11 次自身函數(shù)。而且調(diào)用自身函數(shù)的次數(shù)永遠(yuǎn)是，n + 1 次，n 代表第 n 個(gè)需求的斐波那契數(shù)。

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

遞歸輔助方法

有時(shí)候可以通過(guò)找到一個(gè)要解決的初始問(wèn)題的類似問(wèn)題，來(lái)找到初始問(wèn)題的解決方案。這個(gè)類似的方法稱之為遞歸輔助方法。

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

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

每次調(diào)用 palindrome 方法時(shí)，都會(huì)使用 str.slice 來(lái)創(chuàng)建一個(gè)新的字符串。
為了避免重新創(chuàng)建字符串，使用遞歸輔助方法 isPalindrome 來(lái)進(jìn)行改良。

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