配列で表現された数値に1を加算する方法（再帰的アプローチ）

この記事では、興味深い問題を一つ取り上げます。それは「与えられた数値に1を加算する」というものです。これは非常に単純な作業ですが、ここでは数値を配列として扱う点がポイントになります。数値の各桁は、配列の各要素として格納されます。たとえば、数値が512であれば、{5, 1, 2} のように保存されます。さらに、この加算処理を再帰的アプローチで実装する必要があります。それでは、アルゴリズムを見ていきましょう。

アルゴリズム

increment(arr, n, index)

初期状態では、indexのデフォルト値は0です。

begin
    if index < n, then
        if arr[index] < 9, then
            arr[index] := arr[index] + 1
        else
            arr[index] := 0
            increment(arr, n, index + 1)
        end if
    end if
    if index = n, then
        arr[n] := 1
        n := n + 1
    end if
end

このアルゴリズムの動作は以下の通りです。

• 現在の桁（index）が9未満であれば、その桁に1を足すだけで処理は完了します。
• 現在の桁が9である場合は、その桁を0にして、次の桁に対してincrement関数を再帰的に呼び出します。これにより、繰り上がり（キャリー）が正しく上位の桁へ伝播していきます。
• すべての桁が9だった場合（例：999）、最上位の桁を超えた位置に新しく1を追加し、配列の長さnを1つ増やします。

C++による実装例

#include <iostream>
#include <cmath>
#define MAX 20
using namespace std;
void increment(int num_arr[], int &n, int index = 0){
    if(index < n){
        if(num_arr[index] < 9){ // 桁が9未満の場合は、そのまま1を加算
            num_arr[index]++;
        }else{ // それ以外の場合は、次の桁へ再帰的に処理を委ねる
            num_arr[index] = 0;
            increment(num_arr, n, index+1);
        }
    }
    if(index == n){
        num_arr[n] = 1; // 余分な繰り上がりを追加
        n++; // 桁数を1つ増やす
    }
}
void dispNumber(int num_arr[], int n){
    for(int i = n-1; i>= 0; i--){
        cout << num_arr[i];
    }
    cout << endl;
}
int numToArr(int num_arr[], int number){
    int i = 0;
    int n = log10(number) + 1;
    for(int i = i; i< n; i++){
        num_arr[i] = number % 10;
        number /= 10;
    }
    return n;
}
main() {
    int number = 1782698599;
    int num_arr[MAX];
    int n = numToArr(num_arr, number);
    cout << \"Initial Number: \"; dispNumber(num_arr, n);
    increment(num_arr, n);
    cout << \"Final Number: \"; dispNumber(num_arr, n);
}

コードの解説

numToArr関数

数値を配列へ変換する関数です。log10を使って桁数を求め、剰余演算（% 10）によって下の桁から順に配列へ格納していきます。

increment関数

本体となる再帰関数です。デフォルト引数index=0から処理を開始し、桁が9であれば0に戻した上で次の桁へ再帰呼び出しを行います。全桁が9だったケースでは、配列の末尾に新しい1を追加することで桁数自体を拡張できます。

dispNumber関数

配列には下の桁から数値が格納されているため、上の桁から順に表示するために逆順でループ処理を行っています。

実行結果

Initial Number: 1782698599
Final Number: 1782698600

このように、数値型の上限に制約されずに大きな桁数の数値でも、配列と再帰を組み合わせることで柔軟に1の加算処理を実現できます。