通过递归检查数组是否已排序

Question

您能解释一下以下代码的工作原理吗？这是一个检查给定数组是否通过递归排序的函数：

#include<iostream>
using namespace std;

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

    // I am confused here when n will reach 1 then it will 
    // return true to `restArray` after that if array is 
    // not sorted then how will `restArray` become false?
    
    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

（即只有单个元素）的数组始终是排序的。因此它返回

true

并停止递归

如果

n

仍然大于

1

，则执行递归调用并检查没有第一个元素的数组是否已排序（

bool restArray = sorted(arr+1, n-1)

），然后检查数组的第一个元素是否小于第二个元素 (

a[0] < a[1]

)。 （顺便说一句，我可能会在这里检查

<=

）最后，您将这两项检查与

&&

结合起来。

因此，对于您的示例，它将在某个时间点检查

6 < 3

，这将返回

false

，因此整体结果将变为

false

。

但是为了优化，我建议稍微重新排序你的语句，这样如果数组中前两个元素的顺序已经错误，你就不需要递归调用。正如 @Scheff's 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);
}