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