这两个递归函数可以合并成一个吗?

Question

int sorted_a(int arr[], int N)
{
if (N == 1 || N == 0)
return 1;
if (arr[N - 1] < arr[N - 2])
{
return 0;
}
return sorted_a(arr, N - 1);
}
int sorted_d(int arr[], int N)
{
if (N == 1 || N == 0)
return 1;
if (arr[N - 1] > arr[N - 2])
{
return 0;
}
return sorted_d(arr, N - 1);
}

这是两个单独的递归函数来检查数组是否按升序或降序排序(它们为每种情况返回一个)，我似乎找不到一种方法来只使用一个来完成这项工作(函数必须返回1，只有当它被排序时，无论顺序(升序或降序))。有什么帮助吗?

编辑:也许我的问题还不够清楚。我只是想创建一个问题，返回1只有当数组排序(无论排序升序/降序的方向)，否则返回0。

Answer 1

由于大多数解决方案一次只处理升序/降序一个，或者对我来说过于复杂，这里有一个[非递归]版本，在单个函数中一次性测试升序/降序:

int
sorted(const int *arr,int N)
{
int sorted = 0x03;
do {
if (N < 2)
break;
int prev = arr[0];
int cur;
for (int idx = 1;  idx < N;  ++idx, prev = cur) {
cur = arr[idx];
// get difference
int dif = cur - prev;
// the same -- no change in state
if (dif == 0)
continue;
// one of the sort directions is [now] wrong
if (dif < 0)
sorted &= 0x01;
else
sorted &= 0x02;
// both directions are unsorted -- stop early
if (! sorted)
break;
}
} while (0);
return sorted;
}

Answer 2

一种直接的方法是在函数中添加一个参数，该参数将指定数组被检查排序的顺序。

这是一个示范程序。

#include <stdio.h>
int sorted( const int a[], size_t n, int ascending )
{
return n < 2 || ( ( ascending ? !( a[1] < a[0] ) : !( a[0] < a[1]) ) &&
sorted( a + 1, n - 1, ascending   ) );

}
int main(void) 
{
int a[] = { 1, 1, 2, 2, 3, 3 };
size_t n = sizeof( a ) / sizeof( *a );

printf( "a[] is sorted - %sn", sorted( a, n, 1 ) ? "true" : "false" );
int b[] = { 3, 3, 2, 2, 1, 1 };
n = sizeof( b ) / sizeof( *b );

printf( "b[] is sorted - %sn", sorted( b, n, 0 ) ? "true" : "false" );
int c[] = { 3, 3, 1, 1, 2, 2 };
n = sizeof( c ) / sizeof( *c );

printf( "c[] is sorted - %sn", sorted( c, n, 1 ) ? "true" : "false" );
return 0;
}

程序输出为

a[] is sorted - true
b[] is sorted - true
c[] is sorted - false

Answer 3

任务，即检查数组是否排序，不是使用递归函数解决的任务。使用简单的for/while循环代替。

进一步-为什么要花时间将两个函数合并为一个?好的编程实际上是把东西分解成简单的函数。你已经有了两个简单的函数，所以你可以这样做:

int sorted(int arr[], int N)
{
return sorted_a(arr, N) || sorted_d(arr, N);
}

也就是说，在某些情况下(为了性能和/或资源使用)使用单个"更复杂的"代码是有意义的。函数而不是一些简单的函数。然而，这并不适用于这里，因为方法(即递归函数)从一开始就是错误的。

无论如何-你的两个函数可以合并，但结果代码是真正糟糕的.

这里有一个例子，但是不要这样做

int sorted(int* arr, int N)
{
if (N < 2) return 1;
if (arr[0] == arr[1]) return sorted(arr+1, N - 1);

if (arr[0] > arr[1])
{
if (arr[N - 1] > arr[N - 2])
{
return 0;
}
}
else
{
if (arr[N - 1] < arr[N - 2])
{
return 0;
}
}
return sorted(arr, N - 1);
}

使用for/while代替递归。

Answer 4

首先，将原始函数转换为循环以消除递归。例如，第一个是:

int sorted_a(int arr[], int N) {
while(N > 1) {
if (arr[N - 1] < arr[N - 2]) {
return 0;
}
N--;
}
return 1;
}

下;添加2个标志，一个代表"仍可能上升"。另一个是"仍有可能下降"，所以你可以将所有内容合并到一个函数中:

int sorted(int arr[], int N) {
int a = 1;
int d = 1;
while(N > 1) {
if( a != 0) {
/* Still possibly ascending */
if (arr[N - 1] < arr[N - 2]) {
if( d != 0) {
/* Not ascending and can't be descending */
return 0;
}
a = 0;   /* Not ascending (but could still be descending) */
}
}
if( d != 0) {
/* Still possibly descending */
if (arr[N - 1] > arr[N - 2]) {
if( a != 0) {
/* Not descending and can't be ascending */
return 0;
}
d = 0;   /* Not descending (but could still be ascending) */
}
}
N--;
}
return 1;
}

这个版本可能比只有2个单独的版本慢(除了不太可能的情况-例如，当数组以重复的相同数字开始时，像{1, 1, 1, 1, 1, ...持续直到它比缓存大)。尽管如此，对于你的问题，这是一个可行的答案("是的，它们可以合并!")。

然而;在循环中只有3种情况(仍然可能是升序或降序，仍然可能是升序但不降序，仍然可能是降序但不升序)。这意味着您可以将合并的版本分成3个部分，以避免一些(if(a == 0))分支，并摆脱标志，如:

int sorted(int arr[], int N) {
if(N < 2) {
return 1;
}
while(N > 1) {
if (arr[N - 1] != arr[N - 2]) {
if (arr[N - 1] > arr[N - 2]) {
return sorted_a(arr, N-1);
} else {
return sorted_d(arr, N-1);
}
}
N--;
}
return 1;
}
int sorted_a(int arr[], int N) {
while(N > 1) {
if (arr[N - 1] < arr[N - 2]) {
return 0;
}
N--;
}
return 1;
}
int sorted_d(int arr[], int N) {
while(N > 1) {
if (arr[N - 1] > arr[N - 2]) {
return 0;
}
N--;
}
return 1;
}

这是我能想到的最快的(但我不认为"当它有助于性能时合并，但当它损害性能时不合并")。是你要求的，所以…)