ミスを減らす再帰関数のデザイン

はじめに

先日,再帰関数のプログラムを作っていたのですがとあるミスを生じてしまいました
そんな中,「この再帰関数のデザインはいいな」と思えたコードがあったので紹介します

実際の例

前の記事(10進から2進変換の様々なアプローチ)より再帰関数のプログラムを少し書き替えます

recursive.cpp

void print_dec2bin(int n)
{
    if(n==0){
        return;
    }else{
        print_dec2bin(n/2);
        printf("%d",n%2);
    }
    return;
}

この例では前回の関数から引数のdigitを消去し,再帰の終端条件をn==0としました
digitを消したので負の値は定義できないので考えないものとし,最後の改行文字も不要だとします
実はこの段階でバグをはさみ込んでしまっているのですが,皆さんお気づきでしょうか？
(もちろん,桁溢れなどのシステム面のバグは含まないものとします)

ここに答えを書いてしまうと答えが画面に表示されてしまいますので再帰関数の考え方についてその後に答えを書こうかと思いますので,皆さん考えてみてください

再帰関数の一般的な考え方

再帰関数とは関数の中で自分の関数を呼ぶ関数のことです
関数を呼ばれるタイミングの前と後で処理順が逆になります
単純に関数を呼びつづけると無限ループになって終わらないので終端条件をつけて関数を遡っていきます
以上からイメージはこんな感じになります

丸四角が関数で白丸が前後の処理,黒丸が終端条件(関数を含む)になっています
上記の例では110→11→1→0となり0の地点で終端として0→1→11→110の右端(2で割った余り)を書いていけば答えにたどり着けるという魂胆です

問題点の答え

答えはこの関数は入力0に対応してないということです
入力が0の場合いきなり終端条件を満たしてしまい,何もせずに終了します
前回のプログラムでは桁の指定があるので,1桁になるので問題はないですが
改造するところで失敗しちゃっています
これを解決するための一つの方法として以下のような方法があります

recursive2.cpp

void print_dec2bin(int n)
{
    if(n<2){

    }else{
        print_dec2bin(n/2);
    }
    printf("%d",n%2);
    return;
}

終端条件を2以上にしてどんな値でも1桁目を吐かせれば確かに答えになりますが
見た目も分かり辛いのでよろしくありません,そこで考え方をちょっと捻ってみます

良いデザイン

ここでの問題点は終端条件とすべき部分で答えが返らないということです
なら逆に考えて終端条件で答えを出力すれば上手く行くのではないかと考えるのです
ということでやっていきます

recursive3.cpp

void print_dec2bin(int n)
{
    if(n==0)      printf("0");
    else if(n==1) printf("1");
    }else{
        print_dec2bin(n/2);
        print_dec2bin(n%2);
    }
    return;
}

ここでのポイントは「今までの再帰関数」と「終端条件用関数」の2つを呼び出すことです
上で書いたようなイメージに直すと以下の様になります

処理の流れは110→11→1(1)→[11→1(2)→11]→[110→0(3)→110]という風になります
再帰関数を使って逆順に戻っていき,その1の位を終端条件としての再帰関数にぶつけて値を吐かせていきます
先ほどの唐突に出てくる終端条件の「2より小さい」の理由とか説明しなくても簡潔に表すことができました
最初は再帰関数自体が2つの仕事をしていて少し気持ち悪い形に見えますが,使いこなせれば便利かもしれません