你能解释一下以下代码的工作原理吗？

Question

// 这是一个检查给定数组是否通过递归排序的函数

#include<iostream>
using namespace std;
bool sorted(int arr[],int n)
{
    
    if(n==1)
    {
        return true;
    }

我很困惑，当 n 达到 1 时，它会 return 对“restArray”为真，如果数组未排序，那么“restArray”将如何变为假？

    bool restArray = sorted(arr+1, n-1);
    
    return (arr[0]<=arr[1] && restArray);
}

int main()
{
    int arr[]={1,6,3,4,5};
    cout<<sorted(arr,5);
    return 0;
}

Answer 1

因为在每个递归中有两种情况

首先是简单的情况 if (n == 1)：大小为 1 的数组（即只有一个元素）总是排序的。因此它 returns true 并停止递归

如果 n 仍然大于 1，则进行递归调用并检查没有第一个元素的数组是否已排序 (bool restArray = sorted(arr+1, n-1))，然后检查是否数组的第一个元素小于第二个元素 (a[0] < a[1])。（顺便说一句，我可能会在这里检查 <=）最后你将这两个检查与 &&.

结合起来

因此对于您的示例，它会在某个时间点检查 6 < 3，这将 return false 因此总体结果将变为 false。

但是为了优化，我建议稍微重新排序您的语句，这样如果数组中前两个元素的顺序已经错误，您就不需要递归调用。正如@Scheff 的 Cat 在评论中提到的那样：当您将其转换为尾递归时，任何有缺陷的编译器都能够将该递归重构为（便宜得多的）迭代 ...

而且我还会检查 n <= 1，否则如果您的方法被（错误地！）调用 n = 0，您可能会陷入无限递归。

bool sorted(int arr[],int n)
{
    if (n <= 1)
    {
        return true;
    }

    return arr[0] <= arr[1] && sorted(arr+1, n-1);
}

甚至更简单

bool sorted(int arr[], int n) {
  return n <= 1 
    ? true
    : arr[0] <= arr[1] && sorted(arr+1, n-1);
}

你能解释一下以下代码的工作原理吗？

Could you please explain me the the working of following code?

c++

arrays

sorting

recursion