python - この関数を再帰関数として書き直す方法は?

Question

def digits(n):
    res = []
    while n > 0:
        res.append(n % 10)
        n /= 10
    return res

この関数を書き直して、再帰を使用するようにします。どうしようか迷っているのが現状です。誰かが私に指示を与えることができますか？

Answer 1

再帰関数を作成するには、次の 2 つのことを決定する必要があります。

1) 基本ケース - 再帰を停止したい条件

2) 一般的なケース - 基本ケース以外のすべての入力で何をすべきか

基本ケースは while ループの条件であり、一般的なケースは while ループの内部です。この情報を使用して、前進してください。

Answer 2

考えられる解決策は次のとおりです。

def digits(n):
    if n < 10:
        return [n]
    return digits(n/10) + [n%10]

digits(123)
> [1, 2, 3]

上記の解決策により、コードのバグが修正され、数字が逆順で返されていました。またn、正しい結果を生成するには、ゼロ以上の整数でなければならないことに注意してください。

仕組みは次のとおりです。

1. 数値が 10 未満の場合は、処理する桁がないため、その数値を含むリストを返します。
2. 数値が 9 より大きい場合は、現在の数値の最後の桁を取得し、それをdigits小さい数値 (つまり、処理したばかりの最後の桁のない数値) を再帰的に呼び出した結果のリストの末尾に追加します。

への呼び出しdigits(123)は、再帰の各ステップで次のようになります。

digits(123) = digits(123/10) + [3]
digits(12)  = digits(12/10)  + [2]
digits(1)   = [1]

次に、コール スタックを上に移動します。

[1]
[1] + [2]
[1, 2] + [3]
[1, 2, 3]

編集 ：

@ thg435 の挑戦を受けて、末尾再帰のソリューションを次に示します。

def digits(n):
    def loop(i, acc):
        if i < 10:
            return [i] + acc
        return loop(i/10, [i%10] + acc)
    return loop(n, [])

Answer 3

def digits(n):
    res = []
    res.append(n%10)
    n /= 10
    if n != 0:
        return res + digits(n)
    else:
        return res

Answer 4

再帰を使用する場合、ベース ケースと再帰ケースの 2 つのケースをチェックすることをお勧めします。基本ケースは、プログラムが返す条件と結果です。あなたの場合、基本ケースは n > 0 の場合です (while ループのように考えると、while ループが終了する条件です)。while ループと比較すると、これは基本的にループの本体です。再帰的なケースの最後に、入力への変更で関数を再度呼び出す必要があります。この場合は n/10 です。

したがって、関数定義は次のようになります。

def digits(n):

基本ケースでは、n が 0 かどうかを確認し、0 の場合は空のリストを返します。

    if n <= 0:
        return []

ここで、再帰的なケースでは、リストに n%10 を追加して関数を再度呼び出したいと考えていますが、while ループで使用したように変更された別の n で呼び出したいだけです。

    else:
        return [n%10]+digits(n/10)

したがって、これをたどると、再帰的なケースごとに n%10 を含むリストが得られ、新しい呼び出しの結果が追加されます。これは (n/10)%10 または空のリストのいずれかになります。たとえば、この関数を n=100 で実行すると、次のように分解されます。

newlist = digits(100)
newlist = [100%10]+digits(100/10)
newlist = [100%10]+([10%10] + digits(10/10))
newlist = [100%10]+([10%10] + ([1%10] + digits(10/10)))
newlist = [100%10]+([10%10] + ([1%10] + ([])))
newlist = [0,0,1]

ネストされた括弧は、関数の数字がインラインで書き換えられる方法を示すために使用されます。