ruby - Ruby 中的递归

Question

我正在编写一个选择排序，当我传入一个数组时我让它工作，但是当我尝试使用递归时，它给了我一个堆栈太深的错误。我做错了什么？

def selectionSortRecursive(array, arrayPosition)
   if arrayPosition == (array.length-1)
      puts "End of the line folks!"
      return array
   end   
   while arrayPosition >= 1 && array[arrayPosition] < array[arrayPosition - 1] do 
    puts "This is pass #{arrayPosition}"
    if array[arrayPosition] < array[arrayPosition - 1]
      tmp = array[arrayPosition]
      array[arrayPosition] = array[arrayPosition - 1]
      array[arrayPosition - 1] = tmp
    end # end if
    arrayPosition += 1
  end
  selectionSortRecursive(array, arrayPosition)
  return array
end

这是我用来测试它的：

selectionSortRecursive(array, 1)

Answer 1

在这种情况下，只需输入打印语句即可查看执行了哪些代码以及使用了哪些值。你会看到：

$ ruby -w t4.rb 
t4.rb:21: warning: mismatched indentations at 'end' with 'while' at 10
initial array=[4, 3, 2, 1], initial position=2
last_pos=3
This is pass 2 cur=2  pre=3
after switching elements : [4, 2, 3, 1]
This is pass 3 cur=1  pre=3
after switching elements : [4, 2, 1, 3]
initial array=[4, 2, 1, 3], initial position=4
last_pos=3
initial array=[4, 2, 1, 3], initial position=4
last_pos=3
initial array=[4, 2, 1, 3], initial position=4
last_pos=3
initial array=[4, 2, 1, 3], initial position=4
last_pos=3
.......
t4.rb:2: stack level too deep (SystemStackError)

要停止递归，您需要检查一些条件。看看数百万个总是用来解释递归的阶乘或斐波那契例子。

我不确定你想如何排序，但这段代码有效：

def selectionSortRecursive(array, arrayPosition)
   puts "initial array=#{array}, initial position=#{arrayPosition}"
   initial_array_position = arrayPosition
   last_pos = array.length - 1
   puts "last_pos=#{last_pos}"
   if arrayPosition == (last_pos)
      puts "End of the line folks!"
      return array
   end   
   while arrayPosition >= 1 && arrayPosition <= last_pos && array[arrayPosition] < array[arrayPosition - 1] do
    cur = array[arrayPosition]
    pre = array[arrayPosition - 1]
    puts "This is pass #{arrayPosition} cur=#{cur}  pre=#{pre}"
    if array[arrayPosition] < array[arrayPosition - 1]
      tmp = array[arrayPosition]
      array[arrayPosition] = array[arrayPosition - 1]
      array[arrayPosition - 1] = tmp
      puts "after switching elements : #{array}"
    end # end if
    arrayPosition += 1
   end
   selectionSortRecursive(array, arrayPosition) if arrayPosition != initial_array_position
   return array
end

p selectionSortRecursive([4,3,2,1], 2)

执行 ：

$ ruby -w t4.rb 
initial array=[4, 3, 2, 1], initial position=2
last_pos=3
This is pass 2 cur=2  pre=3
after switching elements : [4, 2, 3, 1]
This is pass 3 cur=1  pre=3
after switching elements : [4, 2, 1, 3]
initial array=[4, 2, 1, 3], initial position=4
last_pos=3
[4, 2, 1, 3]