使用连续减法分割两个数字的递归函数

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)