遞歸:解決一個問題的時候可以分解為更小的問題,而且分解之后的問題的解決方法和原來的一致,這時可以把問題一直這么分解下去,直到問題分解到足夠小的時候進行解決,然后再回溯回去解決原來的問題.
遞推:類似于數(shù)學歸納法中的歸納步驟,假設(shè)某個問題在某一步時某個條件成立,下一步可以根據(jù)這一步所得的關(guān)系進行推導,這就是遞推.
本質(zhì)上,遞歸和遞推都是同一種解決問題的思路,就是把問題分解中較小的問題,但是遞歸是由大到小的推導直到問題規(guī)模足夠小可以不必繼續(xù)推導就可以解決了,而遞推是由小到大的推導,采用遞推解決問題的有KMP算法之中尋找next數(shù)組元素值的算法.
遞歸,一般的算法書上都有明確的定義,而遞推我印象之中還沒有非常嚴格的說明.在這里根據(jù)我的理解作一個解釋,也許不完全對,請大家指正.