在紅寶石遞歸

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]