斐波那契遞歸

fuyi501 發(fā)布于2019-08-21 17:13 / 3347人閱讀

摘要：無路什么數(shù)據(jù)結(jié)構(gòu)最后都是隊棧嗎一行寫出斐波那契數(shù)列改進寫法將找到斐波那契數(shù)列的第項問題轉(zhuǎn)化為在一個初始項為和的加法序列序列中，每一項都是前兩項的和中找到第項的問題。

常規(guī)寫法

const Fib1 = n => {
  console.log(`Fib1(${n})`)
  if (n === 0) {
    return 0
  } else if (n === 1) {
    return 1
  } else {
    return Fib1(n - 1) + Fib1(n - 2)
  }
}

console.log(Fib1(5))
// 函數(shù)調(diào)用順序
// Fib1(5) Fib1(4) Fib1(3) Fib1(2) Fib1(1) Fib1(0) Fib1(1) Fib1(2) Fib1(1) Fib1(0) Fib1(3) Fib1(2) Fib1(1) Fib1(0) Fib1(1)

可以發(fā)現(xiàn)整個過程是二叉樹先序遍歷的過程。此外，整個過程中多次調(diào)用了Fib1(3)、Fib1(2)、Fib1(5)，產(chǎn)生大量冗余的調(diào)用。無路什么數(shù)據(jù)結(jié)構(gòu)最后都是隊棧嗎？

一行寫出斐波那契數(shù)列

const Fib1 = n => (n <= 1) ? n : (Fib1(n - 1) + Fib1(n - 2))

改進寫法1

將找到斐波那契數(shù)列的第n項問題轉(zhuǎn)化為在一個初始項為t0和t1的加法序列（序列中，每一項都是前兩項的和）中找到第n項的問題。

求以3和7為初始項的第一個序列中的t6(71)可以轉(zhuǎn)化為求以7和10為初始項的第二個序列中的t5(71)

const Fib2 = n => {
  return AdditiveSequence(n, 0, 1)
}

const AdditiveSequence = (n, t0, t1) => {
  console.log(`AdditiveSequence(${n},${t0},${t1})`)
  if (n === 0) {
    return t0
  } else if (n === 1) {
    return t1
  } else {
    return AdditiveSequence(n - 1, t1, t0 + t1)
  }
}

console.log(Fib2(5))
// AdditiveSequence(5,0,1)
// AdditiveSequence(4,1,1)
// AdditiveSequence(3,1,2)
// AdditiveSequence(2,2,3)
// AdditiveSequence(1,3,5)

改進寫法2

求以3和7為初始項的第一個序列中的t6(71)可以轉(zhuǎn)化為求以10和17為初始項的第二個序列中的t4(71)

const Fib3 = n => {
  return AdditiveSequence(n, 0, 1)
}

const AdditiveSequence = (n, t0, t1) => {
  console.log(`AdditiveSequence(${n},${t0},${t1})`)
  if (n === 0) {
    return t0
  } else if (n === 1) {
    return t1
  } else {
    return AdditiveSequence(n - 2, t0 + t1, t0 + t1 + t1)
  }
}

console.log(Fib3(5))
// AdditiveSequence(5,0,1)
// AdditiveSequence(3,1,2)
// AdditiveSequence(1,3,5)

云服務(wù)器 GPU云服務(wù)器波那契數(shù)列解斐波樹形遞歸遞歸編程

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/89278.html

相關(guān)文章

js 實現(xiàn)斐波那契數(shù)列(數(shù)組緩存、動態(tài)規(guī)劃、尾調(diào)用優(yōu)化)

摘要：根據(jù)該規(guī)則，返回第個斐波那契數(shù)。尾遞歸函數(shù)調(diào)用自身，稱為遞歸。一個前端眼中的斐波那契數(shù)列解斐波那契數(shù)列的實用解法調(diào)用棧尾遞歸和手動優(yōu)化尾調(diào)用優(yōu)化譯我從用寫斐波那契生成器中學(xué)到的令人驚訝的件事斐波那契數(shù)列是以下一系列數(shù)字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數(shù)字 0 和 1 ...

趙連江 2019-08-23 11:38 評論0 收藏0
遞歸

摘要：遞歸概念遞歸是一種針對簡單循環(huán)難以編程實現(xiàn)的問題，通過函數(shù)調(diào)用自身，提供優(yōu)雅解決方案的技術(shù)。擁有基礎(chǔ)情況或終止條件來停止遞歸。這個稱之為遞歸調(diào)用。為了避免重新創(chuàng)建字符串，使用遞歸輔助方法來進行改良。遞歸概念遞歸是一種針對簡單循環(huán)難以編程實現(xiàn)的問題，通過函數(shù)調(diào)用自身，提供優(yōu)雅解決方案的技術(shù)。遞歸都具有以下三個要點：使用 if-else 或 switch 語句來引導(dǎo)不同的情況。 ...

alphahans 2019-08-20 12:14 評論0 收藏0
使用js實現(xiàn)斐波那契數(shù)列

摘要：前言前幾天面試被問到了斐波那契數(shù)列的實現(xiàn)以及優(yōu)化的問題，當(dāng)時現(xiàn)場卡了挺久的，現(xiàn)在進行一下總結(jié)使用實現(xiàn)。題目介紹斐波那契數(shù)列又被稱為黃金分割數(shù)列，指的是這樣的一個數(shù)列，它有如下遞推的方法定義是正整數(shù)，請使用實現(xiàn)斐波那契函數(shù)。前言前幾天面試被問到了斐波那契數(shù)列的實現(xiàn)以及優(yōu)化的問題，當(dāng)時現(xiàn)場卡了挺久的，現(xiàn)在進行一下總結(jié)（使用js實現(xiàn)）。題目介紹 ??斐波那契數(shù)列又被稱為黃金分割數(shù)列，指...

alexnevsky 2019-08-26 13:36 評論0 收藏0
云課堂作業(yè)---斐波那契數(shù)列的引發(fā)的思索

摘要：閉包尾遞歸循環(huán)迭代實現(xiàn)使用方式，主要是看實現(xiàn)思想從圖中我們可以很明顯的看出，使用尾遞歸計算斐波那契數(shù)列性能完勝直接遞歸和閉包，特別是當(dāng)數(shù)值比較大的時候，尾遞歸的作用就越明顯。前端微專業(yè)JavaScript有一道題目是求斐波那契數(shù)列的，一開始沒想很多，覺得實現(xiàn)功能自己已經(jīng)很棒棒了（逃）后面有同學(xué)討論直接遞歸特別耗費時間，開始考慮使用閉包，看我們討論的不亦樂乎的大佬也發(fā)話了，指點我們這兩...

UCloud 2019-08-21 17:42 評論0 收藏0
【劍指offer】8.斐波那契數(shù)列

摘要：題目題目描述大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)，請你輸出斐波那契數(shù)列的第項從開始，第項為?；舅悸愤@道題在劍指中實際是當(dāng)作遞歸的反例來說的。明顯也符合斐波那契數(shù)列的規(guī)律矩形覆蓋我們可以用的小矩形橫著或者豎著去覆蓋更大的矩形。題目題目描述大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)n，請你輸出斐波那契數(shù)列的第n項（從0開始，第0項為0）。基本思路這道題在劍指offer中...

sf_wangchong 2019-08-23 14:50 評論0 收藏0
【C語言】玩轉(zhuǎn)遞歸——學(xué)好遞歸，你需要掌握的知識！

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

Donne 2021-09-09 09:33 評論0 收藏0