zukaついに競技プログラミングを始めました！
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderが公表しているc++の入門記事の内容を1からさらっていくものです。今回は2.05.再帰関数です。
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int count(vector<vector<int> > &C, int x){
// 初期条件
if (C[x].size()==0){
return 1;
}
// 初期化
int report = 0;
// 再帰の実体
for (int c: C[x]){
report += count(C, c);
}
report += 1;
return report;
}
int main() {
int N = 0;
cin >> N;
vector<int> P(N);
// 初期条件
P[0] = -1;
rep(i, N-1){
cin >> P[i+1];
}
// 入力を入れていく
vector<vector<int> > C(N);
rep(i, N-1){
int parent = P[i+1];
C[parent].push_back(i+1);
}
// 再帰を実行しながら出力する
rep(i, N){
cout << count(C, i) << endl;
}
}ポイント
今回おさえるべき内容
関数の中で同じ関数を呼び出すことを再帰と呼ぶ
再帰関数の実装ではベースケースを忘れずに
一般的に再帰はたくさんのメモリを消費してしまう
フィボナッチ数列でおなじみの再帰関数です。再帰関数内では，ベースケース（再帰をせずに計算ができる部分）を書く必要があります。ベースケースを忘れてしまうと，無限に再帰し続けてしまうことになるため注意が必要です。ベースケースは，再帰のゴールとも考えられます。
一般的に再帰関数を呼び出すと，たくさんのメモリが消費されてしまいます。そのため，メモ化（動的計画法）などを用いて計算量を削減しようというアルゴリズムもたくさん存在しています。ここでは割愛しますが，実践問題で直面した際に詳しくお伝えしていこうと思います。
コメント