Rekursiver Horner-Schema-Algorithmus - Verstehe ich ihn richtig?

[Jack159]

Hallo,

Unten befindet sich der Algorithmus mit einem Beispielaufruf und darunter mit meiner Erklärung.
Habe ich die Rekursion richtig verstanden?

public class App {

	public static void main(String[] args) {
		
		
		int a[] = {5, 3, 1};
		System.out.println(horner(a, 2, 2));
		
		
	}
	
	
	 static int horner(int a[], int x, int n){
			int h;
			if(n>0)
			    h=horner(a, x, n-1);
			else
			    return a[n];

			return h*x+a[n];
	 }	
	 
	 
	
}

Zunächst geht er 1x in die if-Abfrage rein und setzt dann h=horner(a, x, n-1). Hier ist also der 1. Rekursionsaufruf erfolgt. Dann passiert dies nochmal (n ist nun 0) und horner wird ein 2. mal intern aufgerufen. Hier ist nun der 2. Rekursionsaufruf erfolgt. Nun ist die if-Abfrage n>0 falsch und er führt den else-Teil aus, indem er a[0] (=5) zurückgibt. Der 2. Rekursionsaufruf ist abgearbeitet, und er überspringt natürlich den else Teil da er ja vom if-Block kommt und gibt nun h*x+a[n] bzw. 5*2+3 zurück, und zwar gibt er dies als Antwort auf den 1. Rekursionsaufruf an h zurück. Also ist nun h=13. Dann wird wieder h*x+a[n] bzw 13*2+1 zurückgegeben, und zwar diesmal als Rückgabewert des ursprünglichen Funktionsaufruf in der System.out.println-Methode.

Habe ich die Rekursion richtig verstanden?

 

[nillehammer]

Um den genauen Ablauf eines Programms nachzuvollziehen, machen sich Log-Statements bzw. System.out.println an geeigneten Stellen ganz gut. Z.B. hier:

static int horner(int a[], int x, int n){
  // Mal nur so schnell hingekliert
  System.out.println("a[]=" + Arrays.toString(a) + ", x=" + x + ", n=" + n);

Das ist jedefalls verlässlicher, als wenn Menschen den Ablauf im Kopf nachvollziehen. Ich bin selbst nicht ganz unerfahren, aber habe mich nicht getraut, ohne Tests auf Deine Frage mit ja oder nein zu antworten.

 

[pappawinni]

Das Ganze mit Array rekursiv zu machen halte ich nicht für eine schöne Lösung.
Der dritte Paramter ergibt sich ja, wenn ich es recht habe, im Grunde aus der Länge des Array.
Wenn das schon sein muss, dann würde ich trotzdem vermeiden wollen einen Aufruf mit 3 Parametern zu erzwingen.
Für eine iterative Lösung würde man wohl eher keinen dritten Parameter fordern.
Es ginge vielleicht auch inetwa so, wenn es denn unbedingt eine Rekursion sein muss:

   static int horner(int a[], int x){
        return horner(int a[], int x, a.length-1)
   }

   private static int horner(int a[], int x, int n){
            int h;
            if(n>0)
                h=horner(a, x, n-1);
            else
                return a[n];
 
            return h*x+a[n];
     }

Ich hab auch online einige Berechnungen mit Java gefunden.
Ob das was taugt, weiss ich auch nicht. Da ist halt alles iterativ...z.B.
hier gefunden: Index of /~rudolph/num Horner.java

import java.lang.*;
// Implementierungsbeispiel für das vollständige Hornerschema
// Berechnung von Funktionswerten und Ableitungen für Polynome f(x) n-ten Grades
// die Koeefizienten des Polynoms werden von links nach rechts mit absteigenden Index als Parameter angegeben
// es müssen alle Koeefizienten angegeben werden (ggf 0)
// das letzte Argument ist x
// Aufruf java Horner 1 2 3 4
public class Horner {
	static int fac( int n){
	// berechne n Fakultät	
	int i, f = 1; // 0! und 1!
	for (i = 2; i <= n; i++)
	    f *= i;
	return f;	
	}
public static void main(String args[]){
  int i, j, k, n;          // Schleifenzähler und höchster Index
  double x = 1.0; // Variable

// ----------- Hilfe   
  if (args.length < 2){
     System.out.println("Berechnet den Funktionswert und alle Ableitungen eines Polynoms");
     System.out.println("Syntax: java Horner Koeffn .... Koeff0 x");
     System.out.println("Beispiel 1:");
     System.out.println("berechnet fuer x = 4 die Funktion f(x) = (x + 2) x + 3 und deren Ableitungen");
     System.out.println("java Horner 1 2 3 4");
     System.out.println("Beispiel 2:");
     System.out.println("berechnet fuer x = 5 die Funktion f(x) = (2x + 0) x + 3 und deren Ableitungen");
     System.out.println("java Horner 2 0 3 5");
     return ;
     }

// ----------- Dekodieren der Komandozeile
  n = args.length - 1;
  double [] a = new double [n]; // Deklaration des Koeffizientenvektors
  for (i = 0; i < n; i++){
  	a[i] = new Double (args[i].trim()).doubleValue();
      }
  x = new Double (args[args.length-1].trim()).doubleValue(); // letztes Argument ist x

// ----------- Anzeige der Funktion
  System.out.println("Polynomberechnung nach Horner");
  System.out.println("Grad n: " + (n - 1));
  System.out.print("Funktion: f(x) = ");
  for (i = 2; i < n; i++) System.out.print("(" );
  System.out.print(a[0]);
  if (n > 1) System.out.print(" x + " + a[1]);
  for (i = 2; i < n; i++) System.out.print(") x + " + a[i] );  
      System.out.println("");

// Berechnung der Werte nach dem vollständigen Hornerschema
//System.out.println("vollständiges Hornerschema");
  System.out.println("Ergebnisse fuer x = " + x);
   for (i = 0; i < n; i++){
   	for (j = 1; j < n - i; j++){
   		a[j] = a [j] + a[j - 1] * x;
   	}
   	if (i == 0)
    	    System.out.print("Funktionswert  f");
   	else
    	    System.out.print(i + "-te Ableitung f");
  	
   	for (k = 0; k < i; k++) System.out.print("'");
   	System.out.println("( " + x + " ) = " + a[j-1] * fac(i));
}
  return ;
  }
}// class