5

私は再帰のアイデアにかなり慣れていないので、これは実際に再帰メソッドを書く最初の試みです。

最大の要素を出力するために、配列のサイズを保持する変数とともに、配列を渡す再帰関数 Max を実装しようとしました。

機能しますが、気分が良くありません。

また、一般的にクラスメートよりも static 修飾子を使用しているように見えることにも気付きました...

コードを改善する方法について、一般的なヒントとフィードバックを提供してもらえますか?

public class RecursiveTry{

static int[] n = new int[] {1,2,4,3,3,32,100};
static int current = 0;
static int maxValue = 0;
static int SIZE = n.length;

public static void main(String[] args){
    System.out.println(Max(n, SIZE));
}   

public static int Max(int[] n, int SIZE) {
    if(current <= SIZE - 1){
        if (maxValue <= n[current]) {
            maxValue = n[current];
            current++;
            Max(n, SIZE);                       
        }
        else {
            current++;
            Max(n, SIZE);
        }
    }
    return maxValue;
}

}

4

11 に答える 11

9

関数の外部で状態を保持するために静的変数を使用することは、困難の原因になります。

擬似コードでのmax（）関数の再帰的実装の例は次のとおりです。

function Max(data, size) {
    assert(size > 0)
    if (size == 1) {
        return data[0]
    }
    maxtail = Max(data[1..size], size-1)
    if (data[0] > maxtail) {
        return data[0]
    } else {
        return maxtail
    }
}

ここで重要なのは、Max（）の再帰呼び出しです。ここでは、最初の要素を除くすべてを渡し、サイズより1つ小さくします。一般的な考え方は、この関数は「このデータの最大値は最初の要素か、配列の残りの値の最大値のいずれか大きい方です」と言うことです。

この実装では、関数定義の外部に静的データは必要ありません。

再帰的実装の特徴の1つは、再帰が永久に（またはスタックオーバーフローが発生するまで）続くのを防ぐ、いわゆる「終了条件」です。上記の場合、のテストsize == 1は終了条件です。

于 2008-10-29T01:17:42.850 に答える
4

関数を静的変数に依存させることは良い考えではありません。再帰的なMax関数の可能な実装は次のとおりです。

int Max(int[] array, int currentPos, int maxValue) {
    // Ouch!
    if (currentPos < 0) {
        raise some error
    }
    // We reached the end of the array, return latest maxValue
    if (currentPos >= array.length) {
        return maxValue;
    }
    // Is current value greater then latest maxValue ?
    int currentValue = array[currentPos];
    if (currentValue > maxValue) {
        // currentValue is a new maxValue
        return Max(array, currentPos + 1, currentValue);
    } else {
        // maxValue is still a max value
        return Max(array, currentPos + 1, maxValue);
    }
}
...

int[] array = new int[] {...};
int currentPos = 0;
int maxValue = array[currentPos] or minimum int value;  
    maxValue = Max(array, currentPos, maxValue);
于 2008-10-29T01:28:45.887 に答える
3

「max」関数は、再帰関数を作成するのに間違ったタイプです。「current」と「maxValue」に静的な値を使用しているため、関数は実際には再帰関数ではありません。

階乗のように、再帰的アルゴリズムにもう少し従順なことをしてみませんか？

于 2008-10-29T01:14:03.777 に答える
2

「宿題じゃない」？

ともかく。まず最初に。ザ

static int[] n = new int[] {1,2,4,3,3,32,100};
static int SIZE = n.length;

名前を共有するMax（）のパラメーターとは何の関係もありません。これらをメインに移動すると、「静的」指定子が失われます。main（）内からMax（）の最初のインスタンスを呼び出すときに、これらは1回だけ使用されます。それらのスコープはmain（）を超えて拡張するべきではありません。

Max（）のすべての呼び出しが単一の「現在の」インデックスを共有する理由はありません。「current」はMax（）に対してローカルである必要があります。しかし、Max（）の連続した繰り返しは、使用する「current」の値をどのように知るのでしょうか。（ヒント：Max（）は、すでに他のMax（）の下位にいくつかのデータを渡しています。このデータに「current」を追加してください。）

maxValueについても同じことが言えますが、ここでの状況はもう少し複雑です。現在の「maxValue」を行に渡す必要があるだけでなく、再帰が終了したら、最初のMax（）関数に戻す必要があります。これにより、main（）に戻ります。他の再帰の例をいくつか見て、これに時間を費やす必要があるかもしれません。

最後に、Max（）自体は静的です。ただし、外部データ（静的変数）を参照する必要がなくなったら、それは本当に重要ではありません。これは、オブジェクトをインスタンス化せずにMax（）を呼び出すことができることを意味します。

于 2008-10-29T01:28:38.117 に答える
2

他の人が観察しているように、Max関数を実装するために再帰する必要はありませんが、新しい概念を試すために使い慣れたアルゴリズムを使用することは有益です。したがって、ここに簡略化されたコードがあり、以下に説明があります。

public class RecursiveTry
{
    public static void main(String[] args)
    {
        System.out.println(Max(new int[] {1,2,4,3,3,32,100}, 0, 0));
    }   

    public static int Max(int[] n, int current, int maxValue) 
    {
        if(current < n.Length)
        {
            if (maxValue <= n[current] || current == 0))
            {
                return Max(n, current+1, n[current]);
            }
            return Max(n, current+1, maxValue);
        }
        return maxValue;
   }
}

静的な状態はすべて不要になります。代わりに、すべてがスタックに渡されます。Max関数の内部ロジックは合理化されており、楽しみのために2つの異なる方法で再帰します。

于 2008-10-29T01:29:40.703 に答える
2

これがあなたのためのJavaバージョンです。

public class Recursion {

    public static void main(String[] args) {
        int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        System.out.println("Max: " + max(0, data));
    }

    public static int max(int i, int[] arr) {
        if(i == arr.length-1) {
            return arr[i];
        }

        int memo = max(i+1, arr);
        if(arr[i] > memo) {
            return arr[i];
        }
        return memo;
    }
}

再帰関係とは、配列の最大要素が最初の要素であるか、配列の残りの最大要素であるということです。配列の最後に到達すると停止条件に達します。メモ化を使用して、再帰呼び出しを (おおよそ) 半分に減らしていることに注意してください。

于 2008-10-29T02:44:36.233 に答える
0

基本的に反復バージョンを作成していますが、ループに末尾再帰を使用しています。また、非常に多くの変数を静的にすることで、基本的にオブジェクトの代わりにグローバル変数を使用しています。これは、典型的な再帰的実装に近いものへの試みです。もちろん、実際には、末尾呼び出しを最適化しないJavaのような言語を使用している場合は、ループを使用して「Max」関数を実装します。

public class RecursiveTry{
  static int[] n;

  public static void main(String[] args){
        RecursiveTry t = new RecursiveTry(new int[] {1,2,4,3,3,32,100});
        System.out.println(t.Max());
  }       

  RecursiveTry(int[] arg) {
    n = arg;
  }

  public int Max() {
    return MaxHelper(0);
  }

  private int MaxHelper(int index) {
    if(index == n.length-1) {
      return n[index];
    } else {
      int maxrest = MaxHelper(index+1);
      int current = n[index];
      if(current > maxrest)
        return current;
      else
        return maxrest;
    }
  }
}
于 2008-10-29T01:19:51.253 に答える
0

配列の最大値を再帰的に取得するより適切な方法は、クイックソート(優れた再帰的なソート アルゴリズム) を実装し、最初の値を返すことです。

これは、クイックソートの Java コードです。

于 2008-10-29T03:12:39.763 に答える
0

私が得ることができる最小のコードサイズ:

public class RecursiveTry {
    public static void main(String[] args) {
        int[] x = new int[] {1,2,4,3,3,32,100};
        System.out.println(Max(x, 0));
    }   

    public static int Max(int[] arr, int currPos) {
        if (arr.length == 0) return -1;
        if (currPos == arr.length) return arr[0];
        int len = Max (arr, currPos + 1);
        if (len < arr[currPos]) return arr[currPos];
        return len;
    }
}

いくつかのこと：

1/ 配列のサイズがゼロの場合、最大 -1 を返します (別のマーカー値、たとえば -MAX_INT を使用するか、例外をスローすることができます)。ここでは、コードを明確にするために、すべての値が 0 以上であると仮定しています。そうでなければ、（質問への回答に関して）あらゆる種類の不要なものをコードに追加していたでしょう。

2/私の意見では、終了ケースが最後のデータではなくデータなしの場合、ほとんどの再帰は「よりクリーン」です。したがって、配列を終了したときに最大値以下であることが保証された値を返します。他の人は意見が異なるかもしれませんが、彼らが間違っていたのは最初でも最後でもありません:-)。

3/ 再帰呼び出しは、リストの残りの最大値を取得し、それを現在の要素と比較して、2 つの最大値を返します。

4/「理想的な」解決策は、再帰呼び出しごとに変更された配列を渡して、最初の要素とリストの残りの要素のみを比較し、currPos の必要性をなくすことでした。しかし、それは非効率的であり、SOの怒りを買い取ったでしょう.

5/ これが必ずしも最善の解決策であるとは限りません。CAR、CDR、およびこれらの果てしなく続く括弧を使用した LISP の過度の使用により、灰白質が損なわれている可能性があります。

于 2008-10-29T03:45:51.897 に答える
0

これは、Scheme では非常に簡潔に記述できます。

(define (max l)
    (if (= (length l) 1)
        (first l)
        (local ([define maxRest (max (rest l))])
          (if (> (first l) maxRest)
              (first l)
              maxRest))))

確かに、これは配列ではなくリンクされたリストを使用しているため、サイズ要素を渡さなかったのですが、これにより問題が本質的に抽出されたと感じています。これは疑似コードの定義です:

define max of a list as:
    if the list has one element, return that element
    otherwise, the max of the list will be the max between the first element and the max of the rest of the list
于 2008-10-29T01:49:02.677 に答える
-2

まず、静的スコープの問題に対処しましょう...クラスはオブジェクトを定義していますが、実際にはオブジェクトをインスタンス化することはありません。mainは静的にスコープされているため、最初に行うことはオブジェクトを取得してから、次のようなメソッドを実行することです。

public class RecursiveTry{

    private int[] n = {1,2,4,3,3,32,100};

    public static void main(String[] args){
        RecursiveTry maxObject = new RecursiveTry();
        System.out.println(maxObject.Max(maxObject.n, 0));
    }

    public int Max(int[] n, int start) {
        if(start == n.length - 1) {
            return n[start];
        } else { 
            int maxRest = Max(n, start + 1);
            if(n[start] > maxRest) {
                return n[start];
            }
            return maxRest;
        }
    }

}

これで、静的スコープを必要としないmaxObjectという名前のRecursiveTryオブジェクトができました。従来のループ方式の反復回数はほぼ同等であるため、再帰を使用して最大値を見つけることが効果的かどうかはわかりませんが、再帰を使用すると、使用されるスタックの量が多くなります。しかし、この例では、私はそれをかなり削減します。

再帰の利点の1つは、反復の場合のように、繰り返しのテスト中に状態を永続化する必要がないことです。ここでは、開始点を保持するために変数を使用することを認めました。これは、最初の項目を除くすべての項目を含む新しいint []を渡すよりも、CPUの負荷が少ないためです。

于 2008-10-29T01:18:53.893 に答える