1樓：楊零
遞迴本身是描述問題的一種很好的方式，它的易於理解性和實現難度帶來的價值，遠高於幾次程式呼叫和遞迴棧帶來的成本。因此你可以放心大膽的用。但是，遞迴雖然是一種好的對解決問題的方法的描述，但並不是所有的問題都能只用遞迴就能很好的解決。
另外，能用遞迴寫，非要改成遞推，然後時間複雜度沒有變化，我認為是划不來的。所以說看效率，跟這個演算法是不是遞迴沒有任何關係，看它的時間複雜度是多少就完了。問遞迴的效率高不高這個問題過於抽象，就好像是在問數學是不是解決問題的好方法一樣。
2樓：呂建偉
找到規則就可以寫個通項公式sum =2*i 所有項的和就是total =sum#include
int total=0;
void fun(int a)
}void main()
假如乙個結點A有左孩子B或右孩子C，則生成新的結點B或結點C；並儲存和結點A 的父子關係；假如B或C不存在，即你說的b=0，那就回來到結點A的父結點O；假定A是O的左孩子，回來O後，持續處理O的右孩子；處理完了，再回到O的父結點；依此類推如圖，處理到H；H沒有孩子，就要回來到D；D沒有右孩子，持續回來到B；處理B的右孩子；回來操作是由遞迴來完結的；就像乙個大人，讓乙個孩子去做一件事；做完了，必須通知大人；然後，這個大人再讓另乙個孩子去做另一件事；而這需求第乙個孩子通知大人，他的完結情況大人知道今後，才會讓另乙個孩子去做另一件事。
3樓：
其實沒有遞迴也可以寫程式的，因為遞迴和迴圈是等價的。事實上的話，遞迴只能算是函式式程式設計的基本思想，因為λ-演算的模型下沒法表達迴圈，但在圖靈模型下可以，而這兩個計算模型是等價的。
你覺得慢的原因是因為所有計算機都是圖靈機，寫遞迴的話相當於在模擬器上跑，但如果把演算法寫成尾呼叫的話，效率應該和迴圈是一樣的，因為很多語言對於尾呼叫有優化。
4樓：Milo Yip
遞迴中有重複子問題而不做 Memoization 的話效率不高。在實際程式設計情況中遞迴有一些額外開銷，可能可通過轉化為非遞迴版本去優化效能。
另外，就斐波那契數列的計算而言，有通項公式：
import
math
sqrt5
=math
.sqrt(5
)golden=(
1+sqrt5)/
2def
fib(n):
return
round
(math
.pow
(golden,n
)/sqrt5
)但因浮點精度有限，對於較大的數，可用斐波那契數列的矩陣形式：
然後用快速冪實現 時間複雜度。
5樓：勉強
哥們你看一下fib第400w項的值。。。內個數就表示計算了fib(1)和fib(2)的總次數，這還不算中間其他數的次數。
然後再想想每次函式呼叫時要花費的開銷。。。
然後再想想python本來效率就不算高。。
更可怕的是你還把前400w項都算了。。
這麼大的工作量你從哪看出來不複雜的。。
(cpu:mmp~)
(另外非python黨有個疑問：python中int沒有範圍麼？感覺這個數到最後應該超過42億了。。。不會溢位麼？)
6樓：Albert Anne
要用尾遞迴。
通常情況下，遞迴算是很耗資源的，每一次遞迴都會在記憶體裡建乙個堆疊，次數越多記憶體消耗越多。
具體參考mit的《演算法導論》。
7樓：
應該不算特別高，特別是Python本身也不算快。看一下組合語言就知道函式的呼叫是要占用計算資源的，而且占用棧。反之迴圈就要相對快一些。
用遞迴主要是便於理解和設計，如果處理問題的規模比較大的問題，能用迴圈還是用迴圈吧
8樓：靈劍
遞迴跟效率沒關係，是解決可計算性問題的，圖靈可計算的問題都可以通過一些單步的操作加上遞迴完成，所以有遞迴就能表述出所有的程式，而且比圖靈機程式更直觀。至於效率那是實現時候的問題。
9樓：lhrbu
不是，遞迴演算法其實就是數學歸納法的逆運算，效率特別低，如求斐波那契數列第n項當n比較大時，用函式遞迴演算法比正向暴力累加慢不知道多少倍
10樓：
思想沒有效率。遞迴思想也不只體現在你程式設計些函式那點東西上面。
本科學過編譯原理的都知道，沒有遞迴就不可能用有限的字母概括擁有無窮句子的語言。
在深入一點，丘奇定理了解一下。
11樓：
並不存在「遞迴思想是程式設計的基本思想」這個說法，遞迴思想只是程式設計思想的其中一種；
程式設計思想，就是用計算機來解決現實問題的一些思想；
遞迴很蠢很笨效率很低，你可以一步一步觀察到計算機是怎麼從n=1，計算到n=n這個過程；
計算機很笨，它只是計算頻率非常高，計算速度非常快——而已；
遞迴所代表的的，就是把乙個很複雜的問題，拆解成很小很簡潔的問題，然後交給計算機一步一步地去執行。
12樓：PegasusWang
哈哈，巧了，我之前面試就是被考過這個。直接斐波那契數列效率很低是因為中間很多重複計算，比如 f(5) = f(4) + f(3), f(4) = f(3) + f(2)，你發現了嗎， f(3) 被多次計算了。你畫出來這個計算過程就是一棵樹，樹的節點有很多重複計算項。
如果我們加上快取，或者你開乙個陣列把之前的結果都記錄下來，讓已經計算的資料查詢達到 O(1)，計算就成了 O(n)。而原始的遞迴式時間複雜度是 O(2^n)
乙個裝飾器就可以搞定：
def cache(func):
@cache
def fib(n):
if n <= 2return 1
elsereturn fib(n - 1) + fib(n - 2)
13樓：
誰說的遞迴是程式設計的基本思想？遞迴就是在函式A裡呼叫函式B，只不過AB恰好是同乙個。遞迴要算基本，那函式就是基本的基本了。
至於遞迴跟效率的關係，就和鍵盤跟效率的關係一樣。
14樓：棕小漸
它效率很高嗎？
Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation!
作為結論先丟擲來：
「如果使用迴圈，程式的效能可能更高；如果使用遞迴，程式可能更容易理解。」
使用遞迴為什麼效率不高，這就需要理解call stack。
如果呼叫函式，計算機首先為該函式呼叫分配一塊記憶體，函式呼叫會在記憶體形成乙個「呼叫記錄」，儲存呼叫位置和內部變數等資訊，該「呼叫記錄」稱之為：call frame。計算機使用乙個棧來表示這些記憶體塊，且這個棧用於儲存多個call frame，這個棧就被稱為call stack。
function
foo(
name
)function
bar(
name
)bar
('bar'
)呼叫bar('bar')，計算機為該函式呼叫分配其所需的記憶體，接著呼叫foo('foo')，同理也為其分配所需的記憶體。呼叫另乙個函式時，當前函式處於未完成狀態，該函式的所有變數的值都還在記憶體中。函式 bar 的內部呼叫函式 foo ，那麼在 bar 的call frame上方，還會形成乙個 foo 的call frame。
等到 foo 執行結束返回，foo 的call frame才會消失。
使用遞迴時，當前函式處於未完成狀態，而繼續呼叫另乙個函式，直到遞迴呼叫完成。每個函式呼叫都要占用一定的記憶體，棧中儲存了多個call frame。如果棧很高，就意味著儲存了大量的call frame。
總體來說，使用遞迴的效率並不高。
遞迴思想為什麼是程式設計的基本思想
用計算機來解決人們實際問題的思維方式，即程式設計思想。
假設乙個實際存在的問題：有乙個蘋果放在箱子中，但這個箱子裡有箱子，而箱子裡的箱子又有箱子，蘋果可能就存在某個箱子中，現在需要找出放在箱子裡的蘋果。
如果使用非遞迴思想可以這麼做：
建立乙個要查詢的箱子堆
從箱子堆中取出乙個箱子進行搜尋
如果找到的是盒子，將其放到盒子堆中
如果找到的是蘋果，則結束搜尋
回到步驟二
如果用遞迴的思想可以這麼做：
檢查箱子裡的物品
如果是箱子，則回到步驟一
如果是蘋果，則結束搜尋
遞迴的思想確實是可以解決實際問題，通過重複將問題分解為同類的子問題而解決問題，更易於理解。
15樓：黃玄
題主，Top-down dynamic programming | Memoization （動態規劃）
Time complexity & Recurrence relation （時間複雜度）
Theory of computation （計算理論）μ-recursive functions （μ-遞迴函式）Fast matrix exponential （快速矩陣冪）Tail recursion optimization （尾遞迴優化）
了解一下
16樓：
這不是遞迴的問題，是演算法的問題，要快取前兩次的結果，才會快。
遞迴是一種能簡化程式設計模型的抽象，實際編譯中，遞迴會用迴圈來實現。
17樓：掛瓜
題主應該看一本書叫《電腦程式的構造和解釋》簡稱《SICP》。
用lisp描述的。
其實遞迴描述演算法是非常直觀的。描述演算法和演算法優化就是兩碼事了。
比如經典的快速排序，你用基本快速排序，其實用遞迴形式就幾句話就說明白了。
可效率真的太不行了，一定程度還不如歸併排序。
因為基本快速排序的描述用了兩個遞迴。
但你稍微優化一下，去除乙個遞迴，用乙個引數傳遞結果，就會有質的變化。
所以先把演算法搞清楚在先，優化慢慢來。
18樓：烈日烤魚
因為遞迴是函式式程式設計的重要手段，函式式程式設計是圖靈機思想的更直接體現，而圖靈機是程式執行的基本模型，所以遞迴某種程度上體現著程式執行的基本思想。
PS：我其實不敢苟同遞迴思想是程式設計的基本思想，「基本」兩字它還有點配不上，以上回答是根據結果硬猜的原因。
19樓：楊航鋒
如果題主非要用遞迴的方法求斐波那契數列，又要速度快那也是有方法的。
import
functools
# 方法一，自定義快取裝飾器
defcache
(func
):memo
=dict
()@functools
.wraps
(func
)def(*
args,**
kwargs
):if
args
notin
memo
:memo
[args]=
func(*
args,**
kwargs
)return
memo
[args
]return
@cache
deffib(n
):if
n<=2:
return
1return
fib(n-
2)+fib(n
-1)# 方法二，使用內建快取裝飾器
@functools
.lru_cache(8
)def
fib(n):
ifn<=2:
return
1return
fib(n-
2)+fib(n
-1)用上述fib函式求符合條件的結果，時間可以忽略不計。
目標管理的基本思想？
培訓師胡一夫 手下人總是給你出題，你千萬要小心，不要掉到他們給你挖的陷阱裡面去了。但是很多管理者不小心就當考生了，有的是答問答題 有的是答填空題 有的答選擇題，水平高一點還知道答選擇題。其實什麼題都不應該答，按照德魯克的管理原則，一層一層把目標設立了，大家就按照這個目標去做事情，為什麼要讓我去答題，...
你認為數學的基本思想方法是什麼
少年A 聯絡的眼光，發展的眼光 過程是曲折的，前途是光明的 乙個理科生在政治課上學到的哲學，意外的發現也很適用於數學 這麼說，著名數學教育家polya也是位哲學博士 黃守衛 數學，就是從公理和基本概念出發，按最基本邏輯構建體系和系統，從而可以覆蓋所遇到的問題，不過，問題中大多數並沒有確定性。數學，是...
你認為物理的基本思想方法是什麼
楊昇山 我認為，首先是搞清楚理論與物質之間的關係。自然界並沒有給出乙個理論，所有的理論都是人們互相交流的看法。自然界也沒有給出乙個數值，所有的數值都是人們對自然界物質以及物質運動現象進行區分的結果。從人類認識自然界的過程中來分析，人們區分物質的方法是比較。原始的比較是直接把物體放在一起進行比較的。由...