如何用遞歸重新賦值？

Question

給定一個層次結構（如輪廓），其中每個層次都由一個整數表示（例如，第一個層次爲0，第二個層次爲1，並且任何時候您都可以在較早的層次上開始一個新點），則I想要重新分配整數，以便數字不會被跳過，但同時要尊重原始關係。我已經表示的輸入作爲數組：

$stuff = array(0,1,2,2,4,1,9,9,10,3,8,4);

和（當被表示爲陣列）所期望的輸出是：

$stuff = array(0,1,2,2,3,1,2,2,3,2,3,3);

規則是：

• 如果給定值與最接近的先前值相同，則輸出值應該與最接近的之前的輸出值相同
• 如果給定值比最近的先前值更高（即更深），那麼輸出值應該大於最接近的前一個輸出值的值
• 如果給定值比最近的值更低（即更淺）之前的值，然後找到最接近的先前值小於給定值，並且輸出值應該比那個值大1。

我認爲這樣做的唯一方法是通過遞歸。除了上述輸入數組中的最後一種情況外，我可以爲它工作。如果我將輸入數組中的最後一個案例更改爲「5」而不是「4」，那麼它將起作用。

這裏就是我想：

<?php 

$input = array(0,1,2,2,4,1,9,9,10,3,8,4); 
$debug = false; 
for ($i =0; $i < count($input); $i++) { 
    if ($debug) { 
     echo '<hr />Old level: '.$input[$i]; 
     $newLevel = newLevel($input,$i,$input[$i],$debug); 
     echo '<br />New level: '.$newLevel.'<br /><br /><br /><hr />'; 
    } 
    else { 
     echo 'Old level: '.$input[$i].'; New level: '.newLevel($input,$i,$input[$i],$debug).'<br />'; 
    } 
} 

function newLevel($input, $index,$origValue,$debug) { 
    if ($index == 0) return 0; 
    else { 
     if ($input[$index] > $input[$index-1]) { 
      if ($debug) echo '<br />Orig value: '.$origValue.' in else/if'; 
      return newLevel($input,$index-1,$origValue,$debug)+1; 
     } 
     elseif ($input[$index] == $input[$index-1]) { 
      if ($debug) echo '<br />Orig value: '.$origValue.' in else/elseif1'; 
      return newLevel($input,$index-1,$origValue,$debug); 
     } 
     elseif ($input[$index] < $input[$index-1]) { 
      for ($i = $index-2; $i >= 0; $i--) { 
       if ($input[$index] == $input[$i]) { 
        if ($debug) echo '<br />Orig value: '.$origValue.' in else/elseif2/for/if'; 
        return newLevel($input,$i,$origValue,$debug); 
       } 
       elseif ($input[$index] == ($input[$i] + 1)) { 
        if ($debug) echo '<br />Orig value: '.$origValue.' in else/elseif2/for/elseif'; 
        return newLevel($input,$i,$origValue,$debug); 
       } 
      } 
       die ("Error with going to outer level -- should never hit this."); 
     } 
    } 
} 

?> 

這是我想要的輸出：

Old level: 0; New level: 0 
Old level: 1; New level: 1 
Old level: 2; New level: 2 
Old level: 2; New level: 2 
Old level: 4; New level: 3 
Old level: 1; New level: 1 
Old level: 9; New level: 2 
Old level: 9; New level: 2 
Old level: 10; New level: 3 
Old level: 3; New level: 2 
Old level: 8; New level: 3 
Old level: 4; New level: 3 

但我得到的輸出有一個「2」最後的新水平線。任何幫助非常感謝它。

Answer 1

其實，你根本不需要遞歸。你在不使用遞歸的情況下很好地解釋了你的算法，所以你的代碼也不需要它。

這是我的算法版本，沒有遞歸。

$original = array(0,1,2,2,4,1,9,9,10,3,8,4); 
$revised = array(); 

foreach($original as $index=>$value) { 
    $output = 0; 
    $previous = false; 

    if ($index > 0) 
     $previous = $original[$index-1]; 

    if ($previous === false) 
     $output = 0; 
    else if ($value == $previous) 
     $output = $revised[$index-1]; 
    else if ($value > $previous) 
     $output = $revised[$index-1] + 1; 
    else { 
     $output = 1; // worst case scenario 
     for($rindex = $index-1; $rindex >= 0; $rindex--) { 
      if ($value > $original[$rindex]) { 
       $output = $revised[$rindex]+1; 
       break; 
      } 
     } 
    } 

    $revised[] = $output; 
} 

echo "\n"; 
print_r($original); 
print_r($revised);