Skip to content

Problem 1: Functional Power (100 pts)

Problem

The n-th functional power of a function \(f\), denoted \(f^n\), is defined as the result of applying the function \(f\) repeatedly to its own output, \(n\) times. Formally, it is defined as:

\[f^n(x)=\underbrace{f(f(\ldots f(x)\ldots))}_{f\mathrm{~appears~}n\mathrm{~times}}\]

For example:

  • \(f^3(x)=f(f(f(x)))\)
  • \(f^2(x)=f(f(x))\)
  • \(f^1(x)=f(x)\)
  • \(f^0(x)=x\) (This represents the identity function.)

Define a higher-order function make_power such that given a function \(f\) and a natural number \(n\), make_power(f, n) returns the n-th functional power of \(f\), which is the function \(f^n\).

函数 \(f\) 的第 \(n\) 次函数幂（或 \(n\) 次复合），记作 \(f^n\)，定义为将函数 \(f\) 重复应用于其自身的输出，\(n\) 次所得的结果。形式上，它定义为：

\[f^n(x)=\underbrace{f(f(\ldots f(x)\ldots))}_{f\mathrm{~出现~}n\mathrm{~次}}\]

例如：

  • \(f^3(x)=f(f(f(x)))\)
  • \(f^2(x)=f(f(x))\)
  • \(f^1(x)=f(x)\)
  • \(f^0(x)=x\) （这代表恒等函数。）

定义一个高阶函数 make_power，它接受一个函数 \(f\) 和一个自然数 \(n\)，make_power(f, n) 返回 \(f\) 的第 \(n\) 次函数幂，即函数 \(f^n\)。

def make_power(f, n):
    """Return f^n, the n-th functional power of f,
    such that f^n(x) = f(f(...f(x)...)) where f appears n times.

    >>> square2 = make_power(square, 2)
    >>> square2(2)
    16
    >>> add_three = make_power(increment, 3)
    >>> add_three(5)
    8
    """
    "*** YOUR CODE HERE ***"

Hints

Hint1: f is guaranteed to be a function that takes a single argument.

Hint2: Use iteration to solve this problem since we have only taught iteration so far. Do not use recursion.

  • \(f\) 是一个只接受一个参数的函数。

  • 因为到目前为止我们只教授了迭代（iteration），所以请使用迭代来解决此问题。请勿使用递归（recursion）。

  • 递归次数过多时会触发 RecursionError，如果能想办法不触发，那么就可以通过OJ。

  • 建议从0次幂开始算。

Solutions

因为返回值是一个函数，所以我们需要定义一个辅助函数（被返回的函数）来解决这个问题。

def make_power(f, n):
    # 辅助函数，用于定义 f^n(x) 的行为
    def helper(x):
        # 初始结果就是 x
        result = x
        # 计数器，用于追踪 f 应用的次数
        count = 0

        # 使用 while 循环，重复应用函数 f n 次
        while count < n:
            # 将函数 f 应用到当前结果上，更新 result
            result = f(result)
            # 计数器加 1
            count = count + 1

        # 循环结束后，result 就是 f^n(x) 的结果
        return result

    # 返回定义的辅助函数 helper，它就是 f^n
    return helper

由于样例所给值较大，会超过递归深度，我们一般不方便使用递归。但也可以修改递归深度。

identity = lambda x: x

def make_power(f, n):
    # 修改递归深度限制
    import sys
    sys.setrecursionlimit(50000)

    # 递归
    return identity if n == 0 else lambda x: f(make_power(f, n - 1)(x))