在红宝石递归

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

在这种情况下，只要把print语句来执行这些代码，并与值。你会看到：

$ 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]