10082. 費式數列

I'm a slow walker, but I never walk backwards.

Task Description
請寫一函式,使用「遞迴」方式計算費式數列的第 N 個數字。

費式數列定義為:第 0 個數字為 0,第 1 個數字為 1,第 n 個數字為第 (n-1) 個數字和第 (n-2) 個數字的和。

例如,前幾個費式數字依序為:0, 1, 1, 2, 3, 5, 8, 13, 21, ...

請讓使用者輸入一個正整數 N,程式應該印出費式數列的第 N 個數字。

Input Format
測資給定一正整數 N。

Output Format
印出費式數列第 N 個數字。

Sample Input

10

Sample Output

55

Submit

Login

Testdata Set

Download Testdata