Rekursion zu Iteration

[Ronni018]

Hallöchen,

in der Schule hab ich eine Aufgabe zum Thema Rekursion / Iteration. Und zwar sollen wir eine neue Funktion, in welcher ein
Problem iterativ gelöst wird, so schreiben, dass sie das gleiche Problem löst, wie die Funktion unten rekursiv.

Code: Alles auswählen

function werbinich_rek (k: integer):integer;
begin
if k <=1 then begin
     if k=0 then result:=0;
     else result :=1;
     end;
else result:=k + werbinich_rek(k-2);
end;

Ich habe keine Ahnung wie das gehen soll und habe gedacht, dass ich vielleicht in diesem Forum hier, Hilfe bekomme.
Danke schonmal für die Antwort(en).

[Winni]

Hallo!

Schule hat wieder angefangen!

Also so wie Du Deinen Code aufgeschrieben hast, ist der niemals durch einen Compiler gelaufen:
Kein Semicolon vor else !!

Wenn Du rekursiv nach linear umwandelst, dann must Du erstmal wissen: Was ist das Abbruchriterium des rekusiven Aufrufs?

Das ist in Deinem Fall:

Code: Alles auswählen

if k <=1 then ...

weil ja nur auf dem else-Zweig der rekusive Aufruf erfolgt.

Wie wird die Function recursiv aufgerufen? Indem k jedesmal um 2 dekrementiert wird ( -2 )

Außerdem können wir uns nicht mehr bei einer linearen Abarbeitung auf result verlassen, weil wir das ja in einer einzigen linearen Prozedur abwickeln wollen. Also brauchen wir eine Variable die die Summe mit sich schleppt.

Dann haben wir:
Statt der rekursiven Aufrufe brauchen wir eine Schleife, die solange "schleift" bis das Abbruchkriterium erreicht ist - nämlich k<= 1. Zweitens summieren wir alles auf.

Hier mal Deine Version in korrigiert und die lineare Version:

Code: Alles auswählen

function werbinich_rek (k: integer):integer;
begin
if k <=1 then
     begin
	      if k=0 then result:=0
	      else result :=1;
     end
     else
       result:=k + werbinich_rek(k-2);
end;


function werbinich_lin (k: integer):integer;
var fertig : Boolean;
    sum : Integer;
begin
sum := 0;
fertig := false;
while not fertig do
begin
    if k <=1 then
    begin
	      if k=0 then sum := sum+0  // Blödsinn, aber zur Verdeutlichung
	      else sum := sum +1;
     fertig := true;
     end else
        begin
        sum := sum+k;
        k := k -2;
    end;
end; //while
result := sum;
end;

Falls was unverständlich ist: Fragen.
Als Lehrer hab ich noch nie getaugt.

Winni

PS.: Alter Merksatz:

Um Rekursion zu verstehen, muss man Rekursion verstanden haben ......