Python如何不使用运算符、仅靠递归和给定工具函数比较两个整数大小

实现思路 #

核心逻辑为同步递减两个输入整数，直到其中至少一个数触发zero判断条件，通过终止状态判定大小：

• 若b先变为0：此时如果a不为0，说明a原值更大，返回True；如果a也同时为0，说明两数相等，返回False
• 若a先变为0：此时b必然还大于0，说明a原值小于等于b，直接返回False
• 两数均未到0时，递归调用gt函数，传入两个数各自递减1之后的结果即可

完整实现代码 #

def gt(a, b):
    '''Returns True if a is an integer greater than b;
       returns False otherwise'''
    # 仅使用给定的incr、decr、zero工具函数和递归实现
    if zero(b):
        return not zero(a)
    if zero(a):
        return False
    return gt(decr(a), decr(b))


def incr(a):
    '''Returns the next integer after a'''
    return a + 1

def zero(a):
    '''Returns True if a is zero'''
    return a == 0

def decr(a):
    '''Returns the integer before a'''
    return a - 1

效果验证用例 #

• gt(5, 3) 预期返回True：同步递减3次后b变为0，a剩余2，返回not zero(2)即True
• gt(2, 4) 预期返回False：同步递减2次后a变为0，b剩余2，直接返回False
• gt(4, 4) 预期返回False：同步递减4次后a、b同时为0，返回not zero(0)即False

注：上述实现默认输入为非负整数，符合该类算法题的常规前置设定

内容的提问来源于stack exchange，提问作者Fahim Ferdous