0

通常、スタック オーバーフローは具体的な問題のために予約されていますが、パズルに頭を抱えており、誰かがそれを説明できるかどうか疑問に思っていました。私は再帰を検討していて、Dave Thomas の Code Kata (非常にクール) に出会いました。私は楽しんで自分なりの答えを作り、それを絞り込もうとしていますが、理解できない答えが 1 つあります。

問題：コード型 #2 http://codekata.pragprog.com/2007/01/kata_two_karate.html

うまくいく答えですが、なぜここにあるのか理解できません:

def chop(target, values)  
  # Special handling for zero and single element arrays
  return -1 if values.empty?
  return ((target == values[0]) ? 0 : -1) if values.length == 1

  # Try the bottom half first
  pos = chop(target, values[0, values.length/2])
  return pos if pos != -1

  # Then the upper half ... remember that the returned
  # position is relative to the middle of the array.
  pos = chop(target, values[values.length/2, values.length-1])
  return pos + (values.length/2) if pos != -1

  # Didn't find what we were looking for
  return -1
end

インデックスがこの再帰パターンをどのようにバックアップするかを誰かに説明してもらえますか?

私がそれを読んだとき、それはその数に達して0を返すまで再帰します。なぜ/どのようにこのことがインデックスを吐き出すのか、私の人生ではわかりません。

4

1 に答える 1

0

このような再帰的なコードを処理する最善の方法は、return ステートメントから始めることです。" return pos + (values.length/2) if pos != -1" 行で魔法が起こります。

コードを英語で言い換えると、「見つかった要素 (0 または正の数) の位置を、元の配列内の指定された配列のオフセットに追加する」.

基本的に、呼び出しチェーンを遡る途中で数回呼び出され、最終的な回答のアキュムレータとして機能します。これを実際に確認するには、次を試してください。

def chop(target, values)
  return -1 if values.empty?
  if values.length == 1
    return ((target == values[0]) ? 0 : -1)
  end
  pos = chop(target, values[0, values.length/2])
  return pos if pos != -1
  pos = chop(target, values[values.length/2, values.length-1])
  # Print some info
  if pos != -1
    puts [pos, (values.length/2)].inspect
    return pos + (values.length/2)
  end
  return -1
end
于 2012-08-17T02:39:22.793 に答える