斐波那契遞歸

fuyi501 發布于2019-08-21 17:13 / 3290人閱讀

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

常規寫法

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))
// 函數調用順序
// 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)

可以發現整個過程是二叉樹先序遍歷的過程。此外，整個過程中多次調用了Fib1(3)、Fib1(2)、Fib1(5)，產生大量冗余的調用。無路什么數據結構最后都是隊棧嗎？

一行寫出斐波那契數列

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

改進寫法1

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

求以3和7為初始項的第一個序列中的t6(71)可以轉化為求以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)可以轉化為求以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)

GPU云服務器云服務器波那契數列解斐波樹形遞歸遞歸編程

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

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

js 實現斐波那契數列(數組緩存、動態規劃、尾調用優化)

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

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

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

alphahans 2019-08-20 12:14 評論0 收藏0
使用js實現斐波那契數列

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

alexnevsky 2019-08-26 13:36 評論0 收藏0
云課堂作業---斐波那契數列的引發的思索

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

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

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

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

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

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