再帰(recursion, recursive call)とは
自分を定義するのに自分を用いる手続き

main()
{
  printf("Hello\n");
  main(); //再帰呼び出し
  return(0);
}

永久ループのように動作するがしばらくすると セグメント例外
…戻り番地をスタックに保存しmain()を読み出すが、復帰せず繰り返されるので、 スタックオーバーフロー

再帰呼び出しが正常に機能するには、一定の条件( 基底条件)が成立したら、復帰するようにする

再帰的アルゴリズムの特徴
・ シンプルで美しい
　問題によっては非常に簡潔明快
　→ 全体と部分が同じ構造をしている
・ 効率は悪い
　関数読み出しに伴う オーバーヘッドが大きい
　…戻り番地、引数、ローカル変数などをスタック上に取る
　　→メモリを大量に消費

要するに、 効率的じゃないけど美しいプログラムを書ける

例：木の枝分かれなど

再帰的アルゴリズム作成のポイント
・現在の問題(自分)を解くのに、ひとまわり小さな問題(自分)にどんな操作をしたらよいか考える
・これ以上小さな問題にならない条件を見つける( 基底条件)
　…自明な解は何か、最小の解は何かなど
※自明…言うまでもなく明らかなこと。