????????在調用一個函數的過程中又出現直接或間接地調用該函數本身,稱為函數的遞歸(recursive)調用。C和C++允許函數的遞歸調用。例如:
????????int f(int x)
? ? ? ? { int y,z;
? ? ? ? ? z=f(y);????????????????//在調用函數 f 的過程中,又要調用 f 函數
? ? ? ? ? return (2*z);
????????}
????????以上是直接調用本函數。
????????可以看出,這種遞歸調用是無終止的自身調用。顯然,程序中不應出現這種無終止的遞歸調用,而只應出現有限次數的、有終止的遞歸調用,這可以用 if 語句來控制,只有在某一條件成立時才繼續執行遞歸調用,否則就不再繼續。
????????包含遞歸調用的函數稱為遞歸函數。關于遞歸的概念,有些讀者可能感到不好理解,下面用一個日常生活中的例子來說明。
????????例?有5個人坐在一起,問第5個人多少歲?他說比第4個人大兩歲。問第4個人歲數,他說比第3個人大兩歲。問第3個人,又說比第2個人大兩歲。問第2個人,說比第1個人大兩歲。最后問第1個人,他說是10歲。請問第5個人多少歲?
解題思路:
????????顯然,這是一個遞歸問題。要求第5個人的年齡,就必須先知道第4個人的年齡,而第4個人的年齡也不知道。要求第4個人的年齡必須先知道第3個人的年齡,而第3個人的年齡又取決于第2個人的年齡,第2個人的年齡取決于第1個人的年齡。而且每個人都比其前一個人大兩歲,即
????????age(5)=age(4)+2
????????age(4)=age(3)+2
????????age(3)=age(2)+2
????????age(2)=age(1)+2
????????age(1)=10
可以用函數表述如下:
????????age(n)=10? ? ? ? ? ? ? ? ? ? ? ?(n=1)
????????age(n)=age(n-1)+2????????(n>1)
????????可以看到,當n>1時,求第n個人的年齡的公式是相同的。
????????求解可分成兩個階段:第1階段是回溯,即將第n個人的年齡表示為第(n-1)個人年齡的函數,而第(n-1)個人的年齡仍然不知道,還要回溯到第(n-2)個人的年齡……直到第1個人的年齡。此時age(1)已知,不必再向前推了。然后開始第2階段,采用遞推方法,從第1個人的已知年齡推算出第2個人的年齡(12歲),從第2個人的年齡推算出第3個人的年齡(14)……一直推算出第5個人的年齡(18歲)為止。也就是說,一個遞歸的問題可以分為回溯和遞推兩個階段。要經歷許多步才能求出最后的值。顯而易見,如果要求遞歸過程不是無限制進行下去,必須具有一個結束遞歸過程的條件。例如 age(1)= 10,就是使遞歸結束的條件。
編寫程序:
運行結果:
程序分析:
????????用一個age函數來實現遞歸過程。main函數中除了return語句外,只有一個cout語句。整個問題的求解全靠一個函數調用"age(5)"來解決。age函數共被調用5次,即age(5),age(4),age(3),age(2),age(1)。其中,age(5)是main函數調用的,其余4次是在age函數中調用的,即遞歸調用4次。請讀者仔細分析調用的過程。應當強調說明的是:在某一次調用age函數時并不是立即得到age(n)的值,而是一次又一次地進行遞歸調用,到age(1)時才有確定的值,然后再遞推出age(2),age(3),age(4),age(5)。