时间戳

首页 > 解决方案 > 这个递归函数有什么作用？什么是运行时复杂度？

c++ - 这个递归函数有什么作用？什么是运行时复杂度？

问题描述

我对以下代码感到困惑。到目前为止，我认为它将返回数组中具有 n 个元素的最小整数。但是，递归是如何工作的？而且，这个函数的运行时复杂度是多少？

int fun(int arr[], int n)
{
    int x;
    if (n == 1)
        return arr[0];
    else
        x = fun(arr, n - 1);

    if (x <= arr[n - 1])
        return x;
    else
        return arr[n - 1];
}

标签： c++recursion

解决方案

这确实是一个看起来很奇怪的函数，但我们可以将其转换为更熟悉的形式，更经典的递归函数。

首先让我们做一些重命名。n显然是数组的长度，所以我们重命名n为size. 您假设fun在数组中找到最小值，所以让我们从这个假设开始并重命名函数fun。最后，我们将看看假设是否正确。

由于在我们的then分支上if有一个return我们可以抛弃else. 我们将x声明移到第一次使用的地方：

int arr_min(int* arr, int size)
{
    if (size == 1)
        return arr[0];

    int x = arr_min(arr, size - 1);

    if (x <= arr[size - 1])
        return x;
    else
        return arr[size - 1];
}

现在我们清楚地看到了递归结束条件：n==1在这种情况下，我们只返回数组的唯一元素。

接下来我们重点介绍一下if/else。我们可以看到，这里的函数返回了两者之间的最小值x，arr[n-1]所以让我们这样写：

int arr_min(int* arr, int size)
{
    if (size == 1)
        return arr[0];

    int x = arr_min(arr, size - 1);

    return std::min(x, arr[size - 1]);
}

由于现在我们只读取x一次，我们可以摆脱这个命名错误的变量：

int arr_min(int* arr, int size)
{
    if (size == 1)
        return arr[0];

    return std::min(arr_min(arr, size - 1), arr[size - 1]);
}

这是与您所拥有的功能等效的功能，但具有更“经典”的递归形式。现在更容易看出该函数确实返回了数组的最小元素：

非空数组的最小元素是：

  • 如果数组大小为 1：第一个也是唯一的元素
  • 否则：它是最小的：
    • 最后一个元素和
    • 不包含最后一个元素的子数组的最小元素

现在也很容易看出时间复杂度。我会把它留给你弄清楚。

注意：现在应该很明显，该函数仅针对具有至少一个元素的数组定义。

作为奖励，我想用现代 C++ 重写这个函数：

constexpr int arr_min(std::span<const int> arr)
{
    if (arr.size() == 1)
        return arr.front();

    auto head = arr.first(arr.size() - 1);
    return std::min(arr_min(head), arr.back());
}

在您附近的未来标准中：

constexpr int arr_min(std::span<const int> arr)
    [[assert: !arr.empty()]]
{
    if (arr.size() == 1)
        return arr.front();

    auto head = arr.first(arr.size() - 1);
    return std::min(arr_min(head), arr.back());
}

推荐阅读