0

通常堆栈溢出是为有形问题保留的，但我正忙着解决一个难题，想知道是否有人可以解释它。我正在遍历递归并遇到了 Dave Thomas 的 Code Kata（非常酷）。我很高兴自己做出答案，然后试图减少它们，但有一个我无法弄清楚的回应：

问题：代码 Kata #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 回答