使用連續減法分割兩個數字的遞歸函數

Question

我已經嘗試過但未能這樣做。我能朝正確的方向推動嗎？

Answer 1

我應該先強調一下，這通常是遞歸的一個非常糟糕的用法。最好的遞歸解決方案傾向於相當快地減少解決方案的「搜索空間」，例如二進制搜索在每次迭代中刪除剩餘搜索空間的一半。

如果減數與減數相比相對較小（其中minuend - subtrahend給出了差異），則會產生大量遞歸調用，並且很可能會耗盡您的堆棧空間。

---

說了這麼多，下面的解決方案是在僞代碼而已，因爲它可能是功課：

def divu (a, b): 
    if a < b return 0 
    return divu (a - b, b) + 1 

它通過反覆地從a減去b，並且下降的水平，直到你不能再從a中減去b而不會變負。然後它返回遞歸樹，爲每個關卡添加1。

這將只和a非負值（因此divu名無符號）的b正值工作，雖然固定它底片和除以零是隻有一點點額外的工作。

一些提示進行操作標誌和錯誤：

• 檢測直線上升，如果b等於零和退出有一個錯誤，異常，或一些其他機制。
• 將-a/-b視爲a/b。
• 將-a/b作爲-(a/b)。
• 將a/-b設爲-(a/b)。
• 否則，只要工作a/b。

這是可能的處理在一個單一的遞歸調用這些特殊的情況，但在每個水平遞歸增加了不必要的檢查。這也可能是更有效地提供檢查功能div然後可以調用divu做遞歸位，是這樣的：

def div (a, b): 
    if b == 0 
     exit with error 
    if a < 0 and b < 0: 
     return divu (-a, -b) 
    if a < 0: 
     return -divu (-a, b) 
    if b < 0: 
     return -divu (a, -b) 
    return divu (a, b)