Skip to content

Problem 2: F91 (100pts)

Problem

The f91 function is a recursive function, defined by the computer scientist John McCarthy as a test case for formal verification within computer science.

Write a recursive function f91 that takes a single argument n,

  • returns n - 10 when n > 100

  • returns f91(f91(n + 11)) when n ≤ 100

函数 f91 是一个递归函数，由计算机科学家 John McCarthy 定义，作为计算机科学中形式化验证的测试用例。

编写一个递归函数 f91，它接受一个参数 n，

  • 当 n > 100 时，返回 n - 10

  • 当 n ≤ 100 时，返回 f91(f91(n + 11))

def f91(n):
    """Takes a number n and returns n - 10 when n > 100,
    returns f91(f91(n + 11)) when n ≤ 100.

    >>> f91(1)
    91
    >>> f91(2)
    91
    >>> f91(100)
    91
    """
    "*** YOUR CODE HERE ***"

Q: It seems that the argument of f91's recursive calls is not always simpler in terms of less-than relation of integers.

A: Oh, the meaning of "simpler" is not that simple ...

Q: f91 的递归调用参数似乎在整数的“小于”关系上并不总是更简单。

A: 哦，更简单 的含义可没那么简单......

Hints

  • 写一个普通的递归。

Solutions

一个普通的递归。

def f91(n):
    if n > 100:
        return n - 10
    else:
        return f91(f91(n + 11))

def f91(n):
    return n - 10 if n > 100 else f91(f91(n + 11))