遞迴 : 1+2+...N
之前計算1+2+....+N,我們都會使用迴圈的方式的撰寫,其實也可以使用遞迴的方式來處理。遞迴是相當重要的一種演算法,在APCS的考試的觀念題佔有很多比例,可見其重要。
在資訊科學中,我們如果發現一個問題可以分成和自己樣式一樣的小問題 ,那麼,我們就可以遞迴的方式來處理。
f(n) = 1+2+3.....+(n-1)+n
f(n-1) = 1+2+3.....+(n-2)+(n-1)
.........
f(n) = f(n-1) + n
f(6) = f(5) +6
f(5) = f(4)+5
f(4) = f(3)+4
f(3) = f(2)+3
f(2) = f(1)+2
f(1) = 1 是終止條件,會停止遞迴
f(1) = 1 回傳 f(2) = 1+2
f(2) = 3 回傳 f(3) = 3+3
f(3) = 6 回傳 f(4) = 6+4
f(4) = 10 回傳 f(5) 10+5
f(5) = 15 回傳 f(6) 15+6 =21
本課作業:
請練習N!程式,5! = 5 X 4 X 3 X 2 X 1