資訊專欄INFORMATION COLUMN
摘要：在之前的文章中我們學(xué)習(xí)了幾種常見的數(shù)據(jù)結(jié)構(gòu)，接下來我們先了解一下遞歸思想，為我們后面學(xué)習(xí)樹和圖奠定一定的基礎(chǔ)。而如果一直調(diào)用自己的話，最終會導(dǎo)致棧溢出從而導(dǎo)致程序崩潰，這是程序員不想發(fā)生的問題之一。
在之前的文章中我們學(xué)習(xí)了幾種常見的數(shù)據(jù)結(jié)構(gòu)，接下來我們先了解一下遞歸思想，為我們后面學(xué)習(xí)樹和圖奠定一定的基礎(chǔ)。
遞歸 理解遞歸遞歸是一種解決問題的方法。通俗點來講，其核心思想就是函數(shù)自己調(diào)用自己，或者間接調(diào)用自身。而如果一直調(diào)用自己的話，最終會導(dǎo)致棧溢出從而導(dǎo)致程序崩潰，這是程序員不想發(fā)生的問題之一。那么要使用遞歸，就必須遵循的他的一些注意點。首先要注意的是，每個遞歸函數(shù)都有基線條件，也就是不再發(fā)生遞歸的停止點。還有，既然傳遞值或者函數(shù)到?？臻g，那么我們就有好習(xí)慣，將不用的或者需要的空間進(jìn)行返回。也可以這樣理解，遞歸其實就是傳遞和歸還。下面一段簡單的代碼進(jìn)行展示。
function understandRecursion(doIunderstandRecursion) {
const recursionAnswer = confirm("Do you understand recursion?"); // function logic
if (recursionAnswer === true) { // base case or stop point
return true;
}
understandRecursion(recursionAnswer); // recursive call
}
understandRecursion(false);//continue
understandRecursion(false);//continue
understandRecursion(true);//stop
一些經(jīng)典遞歸算法
階乘
function factorialIterative(number) {
if (number < 0) {
return undefined;
}
let total = 1;
for (let n = number; n > 1; n--) {
total = total * n;
}
return total;
}
function factorial(n) {
// console.trace();
if (n === 1 || n === 0) {
return 1;
}
return n * factorial(n - 1);
}
值得注意的是，由于操作系統(tǒng)和瀏覽器的不同，提供的?？臻g不同，也就是棧溢出發(fā)生時函數(shù)的執(zhí)行次數(shù)不同，并且在ES6中提供的是尾調(diào)用優(yōu)化，函數(shù)內(nèi)最后一個操作是調(diào)用函數(shù)時，會通過跳轉(zhuǎn)指令jump而不是子程序調(diào)用，導(dǎo)致程序可以一直進(jìn)行。所以在這里，基線條件是萬萬不能忘了添加的。
斐波那契數(shù)列function fibonacciIterative(n){
let fibNMinus2 = 0;
let fibNMinus1 = 1;
let fibN = n;
for (let i = 2; i <= n; i++) { // n >= 2
fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
fibNMinus2 = fibNMinus1;
fibNMinus1 = fibN;
}
return fibN;
}
遞歸實現(xiàn)
function fibonacciIterative(n){
let fibNMinus2 = 0;
let fibNMinus1 = 1;
let fibN = n;
for (let i = 2; i <= n; i++) { // n >= 2
fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
fibNMinus2 = fibNMinus1;
fibNMinus1 = fibN;
}
return fibN;
}
function fibonacciMemoization(n) {
const memo = [0, 1];
const fibonacci = (n) => {
if (memo[n] != null) return memo[n];
return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
};
return fibonacci(n);
}
總結(jié)
迭代版本比遞歸版本快很多，但是遞歸版本更容易理解，需要的代碼通常更少。使用遞歸有些算法不用，因為尾調(diào)用優(yōu)化會造成多余的內(nèi)存消耗，甚至可能會被清除。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/109980.html
摘要：終止條件遞推公式遞歸的分類通過做大量的題，根據(jù)遞歸解決不同的問題，引申出來的幾種解決和思考的方式。我們通過層與層之間的計算關(guān)系用遞推公式表達(dá)出來做計算，經(jīng)過層層的遞歸，最終得到結(jié)果值。 showImg(https://segmentfault.com/img/remote/1460000019222330); 前言 幾個月之前就想寫這樣一篇文章分享給大家，由于自己有心而力不足，沒有把真...
摘要：一冒泡排序算法介紹比較相鄰的兩個元素如果前一個比后一個大，則交換位置。它與冒泡排序的不同之處在于，它會優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序的核心在于間隔序列的設(shè)定。作為一種線性時間復(fù)雜度的排序，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。 一、冒泡排序 算法介紹： 比較相鄰的兩個元素,如果前一個比后一個大，則交換位置。 第一輪把最大的元素放到了最后面。 由于每次排序最后一個都是最大的，...
摘要：八皇后問題是十九世紀(jì)著名的數(shù)學(xué)家高斯年提出。同時可以擴展為九皇后，十皇后問題。解決方案回溯與遞歸。這樣，編譯器或者解釋器就可以把尾遞歸做優(yōu)化，使遞歸本身無論調(diào)用多少次，都只占用一個棧幀，不會出現(xiàn)棧溢出的情況。 八皇后問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出 。以下為python語言的八皇后代碼，摘自《Python基礎(chǔ)教程》，代碼相對于其他語言，來得短小且一次性可以打印出92種結(jié)果。...
摘要：動態(tài)規(guī)劃法用表示最大子數(shù)組的結(jié)束下標(biāo)為的情形，則對于，有這樣就有了一個子結(jié)構(gòu)，對于初始情形，遍歷就能得到這個數(shù)組，其最大者即可最大子數(shù)組的和。動態(tài)規(guī)劃法想法巧妙，運行效率也高，但是沒有普遍的適用性。 問題簡介 ??本文將介紹計算機算法中的經(jīng)典問題——最大子數(shù)組問題（maximum subarray problem）。所謂的最大子數(shù)組問題，指的是：給定一個數(shù)組A，尋找A的和最大的非空連續(xù)...
閱讀 678·2023-04-26 02:03
閱讀 1045·2021-11-23 09:51
閱讀 1159·2021-10-14 09:42
閱讀 1750·2021-09-13 10:23
閱讀 973·2021-08-27 13:12
閱讀 850·2019-08-30 11:21
閱讀 1010·2019-08-30 11:14
閱讀 1053·2019-08-30 11:09
