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

Question

我尝试过但未能这样做.我可以向正确的方向努力吗？

Answer 1

我首先要强调的是,这通常是递归的一个非常糟糕的用法.最好的递归解决方案倾向于相当快地减少解决方案的"搜索空间",例如二进制搜索在每次迭代时移除剩余搜索空间的一半.

如果减数与minuend相比相对较小(其中minuend - subtrahend给出差异),则重复减法将导致大量递归调用并且很可能耗尽堆栈空间.

话虽如此,下面的解决方案只是伪代码,因为它可能是功课:

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

它通过反复减去b从a,并且正在下降的水平,直到你再也不能减去b从a没有变成负值.然后它返回递归树,为你下降的每个级别添加1.

这只适用于非负值a和正值b(因此是divu无符号的名称),虽然将其修正为负数并且除以零只是一点额外的工作.

处理标志和错误的一些提示:

• 如果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)