6

配列の最大要素を計算する次のコードについて考えてみましょう。

#include <stdio.h>

int maximum(int arr[], int n)
{
    if (n == 1) {
        return arr[0];
    } else {
        int max = maximum(arr, n-1);
        printf("Largest element : %d\n", max);
        return 5; // return arr[n-1] > max ? arr[n-1] : max;
    }
}

int main()
{
    int array[5] = {5, 23, 28, 7, 1};
    printf("Maximum element of the array is: %d", maximum(array, 5));
    return 0;
}

elseブロックが 4 回呼び出されるのはなぜですか?

4

5 に答える 5

4

この関数は再帰的であるため、複数回呼び出されます。

最初に開始するときは、n=5 です。else ブロックを使用します (n は 1 ではありません)。次に、 n-1 (n=4) で maximum を再度呼び出します。繰り返しますが、else ブロックが取得されます。

つまり、関数は n が 1 に達する前に 4 回呼び出され、その後 if ブロックを取り、ar[0] を返します。

他の人が述べたように、書かれた関数はリストの最大値を返しません。興味深いことに、リスト配列のサイズが 1 でない限り、常に 5 を返すようです。1 の場合は、その要素の値を返します。

代わりに、再帰的なアプローチでは通常、リストを毎回半分に分割し、リストが最終的に要素のペアに分割されたときに各ペアの最大値を返します。

于 2012-09-05T16:41:47.773 に答える
3

それがコード化されていることです...

見てみましょう：

main から maximum を 5 で呼び出し、else で関数を n-1 で再度呼び出します。

maximum(array, 5)  //first call from main, hit the else n=5, so recall with n-1
maximum(ar, 4)     //second call from maximum, hit the else n=4, so recall with n-1
maximum(ar, 3)     //third call from maximum, hit the else n=3, so recall with n-1
maximum(ar, 2)     //fourth call from maximum, hit the else n=2, so recall with n-1
maximum(ar, 1)     //fifth call from maximum, n==1 now so do the if and return 5
于 2012-09-05T16:47:09.550 に答える
2

考えられる再帰的な解決策は、前の要素と現在の要素を比較することです。

#include <stddef.h>

static int max(int a, int b) {
    return a > b ? a : b;
}
int max_array(int *p, size_t size)
{
    if (size > 1)   return max(p[size-1], max_array(p, size-1));
    else            return *p;
}
于 2012-09-05T16:48:48.610 に答える
1

実際には4回しか呼び出されません。

あなたが宣言したように、再帰規則は次のとおりです。n == 1の場合、ar [0]を返し、それ以外の場合は最大n-1要素を返します。

そのため、else 部分は 5、4、3、および 2 に対して呼び出されています。

ただし、この再帰は十分ではありません。関数が n-1 回呼び出されるため、再帰のオーバーヘッド (スタックなど) のみが発生しますが、反復に対する利点はありません。

このタスクに本当に再帰が必要な場合は、配列を 2 に分割し、それぞれの半分を再帰関数に渡してみてください。

単純な擬似コード (奇数を正しく処理していない):

int max(int arr[], int n)
{
    if (n<=1)
        return arr[0];
    return MAX(max(arr, n/2), max(arr+n/2, n/2));
}
于 2012-09-05T16:46:52.067 に答える
0 
int maximum(int ar[], int n)
{
  int max;
  if(!n)
    return ar[n];
  max =maximum(ar,n-1);
  return ar[n]>max?ar[n]:max;
}
于 2012-09-05T16:54:11.743 に答える