Python再帰関数で数字を分割して足す

Question

def recursiveDigitsSplitAdded(digits, total, sumUp):
    if digits < 1 and total < 10:
        return sumUp + total
    elif digits < 1 and total >= 10:
        return recursiveDigitsSplitAdded(total//10, sumUp+total%10, sumUp+total)
    else:
        return recursiveDigitsSplitAdded(digits//10, total+digits%10, sumUp)

def recursiveDigitsAdded(digits):

    return recursiveDigitsSplitAdded(digits, 0, 0)

print(recursiveDigitsAdded(3528)) --> 27
print(recursiveDigitsAdded(99999999999884)) --> 132

数字を一桁ずつ足していき、その合計値が一桁になるまで同じ処理を繰り返し、最後にそれぞれの合計値を返す処理になっています。
例：recursiveDigitsAdded(3528) 3 + 5 + 2 + 8 = 18 →　1 + 8 = 9 →　18 + 9 = 27
ただ、recursiveDigitsAdded(99999999999884)を実行するとエラーになります。
原因は、再帰処理の許容度を超えている為だと思います。
再帰関数でrecursiveDigitsAdded(99999999999884)を実行させるには条件式を見直すべきでしょうか？
自分では、改善案が思い付かないので質問させていただきました。
ご教授頂けると幸いです????‍♂️

Answer 1

今回のような桁数が大きな整数を渡すような場合は、文字列として扱った方がいいような気がします。

再帰の回数は今回の場合には問題ないと思います。
以下の例でもわずか３回程度です。

def recursiveDigitsAdded(digits, total):
    dig_list = [int(i) for i in digits]
    sub = sum(dig_list)

    if sub < 10:
        return sub + total
    else:
        total += sub

    return recursiveDigitsAdded(str(sub), total)

if __name__ == '__main__':
    ans = recursiveDigitsAdded(str(99999999999884), 0)
    print(ans)

Comments

[_ryu_]

回答ありがとうございます。
内包表記を使う発想はありませんでした。
勉強になります。

[otn]

内包表記を使うかどうかは本質じゃないです。
この回答は、
「数字の和を求める部分を再帰じゃなくてループにすることでプログラムを簡単にする」
ということです。
再帰にこだわらないなら簡単です。

Answer 2

再帰回数は初期状態である程度の回数で制限されています。通常ならデフォルトは1000回。
変更するには、sys.setrecursionlimit(n)で上限n回まで変更できます。
ただし無制限にすることはできません。実行環境にもよりますが2,3万くらいでpython側がクラッシュします。

なので基本的にはこの設定に頼らないアルゴリズムを考える必要があるでしょう。
特にこの例では20000でも終わらないし。

この問題では再帰を使わずとも簡単に計算することが可能です。
whileでループさせましょう。
ヒントは、digitsを/10していくといつか0になるので、digitsが0になればwhileから抜けらるようにすればよいのです。

Comments

[_ryu_]

回答ありがとうございます。
sys.setrecursionlimit(n)で上限変更できることは知りませんでした。
ただ無制限にできないことに注意が必要なんですね。勉強になります。
whileを使った解き方考えてみます。