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