倒車使用recurion

Question

眼下打印順序，我已在下面的僞代碼

Printstations(fastest, path, lastpath, n) 
print "fastest solution requires" + fastest + "time units" 
print "line' + lastpath +"station" + n 
for j = n downto 2 
     print "line" + path[lastpath, j] + "station" + j-1 
     lastpath = path[lastpath, j] 

一個樣本輸出將是： 最快溶液需要14個時間單位： 線1，站4 線2，站3 第2行，第2行 第1行，第1行

我需要使用遞歸來反轉打印輸出的順序。 基本上，我需要它讀： 最快的解決方案需要14個時間單位： 線1，站1條 線2，站2 線2，站3 線1，站4

感謝。

因此，實質上，由於樣本的原因，車站訂單需要從讀數4下降到1，從站點1變爲1，行順序似乎沒有改變，但它實際上是因爲行號這裏創建一個迴文。我還沒有真正能夠獲得任何一致性。我很困惑如何遞歸可以改變順序。

我想出了這一點：

PrintStations(fastest, path, lastpath, n) 
if n = 0 
     print "fastest solution requires" + fastest + "time units" 
else 
     PrintStations(fastest, path, path[lastpath, n], n-1) 
     print "line" + lastpath + "station" + n 

我覺得可能工作，不能完全肯定，但。

Answer 1

您正處在正確的軌道上。您當前的輸出是這樣的：

fastest solution requires 14 time units: 
    line 1, station 4 
    line 2, station 3 
    line 2, station 2 
    line 1, station 1 

而且你想擁有這樣的輸出：

fastest solution requires 14 time units: 
    line 1, station 1 
    line 2, station 2 
    line 2, station 3 
    line 1, station 4 

爲了實現這個使用遞歸，你需要改變當前的解決方案：

PrintStations(fastest, path, lastpath, n) 
    if n = 0 
     COMMENT: incorrect, because this will be the last printed text, 
     COMMENT: this line should be called once at the begining 
     COMMENT: or even better before the recursive call is executed 
     print "fastest solution requires" + fastest + "time units" 
    else 
     COMMENT: better change the order of the resursive call and the print 
     PrintStations(fastest, path, path[lastpath, n], n-1) 
     print "line" + lastpath + "station" + n 

這將打印行更快的解決方案需要...在執行結束時，而不是在開始。我假設你從n開始並且不是0，因爲如果你從0開始，則永遠不會達到resursive call。

使用遞歸的一般方法是提取調用自己的函數，並最初從另一個函數執行它，因爲您需要一個起點。 您可以創建一個稱爲PrintSolution的功能，該功能採用與您的功能相同的參數，並從內部調用PrintStations。 這也將是打印最快的解決方案...文本的正確的地方：

COMMENT: this is now your starting point 
PrintSolution(fastest, path, lastpath, n) 
    print "fastest solution requires" + fastest + "time units" 
    PrintStations(fastest, path lastpath, n) 

你PrintStations也將變得更小，更容易讀/寫：

PrintStations(fastest, path, lastpath, n) 
    COMMENT: execution break condition is n == 0 
    if n > 0 
     COMMENT: print current path and station 
     print "line" + lastpath + "station" + n 
     COMMENT: call print station with next/previous path to print 
     PrintStations(fastest, path, path[lastpath, n], n-1) 

有當然是創建遞歸函數的其他可能性。不需要第二個函數可能看起來像這樣的解決方案：

variable m = n 
PrintStations(fastest, path, lastpath, n) 
    COMMENT: execution break condition is n == 0 
    if (n = m) 
     COMMENT: first call 
     print "fastest solution requires" + fastest + "time units"   
    if n > 0 
     COMMENT: print current path and station 
     print "line" + lastpath + "station" + n 
     COMMENT: call print station with next/previous path to print 
     PrintStations(fastest, path, path[lastpath, n], n-1) 

在這種情況下，你需要以打印第一行只有一次n變量的初始值。

的resursive調用等效於迭代，因爲它也依次運行在給定的數據結構：

print(3); 

COMMENT: equivalent to for (i = 3; i <= 1; i--) => 3 -> 2 -> 1 
for i = 3 downto 1 
    out i 

COMMENT: 3 -> 2 -> 1 
print(n) 
    if (n > 0) 
     print(n-1); 
     out n 

COMMENT: reverse the print - 1 -> 2 -> 3 
variable m = n 
print(n) 
    if (n <= m) 
     print(n+1); 
     out n 

另一種可能性是給斷點條件常數作爲參數：

print(n, m) 
    if (n <= m) 
     print(n+1, m); 
     out n 
COMMENT: initial call: print(1, 3) 

沒有準確的描述和關於路徑數組的更多信息（或至少是數據），很難編寫一個工作解決方案，但僞代碼朝着正確的方向發展。