【就プロ】再帰関数

はじめに

再帰関数とは「関数内で自分自身を呼ぶ関数」のことをいう。

メリットとデメリット

メリット

• 木構造のデータの処理に適している
• 簡潔に表記できることがある

デメリット

• 終了条件をきちんとしないと、無限ループになる可能性がある
• 再帰をしすぎると、スタックオーバーフローが起こる可能性がある

実装

今回はフィボナッチ数列を実装します。

説明文

フィボナッチ数列$A$の$0$番目の要素は$0$、$1$番目の要素は$1$であり、$2$番目以降の要素$A[n]$は以下の数式で計算される。

\begin{align}
A[n] = A[n -1] + A[n - 2]
\end{align}

入力

整数$n$

出力

フィボナッチ数列の$n$番目の要素の値

実装

C++

#include<iostream>

int Fibonacci(int idx) {
    if (idx == 0) return 0;
    else if (idx == 1) return 1;
    else {
        return Fibonacci(idx - 1) + Fibonacci(idx - 2);
    }
}

int main(int argc, char* argv[]) {
    int n;
    std::cin >> n;

    std::cout << Fibonacci(n) << std::endl;

    return 0;
}