分割統治法

再帰を用いたプログラミングは，「自明だけど非実用的な(再帰を用いないほうが自然な)例」か「興味深いけどコードが複雑な例」しか思い浮かびません．
ここ3年，クイックソート(の変種)を取り上げてきました．ついでに，分割統治法という言葉も説明しています:

対象領域を細分化（分割）して求め（統治），全体として正しい解になるようにする．

なのですが，去年まではこうでした:

対象領域を細分化（分割）して求め，全体として正しい解になる（統治）ようにする．

どっちが正しいのでしょうか．私自身，よく分かっていません*1．
今この二つを並べて見直したところ，もしかしたらこうなのかもしれません:

対象領域を細分化して求め（分割），全体として正しい解になる（統治）ようにする．

クイックソートも分割統治法を利用したアルゴリズムですが，クイックソートでは，全体として正しい解になる「ようにする」処理を特にしていません．なので，分割統治法の典型例として，クイックソートを取り上げるのが不適切なのかもしれません．
授業中にきちんと言えなかったのですが，ここで，再帰と分割統治法の注意点を書いておきます:

• 再帰呼び出しの無限ループに陥ることのないよう，いつかは*2呼び出さなくなるための配慮が必要です．countdownについては，再帰呼び出しをしていくと，実引数の値が1ずつ減っていき，これが0になったら，再帰呼び出しをしなくなります．
• クイックソートにおいて，関数の引数は，処理対象の配列(の先頭を指し示すポインタ)のほか，処理対象の先頭と末尾の位置を書いておきます．再帰呼び出しをするとき，配列(の先頭を指し示すポインタ)はそのまま書き，先頭と末尾は，範囲を狭めるようにします．
  • 配列，先頭，末尾の3つを引数とするのは，クイックソートに限らず，分割統治法を用いた関数を定義するとき，よく行われます．
  • 先頭と末尾の一方が変わらないことはあってもかまいませんが，両方が変わらないときは…再帰呼び出しの無限ループが生じます．そうならないコードであることをしっかり確認しましょう．どうしてもデバッグできないときは，「運用で解決」…再帰呼び出しをするときの引数の値が，関数呼び出し時のそれらと一致するときに，警告を発して再帰呼び出しをしないようにする…も，検討してみましょう．

*1:もう一つ，分かっていないことがありまして，それは「分割統治法は，再帰的な構造を持たない対象に対して適用するのでもいいか」です．分割統治法 - Wikipediaの「構造化プログラミング」や情報技術基礎を見ると，再帰は必須ではないのか，いや転用(もともとは再帰的な構造にしか適用しなかった)に過ぎないのか…．

*2:"eventually" という英単語も覚えておきましょう．