TanZek's 技術空間

遞歸模型

一般由遞歸出口和遞歸體兩部分組成，前者確定遞歸到何時為止，后者確定遞歸的方式。

遞歸出口的一般格式為：
            f(s₀)=m₀
這里s₀與m₀均為常量，有些遞歸問題可能有多個遞歸出口。

遞歸體一般格式為：
            f(s)=g(f(s₁),f(s₂),……,f(s_n),c₁,c₂,……,c_m)
這是S是一個遞歸大問題，s₁,s₂,……,s_n為遞歸小問題，c₁,c₂,……,c_m是若干個可以直接解決的問題。g為遞歸函數，反映了遞歸問題的結構。

遞歸設計的步驟：
1.   對原問題f(s)進行分析，假設出合理的較小問題f(s')。
2.   假設f(s')是可解的，并在此基礎上確定f(s)的解，即給出f(s)與f(s')之間的關系。
3.   確定一個特定情況（如f(1)或f(0)）的解，作為遞歸出口。