【競プロ】再帰関数で遊ぼう【C++】

普段は解いた問題の解説的なものを書いていますが、今日は気分じゃないのでサボります。
昨日書いたのは以下の2つです。

【競プロ】1日1AC : ABC75 B問題

2020年3月30日

【競プロ】1日1AC : ABC96 C問題

2020年3月30日

まだまだ競プロ初心者なので何も理解していませんが、特に再帰関数は何も分かりません。なんとなく嫌いです。

なので今回は、再帰関数を「嫌い」から「好きではない」くらいまで上げるためにちょっと遊んでみましょう、という記事です。

和を計算してみる

よくある例ですが、練習にはちょうどいいでしょう。

再帰関数としてrec関数を考えます。（再帰関数は英語でrecursive function）
ここでは引数kを使い、rec関数は「\(1\) から \(k\) までの和」を返すとします。

では処理の内容を考えましょう。
\[\sum_{i=1}^{n} i=n+\sum_{i=1}^{n-1}=n+(n-1)+\sum_{i=1}^{n-2}=\cdots\]
つまり、

\(\mathrm{rec}(1)\) の中では \(\mathrm{rec}(0)\) なんて変なものを呼びださいように代わりに1を返しましょう。

#include <bits/stdc++.h>
using namespace std;

int rec(int k){
    if(k == 1) return 1;
    return (k + rec(k-1));
}

int main(){
    int n;
    cin >> n;
    cout << rec(n) << endl;
}

楽しいですね。

最大公約数を求める

最初に思いついたネタはこっち。ユークリッドの互除法を使います。

自然数 \(a,b\) の最大公約数を\(\gcd (a,b)\) とすると
\[\gcd (a,b)= \begin{cases}
\gcd (b,a\ \%\ b) & (b \neq 0) \\
a & (b=0)
\end{cases}
\]
です。

例を挙げれば、

これも再帰関数を使って実装できるでしょう。何ならさっきの例より簡単かもしれないですね。

#include <bits/stdc++.h>
using namespace std;

int gcd(int a,int b){
    if(b == 0) return a;
    return gcd(b,a % b);
}

int main(){
    int a,b;
    cin >> a >> b;
    cout << gcd(a,b) << endl;
}

全く説明してないですが、コードを見るとなんと分かりますね？？

終わりに

再帰関数を使う簡単な例で遊んでみました。DFSはまだよく分からないですが、慣れたらこの記事も書こうかなと思ってます。