19

貪欲法や動的計画法などの高度なアルゴリズムの概念を理解するには、まず再帰に精通している必要があります。

私は再帰に比較的慣れていません。質問がなされるたびに、最初に頭に浮かぶのは、反復を使用したソリューションです。再帰的な方法が何を意味し、どのように機能するかは知っていても、再帰的に考えるのは非常に困難です。

以下の質問に答えてください。

1) 反復法を再帰に置き換えることはできますか、またその逆は可能ですか?

たとえば、サイズ n の配列の要素を再帰的に出力する方法は?

for i 0 to n
 Print a[i]

2) 問題を再帰的に解決する方法は? 手順は何ですか？問題を再帰的に解決できることを特定するためのヒントはありますか?

例: 文字列のすべての部分文字列を出力するように求められた場合

INPUT: CAT
OUTPUT: CAT,CA,A,AT,T

反復的な方法をすばやく思いつくことができます。2 つのループを使用すると、問題を解決できます。

しかし、再帰的にそれを解決する方法。問題が再帰的に解決できることを特定する方法。

最初の質問に対する答えが「はい」の場合、反復の代わりに 2 つの再帰を使用することで問題を解決できますか?

3)再帰の概念を完全に理解するための資料/リソースを誰かに提案してもらえますか?

4

8 に答える 8

1

再帰関数を使用して反復問題を解決できると思いますが、最も効率的なアプローチではない可能性があります。Python3 で「for ループ」と「再帰」の両方を使用してリスト内のアイテムを出力する簡単な例を次に示します。

a = [ 1,2,3,4,5] 
#iterative approach using a for loop
for i in nums:
   print(i)

#recursive approach
def printing_list(nums):
    #base case
    if len(nums)==0:
        return
    #recursive
    else:
        print(nums[0])
    return printing_list(nums[1:])

printing_list(nums)

再帰的に考えるには、最初に for ループを作成してから、それに基づいて再帰的なソリューションを作成してみるのが最善かもしれません。すべての再帰的アプローチには、再帰を停止するための基本ケースが必要であることを覚えておいてください

于 2021-11-09T17:54:20.510 に答える
1

CAT の問題は次のように解決できます: (Python コード)

s = "CAT"
op = []
def sub(s):
    # terminating condition.
    if (len(s) == 0) : return

    if s not in op : op.append(s)
    
    # slices from begning
    sub(s[1:])
    # slices from the end
    sub(s[:-1])

sub(s)
print(op)

Output : ['CAT', 'AT', 'T', 'A', 'CA', 'C']
于 2020-11-13T14:37:52.930 に答える