再帰関数の練習

等差数列を使って再帰関数のイメージをつかむための練習。

等差数列

等差数列は、初項$a_1$、公差$d$で表される数列で、第$n$項目$(n > 1)$を以下の一般項と呼ばれる式であらわす。

\begin{equation}
a_n = a_1 + (n-1)\times d 
\end{equation}

再帰関数

再帰関数とは、関数の定義内で自分自身を呼ぶ関数である。
例えば、数学的に表すと、

\begin{aligned}
f(x) &= x + f(x-1)\ \ (x > 1) \\
&= 1\ \ (x \le 1)
\end{aligned}

の様な関数が有った場合$x$に9を代入すると、

\begin{aligned}
f(9) &= 9 + f(9-1) \\
&= 9 + (8 + f(8-1)) \\
&= 9 + 8 + (7 + f(7-1)) \\
&= 9 + 8 + 7 + (6 + f(6-1)) \\
&= 9 + 8 + 7 + 6 + (5 + f(5-1)) \\
&= 9 + 8 + 7 + 6 + 5 + (4 + f(4-1)) \\
&= 9 + 8 + 7 + 6 + 5 + 4 + (3 + f(3-1)) \\
&= 9 + 8 + 7 + 6 + 5 + 4 + 3 + (2 + f(2-1)) \\
&= 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 
\end{aligned}

と式が展開されていく。
上の式は結果的には、1から9までの足し算を行った事になる。
1から9までの足し算であればプログラムでは以下の様に足し算できる。

int sum(0);
for(int i = 9;i > 0;--i){
    sum += (int) i;
}

でも、$f(-10.0)$を代入したらどうだろうか。
この場合は、関数が返す値は1となる。for文では足りなくなってしまう。なので、上述の$f(x)$をプログラム的に記述する際は、

double f(double x){
    double sum(0.0);
    if(x < 1){
        return 1.0;
    }
    sum = f(x-1) + x;
    return sum;
}

と記述してあげればよい。

等差数列をあえて再帰関数を使って表現

再帰関数がどのように動くのかは上述した通り。
何となくイメージがつかめていればいいのかな。
さてさて、等差数列は初項と公差ささえ分かってしまえば第$n$項の値を求めるのは至極簡単。何の意味もないけど、再帰関数を使って等差数列を書いてみた。(どっかの本に再帰関数は数列を頭に思い浮かべるといい見たいに書いてあった気がした)

結果以下の様になった。

sncd.cpp

#include <iostream>
using namespace std;

double fSNCD(double a1,double d,int n){
    double an;
    if(n == 1){
        return a1;
    }
    an = fSNCD(a1,d,n-1)+d;
    return an;
}

void SNCD(){
    double a1;
    double d;
    int n;

    cout << "*------------------------------------------*" << endl;
    cout << " Sequence of Numbers with Common Difference" << endl;
    cout << "*------------------------------------------*" << endl;
    cout << " Input First Term        >> ";cin >> a1;
    cout << " Input Common Difference >> ";cin >> d;
    cout << " Input Number (n > 1)    >> ";cin >> n;
    cout << endl;
    if(n > 1){
        cout << "       Results :: " << fSNCD(a1,d,n) << endl;
        cout << " Check Results :: " << a1 + (n-1)*d << endl;
        cout << endl;
    }else{
        cout << " Number is less than 1 !!! " << endl;
        cout << endl;
    }
}

int main(){
    SNCD();
    return 0;
}

最後結果を出すときにCheck Resultsとして、一般項から第$n$項目を求めている。

再帰関数の応用としてはフラクタルを描く事もできる。
いつか書いてみるかな。