配列として表される数に1を加える方法（再帰的アプローチ）

非負の整数を桁の並びとして表現した配列が与えられます。この数に1を加えてください（桁列で表された数値のインクリメント）。桁は、最上位の桁が配列の先頭要素となるように格納されています。

アルゴリズムの考え方

桁列で表された数に1を加えるには、以下の手順で考えます。

• 配列を末尾から見ていき、加算では最後の数字（たとえば4）を5へ繰り上げます。
• 末尾の要素が9である場合は、その要素を0にし、繰り上がり（キャリー）を1とします。
• 次のステップでは繰り上がりの有無を確認し、加算結果が10になる場合には上記と同じ処理を行います。
• 繰り上がりを加算した後は、次のステップに備えて繰り上がりを0に戻します。
• 加算によって配列のサイズが拡張される場合（すべての桁が9だった場合など）は、先頭に1を追加します。

たとえば、配列が [7, 6, 3, 4] の場合、この配列は十進数の7634を表しています。これに1を加えると7635となるため、新しい配列は [7, 6, 3, 5] になります。

入出力例

入力: [7, 6, 9, 9]
出力: [7, 7, 0, 0]

入力: [4, 1, 7, 8, 9]
出力: [4, 1, 7, 9, 0]

説明：まず配列の最後の要素に1を加えます。その要素が9未満であれば、ここで処理は完了です。要素が9の場合は0に置き換え、残りの要素に対して再帰的に同じ操作を適用します。これにより、9が連続している桁も正しく繰り上がり処理されます。

実装例（C++）

#include <iostream>
using namespace std;
void sum(int arr[], int n) {
    int i = n;
    if(arr[i] < 9) {
        arr[i] = arr[i] + 1;
        return;
    }
    arr[i] = 0;
    i--;
    sum(arr, i);
    if(arr[0] > 0) {
        cout << arr[0] << ", ";
    }
    for(int i = 1; i <= n; i++) {
        cout << arr[i];
        if(i < n) {
            cout << ", ";
        }
    }
}
int main() {
    int n = 4;
    int arr[] = {4, 1, 7, 8, 9};
    sum(arr, n);
    return 0;
}

計算量

この再帰的アプローチでは、最悪の場合（すべての桁が9の場合）に配列全体を走査するため、時間計算量はO(n) となります。また、再帰呼び出しが最大n回発生するため、空間計算量もO(n) です。なお、再帰を使わずループで末尾から処理すれば、空間計算量をO(1)に抑えることも可能です。