[pascal]Recursion

[roedie]

Nou, ik zit nu op stage en ben begonnen met het programeren in pascal. Heb dit een half jaar gehad op school, en omdat vele mij aanrade, en hier ook heb gelezen dat dit een goede taal is om mee te beginnen. Ben begonnen aan een tutorial en zit nu hardstikke vast. Hele middag mijn hersenen over gebroken en nu ga ik het hier neerzetten in de hoop er uit te gaan komen.

Eerst de oorzaak ervan, stukje en link naar de tutorial

http://web.mit.edu/taoyue/www/tutorials/pascal/pas4e.html

The summation function, designated by an uppercase Sigma in mathematics, is a popular example of recursion:

function Summation (num : integer) : integer;
begin
if num = 1 then
Summation := 1
else
Summation := Summation(num-1) + num
end;

Suppose you call Summation for 3.
a := Summation(3);

Summation(3) becomes Summation(2) + 3.
Summation(2) becomes Summation(1) + 2.
At 1, the recursion stops and becomes 1.
Summation(2) becomes 1 + 2 = 3.
Summation(3) becomes 3 + 3 = 6.
a becomes 6.
Recursion works backward until a given point is reached at which an answer is defined, and then works forward with that definition, solving the other definitions which rely upon that one.

Very important! All recursive procedures/functions must have some sort of test so stop the recursion. Under one condition, called the base condition, the recursion should stop. Under all other conditions, the recursion should go deeper. In the example above, the base condition was if num = 1. If you don't build in a base condition, the recursion will either not take place at all, or become infinite.

ik heb ook wat stukjes code gemaakt om mijn best doen het te begrijpen.

code:

program resuraction; uses crt;
var
   a, b : integer;

function Summation (num : integer) : integer;
   begin
      if num = 1 then
         begin
            sound(200);   delay(1000);   {9}
         writeln('if1: ',num,'* ');
            sound(400);   delay(1000);   {10}
         Summation:=1;
            sound(600);   delay(1000);   {11}
         writeln('if2: ',num,'* ');
            sound(800);  delay(1000);    {12}
         end
      else
         begin
            sound(1000);  delay(1000);      {1,3,5,7}
         writeln('else1: ',num,'* ');
            sound(1200);  delay(1000);      {2,4,6,8}
         Summation := Summation(num-1) + num;
            sound(1400);  delay(1000);       {13,15,17,19}
         writeln('else2: ',num,'* ');
            sound(1600);  delay(1000);       {14,16,18,20}
         end
   end;

begin
a := Summation(3);
writeln(' ',a,'* ');
end.

Deze code geeft als uitkomst:

else1: 3*
else1: 2*
if1: 1*
if2: 1*
else2: 2*
else2: 3*
6*

Hier heb ik mee zitten spelen en dacht dat ik het redelijk door heb. Tot op een punt waar ik het echt helemaal kwijt word. Ik heb tussen apostrofs de volgorde neergezet wat ik hoor zodat ik de code dacht beter te kunnen volgen.

Tot en met de uitvoer if1: 1* kan ik het volgen. Maar dan ook bij

code:

Summation:=1;

Wat doet ie hier. Een functie moet een waarde krijgen doormiddel van dit commando. Leuk, maar daarna zou summation de waarde 1 krijgen. Maar de code gaat nog door...

De 2 en de 3 die hij bij afgaand er vanaf heeft gehaald telt ie dan op bij de 1.

de 1 van summation:=1. Als je die varanderd veranderd die 1 dus mee. Verlaag of verhoog ik die gaat de uitkomst mee. Geef ik de parameter 4 ipv 3 mee telt ie dus 1x vaker af. en komt de waarde 4 erbij. De uitkomst word dan dus ook 4 hoger.

Dat kan ik volgen. Maar ik begrijp niet wat en waarom vanaf dat punt dat ik al aangaf. na {10} dus.

[Creepy]

Dat komt door je recursieve aanroep.

Na de aanroep gaat de code door waar ie gebleven is. Na het zetten van de result van de functie gaat de code ook nog gewoon door (dit is dus niet hetzelfde in C waarbij bij de return de functie meteen beeindigt word.)

Daarom krijg je je if2 (bij aanroep summation(1)) en ook je else2 nog twee keer ((bij aanroep summation(2) en summation(3)) te zien

Het eindresultaat 6 is 3+2+1 welke dus mooi recursief wordt opgebouwt.

Delphi:

function blaat: integer;
begin
  result:=6;
  writelln("woei");
end;

Bij bovenstaande code zal de writeln altijd uitgevoerd worden.

[ Voor 12% gewijzigd door Creepy op 17-12-2003 17:18 ]

[Verwijderd]

Hmmm, ik begrijp je probleem niet helemaal, je zegt dat je de recursie begrijpt, maar je vraagt je wel af wat

code:

Summation:=1;

Doet??

Nog even voor alle duidelijkheid:

Je roept een Summation aan met de waarde a.
a > 1 dus Pascal loopt door tot en met Summation(a-1)

Pascal onthoudt dat hij Summation(a) moet uitrekenen, maar omdat te doen moet deze eerst Summation(a-1) uitrekenen;

(a-1) > 1 dus Pascal loopt door tot en met Summation(a-2)

Pascal onthoudt dat hij Summation(a) moet uitrekenen, maar omdat te doen moet deze eerst Summation(a-1) uitrekenen, en omdat weer te doen moet hij eerst Summation(a-2) uitrekenen;

(a-2) = 1 dus Summation(a-2) := 1;

Pascal zal eerst de if functie afmaken en dan kan Summation(a-1) uitrekenen, en met het antwoord daarvan kan hij Summation(a) uitrekenen. Nu moet alleen nog de resterende code langslopen die gemist is (omdat die eerst opnieuw Summation in moest), om vervolgens uit de functie Summation te stappen en naar de regel toe te gaan nadat je summation hebt aangeroepen, klaar programma.


Maar misschien was deze recursie al geheel duidelijk en vroeg je iets anders

[roedie]

Ook, de magic word was, de code gaat verder wat ie nog niet afgemaakt had omdat hij ergens anders naartoe moest.

Mjah, recursion kan dus niet in C ? Tenminste daar word de code dan niet opnieuw afgemaakt.

Wat is een vertaling dan eigenlijk precies. Ik weet nu iig wel hoe ik er mee om moet gaan in pascal en wat je er mee kan. Nog een stukje wat ik vandaag gedaan heb. let niet op dat het niet echt mooie code is. Heb wat aan zitten klungelen.

code:

program TowersOfHanoi; uses crt;
var
   NumberOfDisks : integer;
procedure dotowers (disks, paalEen, PaalTwee, PaalDrie : integer);
   begin
      if disks = 1 then
         begin
         write(' if1: ',disks:2, paalEen:2, PaalTwee:2, PaalDrie:2);
         writeln('  ',paalEen,' naar ',paalDrie);
         write(' if2: ',disks:2, paalEen:2, PaalTwee:2, PaalDrie:2)
         end
      else
         begin
            write(' else1: ',disks:2, paalEen:2, PaalTwee:2, PaalDrie:2);
            dotowers (disks-1, Paaleen, Paaldrie, Paaltwee);
            write(' else2: ',disks:2, paalEen:2, PaalTwee:2, PaalDrie:2);
            writeln('  ',paalEen,' naar ',paalDrie);
            write(' else3: ',disks:2, paalEen:2, PaalTwee:2, PaalDrie:2);
            dotowers (disks-1, Paaltwee, PaalEen, Paaldrie);
            write(' else4: ',disks:2, paalEen:2, PaalTwee:2, PaalDrie:2)
         end
   end;
begin
   Writeln('Aantel schijfjes?');
   readln(NumberOfDisks);
   Writeln;
   dotowers(NumberofDisks, 1, 2, 3)
end.

deze laat pas echt mooi zien wat er precies gebeurd.

[curry684]

roedie schreef op 18 december 2003 @ 16:48:
Mjah, recursion kan dus niet in C ? Tenminste daar word de code dan niet opnieuw afgemaakt.

C en C++ zijn juist bij uitstek talen die door een duidelijk en strikt onderscheid tussen stackbased en static variabelen uitermate geschikt zijn voor recursie. Ik weet niet hoe je aan die conclusie komt maar ik zou de posts hierboven nog eens goed doorlezen

[roedie]

Ok.

Maar hoe weet ik eigenlijk van te voren hoe ik recursie hoe toe ga passen. Die tutorial gaf mij de opdracht dit te maken. Maar omdat ik er eerst niet uit kwam heb ik stiekem gespiekt. Nu wel helemaal overnieuwd gebouwd maar goed.

Hoe weet ik van te voren dat ik 2x in het "else" stuk toe ga passen? Nu kan dat wel via trial end error, Jah, ik weet dat ik dan veel vakker door de code heen scheur mjah, Iets van aanvalsplan. PSD ?

[Infinitive]

Recursie is een techniek die specifiek handig is voor bepaalde problemen. Dus niet een doel op zich

Een voorbeeld zijn problemen in de 'divide en conquer'-hoek. Je splitst een probleem op in een aantal kleinere delen. Zo'n kleiner deel komt overeen met het oorspronkelijke probleem en je kan exact dezelfde procedure er weer op toepassen. Daaruit komt een resultaat en deze combineer je tot een resultaat voor het grotere geheel. Je kunt je kleinere deelproblemen net zolang gaan opsplitsen totdat je problemen zo klein zijn dat je ze direct kan oplossen.

Een voorbeeld is het maximum berekenen in een array. Dat kan op verschillende manieren. Een manier is als volgt:
- ik haal en eerste elementje van de array af. Dan heb ik dat element en een rest-array.
- de rest array is weer een array, dus daar kan ik het maximum van berekenen via de procedure die ik nu aan het schrijven ben. (recursie).
- het maximum is dan het maximum van het huidige elementje en het maximum uit de rest-array. (combineren)
- je kan natuurlijk niet oneindig lang bovenstaande procedure herhalen. Op een gegeven moment heb je nog maar één elementje over. (basisgeval). Daarvoor weet je het antwoord al: het maximum van een array met maar één element is het element zelf.

Recursie kan wat oefening vereisen. Ik weet niet of een 'tower of hanoi' probleem wel het makkelijkste is om mee te beginnen.

[ Voor 6% gewijzigd door Infinitive op 18-12-2003 19:30 ]

[Creepy]

roedie schreef op 18 december 2003 @ 16:48:
Mjah, recursion kan dus niet in C ? Tenminste daar word de code dan niet opnieuw afgemaakt.

Dat bedoelde ik niet.

Delphi:

function woei: integer;
begin
  woei:=6;  // result := 6 mag ook.
  writeln("blaat");
end;

Result zet het resultaat van de functie. De uitvoer van deze functie zal gewoon verder gaan, dus blaat zal nog op het scherm worden gezet.

C:

int woei
{
  return 6;
  printf("blaat\n");
}

Return zet het resultaat van de functie, en zal ook meteen uit de functie springen. Die blaat zal dus niet meer op het scherm worden getoon.

Dit heeft uiteraard niks met het wel of niet ondersteunen van recursie te maken.

Dus na het zetten van de result gaat de functie gewoon door.

In het geval dat het resultaat wordt gezet door een functie zal eerst die functie compleet worden uitgevoerd, daarna het resultaat van die functie in het resultaat van de vorige gezet, en wordt de functie nog compleet uitgevoerd.

code:

function aftrekken(x: integer); // phun intended.
begin
 writeln(x);
 if x=0 then
    result:=x;
 else
   result:=aftrekken(x-1);
 writeln('einde van de functie: ' + x);
end;

als je nu aftrekken(0) aanroept zal het volgende verschijnen

code:

0
einde van de functie 0

Als je nu aftrekken(1) aanroept zal het volgende verschijnen

code:

1
0  //eerst wordt aftrekken weer aangeroepen
einde van functie 0  //in de laatste (!!) aanroep van aftrekken is x 0.
ende van de functie 1  //de eerste aanroep van aftrekken, x was hier 1 en is dat nog steeds.

[ Voor 46% gewijzigd door Creepy op 19-12-2003 08:42 ]

[roedie]

Ok, duidelijk(beide reply's hierboven) ty. Ik vond die tower of hanoi ook wel zware koek als je net een uitleg hebt gehad met 1 screen. Was dus ook niet gelukt zonder afkijken, maar ik zal eens opzoek gaan naar wat meer oefening

[Grijze Vos]

Infintive> Dat is wel heel erg functioneel gedacht. In een imperatieve taal zou je dat probleem oplossen door een lineair search, eventueel bounded...

[curry684]

Grijze Vos schreef op 19 december 2003 @ 11:11:
Infintive> Dat is wel heel erg functioneel gedacht. In een imperatieve taal zou je dat probleem oplossen door een lineair search, eventueel bounded...

Not to mention dat een recursieve aanpak van een lineair probleem op een platte array per definitie maximaal even snel maar meestal langzamer is dan de lineaire oplossing.

Recursie is vooral onmisbaar bij tree-problemen. Het handigste voorbeeld van recursie goed toegepast blijft toch gewoon de klassieke directory-tree van je computer, in pseudocode:

code:

function ShowDirectory(Path)
  foreach Element in OpenDirectory(Path)
    Print Element.Name
    if Element.IsDirectory
      ShowDirectory(Element.Path)
    end if
  end foreach
end function

[Soultaker]

Als je een expliciete boom hebt (in het geheugen bijvoorbeeld) dan is recursie ook al niet nodig; dan kun je voor depth-first traversal ook een lus als deze gebruiken:

code:

node = root;
while(node)
{
    // doe iets met 'node'

    if(node.first_child)
    {
         node = node.first_child;
    }
    else
    {
        do
        {
            if(node.next_sibling)
            {
                node = node.next_sibling;
                break;
            }
            node = node.parent;
        } while(node);
    }
}

Ik vind zelf recursie met name nuttig voor het langslopen of genereren van impliciete boomstructuren (het directory-traversal-voorbeeld was daar een goed voorbeeld van).

[tomato]

Soultaker schreef op 19 december 2003 @ 15:56:
Als je een expliciete boom hebt (in het geheugen bijvoorbeeld) dan is recursie ook al niet nodig; dan kun je voor depth-first traversal ook een lus als deze gebruiken:

Maar dan gebruik je wel dat de traversal state in de boom zelf opgeslagen wordt. Als je dat zelf moet gaan doen wordt het een veel minder elegante methode

[Soultaker]

tomato schreef op 19 december 2003 @ 17:23:
Maar dan gebruik je wel dat de traversal state in de boom zelf opgeslagen wordt. Als je dat zelf moet gaan doen wordt het een veel minder elegante methode

Hoe bedoel je dat precies? Je hoeft geen locale staat bij te houden behalve een pointer naar de huidige knoop ('node' in m'n pseudo-code).

[Grijze Vos]

curry684 schreef op 19 december 2003 @ 11:17:
[...]

Not to mention dat een recursieve aanpak van een lineair probleem op een platte array per definitie maximaal even snel maar meestal langzamer is dan de lineaire oplossing.

Ik zou het niet eens voor de tijdwinst doen (behalve als die tijdwinst echt groot is.) Maar meer voor de bewijslast. Een recursief programma is veel moeilijker te bewijzen dan een linear search. Een linear search is af te doen met het "linear search theorem", 3 regels bewijslast, een recursieve functie is veel meer werk.

Maar goed, dat is puur vanuit academisch oogpunt dan

[Infinitive]

Grijze Vos schreef op 19 december 2003 @ 11:11:
Infintive> Dat is wel heel erg functioneel gedacht. In een imperatieve taal zou je dat probleem oplossen door een lineair search, eventueel bounded...

Uiteraard, maar het is wel één van de meest simpele voorbeelden van recursie die ik kan verzinnen. Ik wilde een voorbeeld van recursie geven voor een probleem die iedereen heel eenvoudig imperatief kan oplossen. Didactisch oogpunt.

Over de bewijslast: dat hangt o.a. af van hoe je preconditie/postconditie gespecificeerd is. Als je wilt bewijzen dat je code voldoet aan bijvoorbeeld een recurrente betrekking, dan is een recursief programma makkelijker.

Bijvoorbeeld (misschien wel leuk voor de topic starter):
als je faculteit specificeerd als:

code:

fac 0 = 1
fac n = n * fac (n-1), n>0

Dan kan je met loop-invariant het volgende niet zo moeilijk te bewijzen is:

code:

function fac(n)
  int r = 1
  for(k=n; k>0; k--)
     r *= k
  return r

Maar dan is dit toch wel makkelijker zou moeten zijn:

code:

function fac(n)
   if n == 0 return 1
   else        return n * fac (n-1)

Voor zover ik me kon herinneren, is een bewijsregel voor functieaanroep alleen niet zo fijn met aliassen enzo.

Voor een wiskundige zal de recursieve aanpak denk ik aantrekkelijker zijn?

Recursie is vooral onmisbaar bij tree-problemen. Het handigste voorbeeld van recursie goed toegepast blijft toch gewoon de klassieke directory-tree van je computer.

Voor tree-traversels zijn o.a. attributen grammatica's wel interessant. Kijk voor de grap eens in hoofdstuk vier van het diktaat van het vak IPT op de uu.

[ Voor 29% gewijzigd door Infinitive op 19-12-2003 21:56 ]

[mbravenboer]

Infinitive: Voor tree-traversels zijn o.a. attributen grammatica's wel interessant.

Je kan zelfs kiezen uit materiaal van de UU .

Bij attribuut grammaticas gaat het niet direct om het definieren van traversals. Sterker nog: het doel is juist om geen traversal te definieren en zo te abstraheren over de manier waarop een bepaalde eigenschap voor een knoop berekend moet worden. Dit kan zeer specificerend werken, wat uiteraard mooie en duidelijke code oplevert.

Stratego, waar dus ook aan ontwikkelt op de UU, is een taal die zicht meer richt op het expliciet definieren van traversals. Met behulp van traversal strategien kan je nauwkeurig controleren in welke volgorde er door een boom wordt gelopen. Je kan hierbij denken aan bottomup en topdown traversals, maar ook hele specifieke traversals die gebruikt kunnen worden om complexe programma transformaties te implementeren. In Stratego kan je generieke traversals definieren, wat betekent dat je traversal werkt over alle data structuren.

Maar goed, laat ik vooral niet het Stratego boek gaan herhalen . Dit hoofdstuk gaat specifiek in op traversals, maar verwacht niet dat je het kan volgen: je valt midden in het boek.

Het vak Program Transformation (wordt gegeven in deze periode) gaat over het implementeren van programma transformaties met behulp van Stratego.

De concepten van Stratego (die concepten worden wel Strategic Rewriting genoemd) vind je ook terug in de visitor combinators voor Java van JJTraveler. Het wordt niet meer aktief onderhouden, maar de concepten blijven interessant en toepasbaar in je eigen projecten.

[Infinitive]

Maar goed, laat ik vooral niet het Stratego boek gaan herhalen .

Ik heb via via al allerlei interessante dingen over stratego gehoord. Het wordt nu wel eens tijd om er zelf naar te kijken. Bedankt voor de link.
Voor de topic-starter denk ik dat hij voorlopig dit onderwerp maar even moet negeren.

Het vak Program Transformation (wordt gegeven in deze periode) gaat over het implementeren van programma transformaties met behulp van Stratego.

Ah, maar eens even kijken of ik volgend jaar dat vak kan volgen

[ Voor 7% gewijzigd door Infinitive op 20-12-2003 09:06 ]