13

非常に迅速で簡単な宿題の質問. 私は問題なく動作していますが、もっと良い
方法があると思います。より Pythonic な方法。
リストの各要素を 1 ずつ再帰的にデクリメントするコードを次に示します。 

l = range(30)  
def recurseDecrMap(l, x = []):  
    if len(l) == 0:  
        return []  
    else:  
        x.append(l[0] -1)  
    recurseDecrMap(l[1:], x)  
    return x

ご意見ありがとうございます。私はより良い再帰を行うことを学ぼうとしています。
コツをつかむのに苦労しています。

4

7 に答える 7

25

おそらくpythonicではありませんが、次のとおりです。

def recurseDecrMap(l):
    return [l[0]-1] + recurseDecrMap(l[1:]) if l else []
于 2013-04-27T23:33:49.063 に答える
14

使用できる引数は 1 つだけです。私の意見では、より単純です。

def recurseDecrMap(l):  
    if not l:  
        return []  
    else:
        return [l[0]-1] + recurseDecrMap(l[1:])

しかし、@jamylak が指摘したように、このアルゴリズムの複雑さは O(N^2)です。これl[1:]は、リスト内の残りの項目への参照を含む新しいリストを作成するためです。

効率が必要な場合は、リスト内包表記 ( Haidro の回答) を使用することをお勧めしますが、学習目的のみで使用する場合は優先事項ではないと思います。

于 2013-04-27T23:27:15.433 に答える
9

本質的に再帰的ではないことを行うために使用しているため、これは再帰について学ぶにはひどい方法です。[1, 2, 3, 4] リストの要素をrecursivelyのようにデクリメントするプログラムを書くように先生が本当に求めているのなら、恥を知れ。

Haidro が指摘したように、この問題を解決する最も Pythonic な方法は、リスト内包表記を使用してリストを反復処理することです。

[i - 1 for i in l]

ループとして、これは

def decr(l):
    a = []
    for i in l:
        a.append(i - 1)
    return a

再帰は、任意の深さレベルで同じ問題を解決したい場合に役立ちます。たとえば、次のようなものが[1, [2, 3], [[4], 5]]あり、リスト構造を維持しながら、各数値を 1 ずつ減らしたいとします。その場合、再帰的なソリューションは、基本ケースに反復ソリューションを使用し、再帰的なケースに対してそれ自体を呼び出します。

def decr_recursive(l):
    a = []
    for i in l:
        if isinstance(i, list):
            a.append(decr_recursive(i))
        else:
            a.append(i - 1)
    return a

リストや整数以上のものをサポートしたい場合は、これを簡単に変更できます。

>>> decr([1, [2, 3], [[4], 5]])
[0, [1, 2], [[3], 4]]

これは、再帰を使用せずに解決するのが非常に難しい種類の問題ですが、再帰を使用すると簡単に解決できます。あなたが求めているのは、再帰なしで簡単に解決できる種類の問題です（神のためにリストを単純に繰り返すだけです）が、それで解決するのはやや難しいです。

Python で再帰を避けるべきいくつかの理由

  • 読みにくいです。[i - 1 for i in l]、または明示的なループでさえ、次のようなものと比較してください

    def decr(l):
    if not l:
        return []
    return [l[0] - 1] + decr(l[:1])

  • Python で関数を呼び出すと、コストがかかる場合があります。私のコンピューターでは、Ashwini Chaudhary とほぼ同じタイミングが得られます。しかし[i - 1 for i in range(10**4)]、私のコンピューターでは 559 µs かかります。これは、最速の再帰的方法よりも 3 桁高速です。

  • 再帰制限を高く設定しない限り、再帰関数は 1000 回を超える呼び出しでは機能しません。sys.setrecursionlimit(10**5)Ashwini Chaudhary の回答でその呼び出しに気付いたかもしれません。これがないと、各呼び出しがRuntimeError: maximum recursion depth exceeded次の巨大なトレースバックにつながるため、これが必要です。ただし、これを使用しても、リストが少し大きくなると、再帰の制限が発生します。また、ドキュメントによると、すべての OS に上限があり、設定が高すぎるとクラッシュする可能性があります。

  • 再帰関数はデバッグが難しくなります。同じ関数からの何百もの呼び出しでスタック トレースが汚染されるだけでなく、スタックのどのレベルにいるかによって、同じ関数の同じ部分がさまざまな方法で使用されているため、概念的に追跡するのが難しくなります。 . 自然な人間の考え方は反復的です。私たちは一度に1つずつ物事を行います。私たち自身の脳の「スタック」は数レベルの深さしかないため、再帰的な方法で問題を解決するのは非常に困難です。終わったら、元の問題を終わらせます。小さな問題でも、同じことをして、終わるまでに数レベル深くなるかもしれません。」だからあなたはペンを取りに台所に行き、それからキャンディーバーを見て食べ始め、食べ終わったらペンのことを忘れます。ペンの問題からキャンディーバーの問題まで、レベルを「再帰」し、メンタルスタックが深すぎました（2レベルだけですが、それで十分です）。代わりにキャンディーバーをつかんで、それを開いて食べ始める前にペンも見つけた場合（私が思いつくことができる最高の反復アナログ）、どちらも忘れずに両方を行います. プログラムで問題を解決する方法は、頭の中で問題を解決する方法とまったく同じでなければなりません。それが、コードが何をしているかを理解する唯一の方法だからです。Python は非常に優れた言語です。なぜなら、その高レベル インターフェイスにより、まさにそれが可能になるからです (少なくとも、低レベル言語よりも頻繁に)。ペンの問題からキャンディーバーの問題まで、レベルを「再帰」し、メンタルスタックが深すぎました（2レベルだけですが、それで十分です）。代わりにキャンディーバーをつかんで、それを開いて食べ始める前にペンも見つけた場合（私が思いつくことができる最高の反復アナログ）、どちらも忘れずに両方を行います. プログラムで問題を解決する方法は、頭の中で問題を解決する方法とまったく同じでなければなりません。それが、コードが何をしているかを理解する唯一の方法だからです。Python は非常に優れた言語です。なぜなら、その高レベル インターフェイスにより、まさにそれが可能になるからです (少なくとも、低レベル言語よりも頻繁に)。ペンの問題からキャンディーバーの問題まで、レベルを「再帰」し、メンタルスタックが深すぎました（2レベルだけですが、それで十分です）。代わりにキャンディーバーをつかんだが、それを開いて食べ始める前にペンも見つけた場合（私が思いつくことができる最高の反復アナログ）、どちらも忘れずに両方を行います. プログラムで問題を解決する方法は、頭の中で問題を解決する方法とまったく同じでなければなりません。それが、コードが何をしているかを理解する唯一の方法だからです。Python は非常に優れた言語です。なぜなら、その高レベル インターフェイスにより、まさにそれが可能になるからです (少なくとも、低レベル言語よりも頻繁に)。代わりにキャンディーバーをつかんだが、それを開いて食べ始める前にペンも見つけた場合（私が思いつくことができる最高の反復アナログ）、どちらも忘れずに両方を行います. プログラムで問題を解決する方法は、頭の中で問題を解決する方法とまったく同じでなければなりません。それが、コードが何をしているかを理解する唯一の方法だからです。Python は非常に優れた言語です。なぜなら、その高レベル インターフェイスにより、まさにそれが可能になるからです (少なくとも、低レベル言語よりも頻繁に)。代わりにキャンディーバーをつかんで、それを開いて食べ始める前にペンも見つけた場合（私が思いつくことができる最高の反復アナログ）、どちらも忘れずに両方を行います. プログラムで問題を解決する方法は、頭の中で問題を解決する方法とまったく同じでなければなりません。それが、コードが何をしているかを理解する唯一の方法だからです。Python は非常に優れた言語です。なぜなら、その高レベル インターフェイスにより、まさにそれが可能になるからです (少なくとも、低レベル言語よりも頻繁に)。それがコードが何をしているかを理解する唯一の方法だからです。Python は非常に優れた言語です。なぜなら、その高レベル インターフェイスにより、まさにそれが可能になるからです (少なくとも、低レベル言語よりも頻繁に)。それがコードが何をしているかを理解する唯一の方法だからです。Python は非常に優れた言語です。なぜなら、その高レベル インターフェイスにより、まさにそれが可能になるからです (少なくとも、低レベル言語よりも頻繁に)。この事実を利用してください！

于 2013-04-28T02:02:01.090 に答える
7

これが最悪の方法です - Fixed Point Combinatorを使用します:

Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))
recurseDecrMap = Y(lambda f: lambda l: [l[0]-1] + f(l[1:]) if l else [])
于 2013-04-27T23:49:40.707 に答える
2

簡単なpythonicの方法は次のとおりです。

>>> mylist = range(30)
>>> def func(l):
...     return [i-1 for i in l]
>>> func(mylist)
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]

説明：

リスト内包表記を使用して、値が元mylistの値よりも 1 小さいすべての要素の新しいリストを作成しました。

複数回使用する場合を除いて、コードに問題はありません。

>>> recurseDecrMap(l)
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]

>>> recurseDecrMap(l)
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]

これを回避するには、この回答を確認してください。

于 2013-04-27T23:22:29.393 に答える
2

これを行うさまざまな方法のタイミング比較:

In [1]: import sys

In [2]: sys.setrecursionlimit(10**5)

In [3]: from so import *

In [4]: %timeit recur(range(10**4)).show()
10 loops, best of 3: 18.2 ms per loop

In [5]: %timeit recurse1(range(10**4))
1 loops, best of 3: 559 ms per loop

In [6]: %timeit recurse2(range(10**4))
1 loops, best of 3: 1e+03 ms per loop

In [7]: %timeit recurse3(range(10**4))
1 loops, best of 3: 1.02 s per loop

In [8]: %timeit recurse4(range(10**4))
1 loops, best of 3: 596 ms per loop

コード：

class recur:
    # No extra memory is required in this method

    def __init__(self,lis):
        self.lis=lis
        self.len=len(self.lis)
        self.rec(0)

    def show(self):
        return self.lis

    def rec(self,n):
        if n!=self.len:
            self.lis[n]-=1
            self.rec(n+1)

def recurse1(l,lis=None):
    lis=lis if lis is not None else []
    if l:
        lis.append(l[0]-1)
        return recurse1(l[1:],lis)
    else:
        return lis

def recurse2(l):
    return [l[0]-1] + recurse2(l[1:]) if l else []

def recurse3(l):  
    if len(l) == 0:  
        return []  
    else:
        return [l[0] -1] + recurse3(l[1:])

def recurse4(l, x = []):  
    if len(l) == 0:  
        return []  
    else:  
        x.append(l[0] -1)  
    recurse4(l[1:], x)  
    return x
于 2013-04-27T23:25:54.843 に答える
1

これは、再帰の深さの制限に達することなく、大きなリストに対処できる再帰的なソリューションです。分割統治を使用すると、単純な再帰の O(N) と比較して、再帰の深さは最悪でも O(log(N)) になります。ただし、単純な for ループで簡単に解決できるため、この問題の手法として再帰を選択するのは適切ではありません。

def dec_list(xs, a, b):
    if b == a + 1:
        xs[a] -= 1
    if a + 1 >= b: return
    mid = (a + b) // 2
    dec_list(xs, a, mid)
    dec_list(xs, mid, b)

def dec(xs):
    dec_list(xs, 0, len(xs))

xs = range(1001)
dec(xs)
print xs
于 2013-04-28T06:10:51.663 に答える