遞歸算法
瀏覽量:2889
在起始條件已知的情況下,解決一類重復性問題的最佳方案莫過于使用程序設計的三大基本結構之一的“循環”結構(分為“有限次”和“無限次”循環兩種情況)。然而現實生活中也存在這樣一類問題——起始條件不明確,但結尾卻已知;或者問題自身嵌套著自身。在這種情況下我們將采用反向思維,從結尾條件開始往前推演,直到把起始條件推算出為止。這樣的一種算法往往被成為“遞歸”法。本章節將主要對此算法進行一系列的探究。
一、遞歸法的定義和數學模型:
遞歸法在數學上的表達函數有點特殊,它是一種自調用函數,形式如下:
從定義式可以看出遞歸函數的最大特征在于自身的輸出作為自身的輸入,直至輸入為某一個條件而終止。
下面就結合實踐,具體闡述并驗證這一理論。
【例1】有甲、乙、丙、丁四人,從甲開始到丁,一個比一個大1歲,已知丁10歲,問甲幾歲?
【分析】這是遞歸法的一道非常典型的題目——因為我們可以很顯然知道:假設要計算甲的年齡,那么必須直到乙的年齡;同樣,算乙的必須直到丙的,算丙的必須知道丁的,因為丁已知,自然可以往前推算了。現在假設有一個數學模型(函數)可以計算出他們各自的年齡(方便期間我們給他們編號——甲=1,乙=2,丙=3,丁=4),那么存在這一個F(X)函數,X表示某人的編號,其規律如下:
F(1)=F(2)+1
F(2)=F(3)+1
F(3)=F(4)+1
F(4)=10
顯然,直到X=4