ループを使わずに数列を出力するPythonプログラム｜再帰とフラグで実現する方法

本記事では、for文やwhile文などのループ構文を一切使わずに数列を表示するという問題の解法について解説します。

問題の定義

問題： 2つの数値 N と K が与えられます。まずNが0より大きい間はNからKを繰り返し引き、Nが0以下（ゼロまたは負）になったら、今度は逆にKを足していきます。そして値が元の数値Nに戻った時点で処理を終了します。

実行例

N = 10
K = 4
出力： 10 6 2 -2 2 6 10

アルゴリズム

1. Nが0より大きい間、関数を再帰的に呼び出し続けます。各呼び出しのたびにNからKを減算します。
2. 数値が0以下になったら加算モードに切り替え、各呼び出しごとにKを加算します。元の数値Nに戻れば完了です。
3. 加算と減算は同じ1つの関数で処理し、モードの切り替えにはブール型の変数flagを使用します。

それでは、Pythonでの実装を見ていきましょう。

コード例

def PrintNumber(N, Original, K, flag):
    # 現在の数値を表示
    print(N, end=" ")
    # 数値が0以下になったらフラグを反転させる
    if N <= 0:
        if flag == 0:
            flag = 1
        else:
            flag = 0
    # 減算フェーズ中に元の数値へ戻ったら終了
    if N == Original and not flag:
        return
    # フラグがTrueの間は減算を続ける
    if flag:
        PrintNumber(N - K, Original, K, flag)
        return
    # フラグがFalseになったら加算に切り替える
    if not flag:
        PrintNumber(N + K, Original, K, flag)
    return

N = 10
K = 4
PrintNumber(N, N, K, True)

出力結果

10 6 2 -2 2 6 10

コードのポイント

このプログラムでは、使用している変数はすべてグローバル名前空間で扱われます。

• 再帰によるループの代替： 関数が自分自身を呼び出すことで、ループ構文と同等の繰り返し処理を実現しています。
• 終了条件（ベースケース）： 「Nが元の値に戻り、かつ減算フェーズである」という条件が再帰の停止条件です。これがないと無限再帰に陥るため注意が必要です。
• フラグによるモード切替： flagがTrueの間は減算を行い、Nが0以下に到達した時点でFalseに切り替わって以降は加算を行います。
• 計算量： 呼び出し回数はおよそ 2 × (N ÷ K) 回程度に収まり、効率的に動作します。

まとめ

本記事では、Python 3.x（およびそれ以前のバージョン）において、ループ構文を一切使わずに数列を表示する手法として、再帰呼び出しとブール型フラグを組み合わせる方法を学びました。ループの代わりに再帰を用いるこの考え方は、木構造の探索やバックトラッキングなど、他の多くのアルゴリズムにも応用できる重要なテクニックです。