best. rekursive funktion erklären

[Delphi-Joe]

hallo,

hab eine problem beim verstehen folgender rekursiven funktion:

Delphi-Quellcode:

function funktion(x, y:byte): byte; 
begin 
  if (x<>2*y) then
    funktion:=funktion(x-1,y-1) + funktion(x,y);
end;

könnt ihr mir das prinzip erklären?

[barnti]

Hallo,

das wird schwer. Die Funktion liefert kein Ergebnis!

[Dax]

Hi!

Wenn x doppelt so groß ist wie y, legt diese Funktion deinen Rechner lahm, ansonsten liefert sie, wie barnti schon gesagt hat, kein Ergebnis.

[Delphi-Joe]

es kommt ja nur auf die funktionsweise an. was wird getan? vielleicht ist es leichter mit einem struktogramm zu erklären?

[Nikolas]

Das mit dem fehlenden Ergebniss stimmt nicht!
Wenn man dem Funktionsnamen einen Wert zuweisst, ist das gleichbedeutend mit einer Zuweisung an result.

Kannst du vielleicht mal erklären, was diese Funktion ausrechnet? Dann könnte es einfacher werden sie zu verstehen

[dizzy]

Für x<>2*y ist es eine Endlosrekursion, und für alle anderen Fälle ist die Rückgabe unbestimmt. So ziemlich das sinnlosete was ich bisher gesehen hab :mrgreen:

[Delphi-Joe]

Das diese Rekursion eine Endlosrekursion ist ändert doch nicht an der Tatsache, das der Computer die Daten verarbeitet? Die Frage ist nun, was der Computer bei dieser speziellen Rekursion arbeitet und wie Toxman vorhin schon richtig bermerkt hat, gibt es in diesem Beispiel Rückgabe.

[alcaeus]

Hi Delphi-Joe,

Ergebnis wirds keins geben. Das hängt einfach damit zusammen, dass selbst falls die Rekursion nicht unendlich wäre, trotzdem kein Ergebnis zugewiesen wird. Das heißt, an der Wurzel des Rekursionsbaumes gibts nur ein undefiniertes Ergebnis, somit sind alle weiteren Ergebnisse auch undefiniert.

Greetz
alcaeus

[Blechwolf]

Zitat:

Zitat von Toxman

Das mit dem fehlenden Ergebniss stimmt nicht!
Wenn man dem Funktionsnamen einen Wert zuweisst, ist das gleichbedeutend mit einer Zuweisung an result.

Wie Toxman schon richtig gesagt hat, kann die Funktion durchaus ein Ergebnis zurückliefern. Damals bei Turbo/Borland Pascal gabs sowas wie ein Result noch nicht. Da ging das nur so.

Was die Funktion macht ist so relativ schwierig zu erklären. Setz doch einfach mal ein paar Werte für x und y ein und dann guck Dir das Ergebnis an. Wenn Du dann ne Vermutung hast, kannst Du die mit Vollständiger Induktion beweisen und weißt wie das ganze im Allgemeinen Fall aussieht. RWTH Aachen Informatik Grundstudium 1. Semester... (Kluuuugscheißer...)
:warn:

Problematisch an der Sache ist der zweite Teil der Addition. Da die Funktion mit den unveränderten Werten wieder aufgerufen wird, hast Du quasi ne schöne Schleife.
Ich versuch mal ein Ablaufdiagramm zu malen und Dir das dran zu hängen...

Grüße

Wolf

[Niels]

Zitat:

Zitat von Blechwolf

Zitat:

Zitat von Toxman

Das mit dem fehlenden Ergebniss stimmt nicht!
Wenn man dem Funktionsnamen einen Wert zuweisst, ist das gleichbedeutend mit einer Zuweisung an result.

Wie Toxman schon richtig gesagt hat, kann die Funktion durchaus ein Ergebnis zurückliefern. Damals bei Turbo/Borland Pascal gabs sowas wie ein Result noch nicht. Da ging das nur so.
...

Hallo,
das ist schon richtig, dass man anstatt result den Funktionsnamen benutzen kann. Jedoch endet die Rekursion wenn x = 2*y. Wenn dieser Fall eintritt wird jedoch kein Ergebnis zugewiesen. Das "else" fehlt hier also.

Ich persönlich seh in der Funktion auch keinen Sinn.

MfG Niels

[edit]
Mir ist grad nochwas aufgefallen. Der rechte Teil der Zuweisung

Delphi-Quellcode:

funktion:=funktion(x-1,y-1) + funktion(x,y);

wird immer wieder mit den Ausgangswerten aufgerufen. Ein Funktionsaufruf endet also immer in einer Endlosrekursion, außer auf die Ausgangswerte trifft zu: x = 2*y. Hier kommt's aber zu dem oben bereits erklärten Problem (unbestimmtes Ergebnis, was eben grad an der Stelle im RAM steht).
[/edit]

[MathiasSimmack]

Zitat:

Zitat von Niels

[edit]
Mir ist grad nochwas aufgefallen. Der rechte Teil der Zuweisung

Delphi-Quellcode:

funktion:=funktion(x-1,y-1) + funktion(x,y);

wird immer wieder mit den Ausgangswerten aufgerufen.[/edit]

Das hat der Blechwolf schon vor ´ner Stunde bemerkt. :zwinker:

[Jelly]

Das Problem in der ganzen Rekursion ist, daß du keinen Startwert hast. Abgesehen von der Abbruchbedingung, berechnest du immer deine Funktion mit Vorwerten. Du brauchst aber einen Startwert, um deine Reihe überhaupt zu beginnen... Das kannst du mit dem Bsp vergleichen, daß du eine Zahl immer mit 2 multiplizierst, bis der Endwert > 100 wird. Du brauchst aber eine Startzahl, mit dem du beginnen kannst.

Gruß,
Tom

[Niels]

Zitat:

Zitat von MathiasSimmack

Zitat:

Zitat von Niels

[edit]
Mir ist grad nochwas aufgefallen. Der rechte Teil der Zuweisung

Delphi-Quellcode:

funktion:=funktion(x-1,y-1) + funktion(x,y);

wird immer wieder mit den Ausgangswerten aufgerufen.[/edit]

Das hat der Blechwolf schon vor ´ner Stunde bemerkt. :zwinker:

Tut mir leid :oops: ...bissl mehr schlafen und bissl weniger Kaffe wäre vielleicht besser :wink:

[glkgereon]

trotzdem bleibt die frage was die function macht...denn:

wenn sie mit x=2*y aufgerufen wird, dann wird sie ohne ergebniss beendet
wenn aber x<>2*x dann
wird immer wieder die function mit x-1 und y-1 aufgerufen
und dann mit den startwerten aufgerufen, wo es zu ner endlosschleife kommt.....

daher hat diese function keinen erkennbaren sinn....

denkbar wäre da schon eher sowas:

Delphi-Quellcode:

function funktion(x, y:byte): byte;
begin
  if (x<>2*y) then
    funktion:=funktion(x-1,y-1) + funktion(x,y);
end;

was das nu wieder bringt is ne andere frage....

[Jelly]

Zitat:

Zitat von Delphi-Joe

Delphi-Quellcode:

function funktion(x, y:byte): byte; 
begin 
  if (x<>2*y) then
    funktion:=funktion(x-1,y-1) + funktion(x,y);
end;

Zitat:

Zitat von glkgereon

Delphi-Quellcode:

function funktion(x, y:byte): byte;
begin
  if (x<>2*y) then
    funktion:=funktion(x-1,y-1) + funktion(x,y);
end;

Bitte wo ist denn da der Unterschied :gruebel:

[glkgereon]

:oops: :oops: :oops:

ich wollte eigentlich das schreiben:

Delphi-Quellcode:

function funktion(x, y:byte): byte;
begin
  if (x<>2*y) then
    funktion:=funktion(x-1,y-1) + funktion(x+1,y+1);
end;

[Niels]

Zitat:

Zitat von glkgereon

:oops: :oops: :oops:

ich wollte eigentlich das schreiben:

Delphi-Quellcode:

function funktion(x, y:byte): byte;
begin
  if (x<>2*y) then
    funktion:=funktion(x-1,y-1) + funktion(x+1,y+1);
end;

Hi,
ist irgendwie kein bisschen besser, weil eine Seite wieder zu ner Endlosrekursion führt und das "else" immer noch fehlt.

MfG Niels :thumb:

[glkgereon]

hmm :gruebel:

stimmt....

aber weisst du was uns die "arbeit" wesentlich erleichtern könnte?

wenn Delphi-Joe uns verraten würde ob es a) nur ein mehr oder minder dummes beispiel war oder b) was das tuen soll....