[Java] Recursie

[Verwijderd]

Hallo, ik ben aan het oefenen voor een tentamen Java, maar ik kom niet uit de volgende (recursie) opgave.

code:

public class Model {
   public int calculation (int[] ar, int i){
    if (i==1) return ar[i-1];
    else return ar[i-1]+ calculation(ar, i-1);
   }
}

Vraag a) Wat wordt er op het scherm afgebeeld als in een method van een client de volgende statements worden uitgevoerd:

code:

Model model= new Model();
int[] list ={2,4,6,8,10,12,14,16,18,20};
System.out.println (model.calculation(list, list.length));

Moet ik hier nu de array int[] list met alle waarden in het array int[] ar zetten? Hoe kom ik tot een link tussen de arrays? Ik heb echt geen clue hoe ik moet beginnen. Verdere subvragen gaan dieper op de method in, zoals het herschrijven naar een for of while loop. Wie kan me een hint geven om deze opgave op te lossen? Wel rekening houdend met mijn Beginner-Level in Java?

Alvast bedankt.

Edit: typo 0 --> 1 veranderd

[Alarmnummer]

Kijk eerst een goed naar deze regel:
if (i==0) return ar[i-1];

[Woy]

Schrijf anders eens stap voor stap op een papiertje uit wat het precies doet dan zal je snel genoeg doorhebben wat het resultaat van die methode is en dan zal het ook niet zo moeilijk zijn om hem te herschrijven

[Woy]

Alarmnummer schreef op 08 augustus 2002 @ 15:42:
Kijk eerst een goed naar deze regel:
if (i==0) return ar[i-1];

Ja dat zag ik ook al. Dat zal wel moeten zijn if(i==1) return ar[i-1];

[Alarmnummer]

Ik heb vandaag mijn glazenbol niet bij me, misschien kan je eerst beter uitleggen wat je bedoelt.

In ieder geval klopt het algoritme niet. En ik heb geen zin om uit te zoeken wat het zou moeten doen.

[ Voor 0% gewijzigd door Alarmnummer op 08-08-2002 15:47 . Reden: typo ]

[Verwijderd]

Ja sorry, dat was een typfoutje. Het moet inderdaad if(i==1) return ar[i-1]; zijn. Maar het inzicht is nog niet gekomen....

[Soultaker]

Een woord: debugger!
(Tweede woord: 'step'.)

[Verwijderd]

rwb schreef op 08 augustus 2002 @ 15:44:
[...]
Ja dat zag ik ook al. Dat zal wel moeten zijn if(i==1) return ar[i-1];

Dat denk ik niet...

Ik denk eerder dat het iets van if(i < 1) return 0; moet zijn. Dan bereken je de som van de elementen in die array, anders is het gewoon wazige code.

[Alarmnummer]

Ok.. ik zie al wat het algoritme gaat doen

je ziet dat er dus 2 keuzes zijn.
zoek die 2 keuzes ff uit, en plaats er commentaar bij.

ga nu per keuze kijken wat er gebeurd.

[Verwijderd]

Oke, een beetje verkeerd van start gegaan.... Maare hoe moet ik nu de connectie zien tussen de waarden in het list array en de method calculation?

[Woy]

Verwijderd schreef op 08 augustus 2002 @ 15:48:
[...]

Dat denk ik niet...

Ik denk eerder dat het iets van if(i < 1) return 0; moet zijn. Dan bereken je de som van de elementen in die array, anders is het gewoon wazige code.

dat doet hij ook als je er neerzet if( i == 1 ) return ar[ i-1 ]; alleen dan maakt hij een itteratie minder. Maar zoals jij het neerzet is het inderdaad wel een stuk netter omdat je dan ook foute invoer afvangt zonder dat je een exception krijgt.

[Alarmnummer]

Verwijderd schreef op 08 augustus 2002 @ 15:51:
Oke, een beetje verkeerd van start gegaan.... Maare hoe moet ik nu de connectie zien tussen de waarden in het list array en de method calculation?

Ojee.. volgens mij is dit niet zozeer een recursie probleem, maar een probleem van parameter passing. Wat snap je precies niet?

[Verwijderd]

Knap dat jullie zelfs gelijk de fouten eruit kunnen halen en de code zelfs kunnen verbeteren in een oogopslag. Echter ik ben nog lang niet zo ver en probeer nog te begrijpen wat de method nu eigenlijk doet...? Wat ga ik nu precies doen met de waarden in die list?

[Verwijderd]

Rekening houdend met mijn beginners status....

[Woy]

Zoals ik al eerder zei. Pak eens gewoon een papiertje en schrijf alle stappen van de recursie uit wat er gebeurt. Met zo'n kleine array is dat best te doen. Als je dat gedaan hebt snap je het waarschijnlijk al een stuk beter

[Verwijderd]

Dat is zeker een goede manier rwb, maar hier heb ik nu juist een hint bij nodig. Hoe begin ik? Wanneer ik eenmaal op weg ben en dus de method begrijp, dan kan ik 'm pas uitschrijven.

[Alarmnummer]

Zijn probleem is parameter passing.

Stel dat ik een bak met cijfers heb (en ik ben de aanroepende code) dan geef ik die bak met cijfers aan jou (jij bent de calulcation methode), dan kan jij een leuke berekening op de bak met cijfers doen. Het feit dat ik jouw die bak met cijfers heb gegeven heet ook wel parameter passing, tenslotte geef ik jou iets door, want anders zou jij niets kunnen doen.

[Verwijderd]

rwb schreef op 08 augustus 2002 @ 15:51:
dat doet hij ook als je er neerzet if( i == 1 ) return ar[ i-1 ]; alleen dan maakt hij een itteratie minder. Maar zoals jij het neerzet is het inderdaad wel een stuk netter omdat je dan ook foute invoer afvangt zonder dat je een exception krijgt.

Het is een recursieve functie, dus je moet rekening houden met het stop-probleem. Als je een stopconditie inbouwt die gegarandeerd stopt, is dat altijd beter.

<insectenliefde modus>
Het is geen "iteratie" maar een "recursieslag".
</insectenliefde modus>

[Woy]

Nou de eerste aanroep is calculation( ar, 10 ). dan kijk je wat er in de methode gebeurt. i==1 is false dus slaat hij dat statement over. dus de functie returnt ar[9] + calculation( ar, 9 ) waar ar[9] dus 20 is. Als je dit zo doorschrijft todat je bij i = 1 aan bent gekomen dan stopt de recursie

[Verwijderd]

Alarmnummer. Ah, dat begint sense te maken. Dus de bak met cijfers zijn in dit geval de waarden in het int[]list array? Deze waarden pass ik door aan de method calculation?

[Alarmnummer]

precies.

[Woy]

Verwijderd schreef op 08 augustus 2002 @ 15:59:
[...]

Het is een recursieve functie, dus je moet rekening houden met het stop-probleem. Als je een stopconditie inbouwt die gegarandeerd stopt, is dat altijd beter.

ja dat zei ik dus ook. Maar ik deed het hier zo omdat het gewoon een opdracht dus probeerde ik me daar gewoon aan te houden. Ik zei niet voor niks dat het met i<1 beter was

[Verwijderd]

rwb schreef op 08 augustus 2002 @ 16:00:
Nou de eerste aanroep is calculation( ar, 10 ). dan kijk je wat er in de methode gebeurt. i==1 is false dus slaat hij dat statement over. dus de functie returnt ar[9] + calculation( ar, 9 ) waar ar[9] dus 20 is. Als je dit zo doorschrijft todat je bij i = 1 aan bent gekomen dan stopt de recursie

Nee, i == 1 stopt niet gegarandeerd:

code:

int[] list; // Een lege array, dus list.length == 0


int x= calculation(list, list.length); // BOEM!

[Verwijderd]

Alarmnummer en Rwb, thanx voor de goede hints. Inderdaad, ik snapte niet hoe de parametrisering werkte. Ik werk nog effe door voor de andere subvragen.

[Alarmnummer]

verder moet je er veel commentaar bij zetten.. desnoods achter iedere regel een hele lading. Zodat je niet elke keer hoeft te redeneren wat je aan het doen bent..

[edit]
trouwens parametrisering is geloof ik niet het goeie woord. Dat gebruik je bij geparametriseerde polymorphisme

[ Voor 0% gewijzigd door Alarmnummer op 08-08-2002 16:12 . Reden: moet ik ook de juiste benaming gebruiken ;) ]

[Verwijderd]

Euh ja, verzon ik ff ter plekke....

[Woy]

Verwijderd schreef op 08 augustus 2002 @ 16:05:
[...]

Nee, i == 1 stopt niet gegarandeerd:

code:

int[] list; // Een lege array, dus list.length == 0


int x= calculation(list, list.length); // BOEM!

Ik zeg dus ook dat i == 1 niet gegarandeerd stopt. Maar in dit geval wel.

[Verwijderd]

rwb schreef op 08 augustus 2002 @ 16:11:
Ik zeg dus ook dat i == 1 niet gegarandeerd stopt. Maar in dit geval wel.

Posts hebben zich gekruist, ik zag je voorlaatste post niet. Het was niet mijn bedoeling het er nog eens in te wrijven ofzo.

[Alarmnummer]

Soultaker schreef op 08 augustus 2002 @ 15:47:
Een woord: debugger!
(Tweede woord: 'step'.)

Denk je nou echt dat dat hierbij handig is?

[Glimi]

Verwijderd schreef op 08 augustus 2002 @ 16:05:
Nee, i == 1 stopt niet gegarandeerd:

code:

int[] list; // Een lege array, dus list.length == 0


int x= calculation(list, list.length); // BOEM!

Nouja BOEM? Eerder een Exception lijkt me

Wat ik echter helemaal een hekel punt vind van deze functie is dus het tweede argument. Hij is imho dan ook typisch gemaakt vanuit C++ (Alarmnummer blijft delphi volhouden ) omdat men standaard het tweede argument gebruikt om de grootte van die array mee te geven aan de functie.

Echter je zou het tweede argument ook kunnen gebruiken voor het aantal recursieve slagen dat je door wilt lopen, maar hang er ajb een aantal check in en becommentarieer het dan! immers had uw school/opleiding dat gedaan, dan begreep jij het ook in 1x

Hier wat code hoe ik hem eigenlijk liever voor onderwijs doeleinden had gezien

code:

/**
 * This function caculates the sum of the first given amount
 * of integers on a given array
 * @param targetArray Arry with integers
 * @param amount the amount of integers that will be calculated
 * @returns int the sum
 */

 public int sumArray( int[ ] targetArray, int amount ) {

        //The input for amount was 0 or less
        //or the amount is larget than the array length
        //
        if( amount <= 0 || amount > targetArray.length ) {

            throw IllegalArgumentException( "Illegal value for amount: " + amount );
        }
        //The input for amount is 1.
        //This means the recursion must stop!
        //
        elseif( amount == 1) {

            return targetArray[ amount -1 ];
        }
        //The input of amount is correct (and not at the stop point)
        //Go to the next step of recursion and add the integer to it
        //
        else {

            return targetArray[ amount -1 ] + sumArray( targetArray, amount -1 );
        }

 }

[ Voor 0% gewijzigd door Glimi op 08-08-2002 16:28 . Reden: code adden ]

[Woy]

Verwijderd schreef op 08 augustus 2002 @ 16:13:
[...]

Posts hebben zich gekruist, ik zag je voorlaatste post niet. Het was niet mijn bedoeling het er nog eens in te wrijven ofzo.

Jaja dat zeggen ze allemaal. Het was gewoon expres

[Verwijderd]

Als ik het goed begrijp, dan wordt de lijst dus geprint met daarna de lengte van de lijst, waarbij de lijst (en dus ook de lengte) telkens met 1 waarde afneemt?

[Woy]

Verwijderd schreef op 08 augustus 2002 @ 16:18:
Als ik het goed begrijp, dan wordt de lijst dus geprint met daarna de lengte van de lijst, waarbij de lijst (en dus ook de lengte) telkens met 1 waarde afneemt?

Dan begrijp je het toch nog niet goed. De methode loopt alle elementen van het array af en telt die bij elkaar op

[Alarmnummer]

kijk eens heel goed naar die calculate methode:

code:

public int calculation (int[] ar, int i){ 
    if (i==1) //wat betekend dit.
        return ar[i-1]; 
    else //en wat betekend dit.
        return ar[i-1]+ calculation(ar, i-1);    
}

de rest van de dingen kan je wel ff skippen.

het is trouwen wel erg belangrijk dat je weet wat die i betekend. Dit is misschien wel het meest belangrijke. Dus wat betekend die i, en dan pas ff naar bovenstaande code kijken.

rwb

verklikker

[Verwijderd]

Echter je zou het tweede argument ook kunnen gebruiken voor het aantal recursieve slagen dat je door wilt lopen, maar hang er ajb een aantal check in en becommentarieer het dan! immers had uw school/opleiding dat gedaan, dan begreep jij het ook in 1x

Mmm, ze willen zeker niet dat ik m'n tentamen haal!

[Verwijderd]

rwb schreef op 08 augustus 2002 @ 16:19:
[...]
Dan begrijp je het toch nog niet goed. De methode loopt alle elementen van het array af en telt die bij elkaar op

Thanx! Euh.....fouten maken is goed voor het inzicht!

Wanneer het volgende waar is:

code:

if (i==1) return ar[i-1];

Dan is de lijst maar 1 lang en wordt dus alleen de waarde van die ene index gegeven.
Wanneer dit niet waar is, dan is de index dus langer en bevat meer gegevens.
Deze worden met de volgende code opgeteld:

code:

else return ar[i-1]+ calculation(ar, i-1);

Heb ik 'm nu wel goed?

[Verwijderd]

C++ stijl? C zal je bedoelen

in C++ zou ik dit zo doen:

code:

template <class T> T calculation(const std::vector<T>& list)
{
  return std::accumulate(list.begin(), list.end(), 0);
}

[Verwijderd]

i = lengte van de lijst
en
ar [i-1] = de index

[xos]

Misschien is het een goed idee om nog eens de API van een array door te lezen. Ik denk dat de recursieve methode niet het probleem is omdat die vrij simpel is in dit geval. Als je precies weet hoe de array werkt dat zal deze opdracht geen probleem meer moeten zijn.

[Woy]

Nee i is niet de lengte van de lijst. Bij de eerste aanroep wel inderdaad maar daarna verander je i om een ander getal uit je array te halen. In deze methode worden alleen elementen uit de array gelezen. De array zelf word niet korter gemaakt ofzo

[Alarmnummer]

eigelijk is het een beetje een slecht geschreven voorbeeld, probeer deze maar eens:

code:

public int calculation (int[] ar, int i){     
    if(i<0)
        ..foutmelding

    if (i==0) 
        return ar[i];     
    else 
        return ar[i]+ calculation(ar, i-1);    
}

en je moet eerst bedenken wat i is, dit is erg belangrijk. Probeer hem maar een andere naam te geven.

[Glimi]

Verwijderd schreef op 08 augustus 2002 @ 16:31:
C++ stijl? C zal je bedoelen

in C++ zou ik dit zo doen:

code:

template <class T> T calculation(const std::vector<T>& list)
{
  return std::accumulate(list.begin(), list.end(), 0);
}

Tuurlijk heb je gelijk als je voorgedefinieerde std arlogrimtes en iteratoren gaat gebruiken Je zou ook gek zijn als je dat niet deed.
Ik doelde echter erop dat C en zijn vriendje C++ bij array's geen idee hebben hoe groot ze zijn en dit vaak meegegeven wordt bij een functie. Iig de functies die je op school leert, want op een of andere manier zijn ze alergisch voor de std

[Alarmnummer]

Het is eerder met de 1 based arrays van delphi en pascal geschreven denk ik. En later is het omgetoverd naar dit voorbeeld rekening houdend met het feit dat je bij java,c(++) er altijd 1 moet aftrekken.

[Verwijderd]

rwb schreef op 08 augustus 2002 @ 16:34:
Nee i is niet de lengte van de lijst. Bij de eerste aanroep wel inderdaad maar daarna verander je i om een ander getal uit je array te halen. In deze methode worden alleen elementen uit de array gelezen. De array zelf word niet korter gemaakt ofzo

Nou de eerste aanroep is calculation( ar, 10 ). dan kijk je wat er in de methode gebeurt. i==1 is false dus slaat hij dat statement over. dus de functie returnt ar[9] + calculation( ar, 9 ) waar ar[9] dus 20 is. Als je dit zo doorschrijft todat je bij i = 1 aan bent gekomen dan stopt de recursie

Ik had dus toch nog problemen met het interpreteren van het onderdeel calculation.
De functie returnt ar[9] "20" + calculation (ar,9) Hier refereert de functie weer aan zichzelf, dus recursie (ff voor de theorie )
Vervolgens vul je bovenaan weer 9 in voor i, i==1 onwaar, dus
ar[8] "18" + calculation (ar,8), i=8, i==1 onwaar
ar[7] "16" + calculation (ar,7), i=7, i==1 onwaar
enz
Totdat alle waarden opgeteld zijn
i==1 waar, dan einde van het optellen.

Het is raar, maar bij dergelijk functies mis ik voor m'n gevoel altijd een variabele waar ik de waarden tussentijds in kan opslaan. Zal wel overgaan met de tijd hoop ik....

[Alarmnummer]

mooi zo

Als je een recursieve functie ingaat, dan krijg dus voor iedere aanroep zijn eigen variablen. Dus als je hem 10 keer zou induiken, dan krijg je ook 10 keer een i. Zo worden die waarden dus opgeslagen.

[Woy]

Mischien is het voor jou zo mischien wat makkelijker te begrijpen.

calculation ( ar, 10 ) = ar[ 9 ] + calculation ( ar, 9 )
calculation ( ar, 9 ) = ar[ 8 ] + calculation ( ar, 8 )
dus dan kan je herschrijven naar
calculation ( ar, 10 ) = ar[ 9 ] + ( ar[ 8 ] + calculation( ar, 8 ) )
(hier zitten extra haakjes bij die niet nodig zijn voor de duidelijkheid)
als je zo door gaat kom je uiteindelijk uit op
ar[ 9 ] + ar[ 8 ] + ar[ 7 ] + .... + ar[ 0 ]
wat dus gewoon een optelling van alle elementen is

[Verwijderd]

Dus eigenlijk maak je een soort "Link" van optellingen, die bij system.out weer als 1 resultaat weergegeven worden. Met daarna ook nog de lengte van de lijst. Dus het resultaat is uiteindelijk 110, 10 (optelling,lengtelijst)

[Alarmnummer]

precies.

[Woy]

Alarmnummer schreef op 08 augustus 2002 @ 17:02:
precies.

Nee niet helemaal die lengte print hij niet uit. Hij print alleen de opteling uit. Het enige wat je doet is het uitprinten van de int die de funtion calculation returnt. Deze returnt alleen de optelling van de elementen. Die lengte gebruikt hij alleen om die uit te rekenen die word voor de rest niet uitgeprint.

om het wat duidelijker te maken voor je kan je dit beter herschrijven
System.out.println (model.calculation(list, list.length));
naar
int resultaat = model.calculation(list, list.length);
System.out.println( resultaat );

Dan is het mischien wat duidelijker voor je dat je alleen het resultaat print

[Verwijderd]

Mooi, dan kan ik nu verder met het model-view-controller pattern, ook leuk... Allemaal bedankt!

[Alarmnummer]

rwb schreef op 08 augustus 2002 @ 17:04:
[...]

Nee niet helemaal die lengte print hij niet uit. Hij print alleen de opteling uit. Het enige wat je doet is het uitprinten van de int die de funtion calculation returnt. Deze returnt alleen de optelling van de elementen. Die lengte gebruikt hij alleen om die uit te rekenen die word voor de rest niet uitgeprint.

Oja.. dom dom

[Verwijderd]

Wat de methode dus doet is het optellen van alle getallen in de array. Het antwoord op vraag a is: 110.

[Alarmnummer]

Verwijderd schreef op 08 augustus 2002 @ 17:05:
Mooi, dan kan ik nu verder met het model-view-controller pattern, ook leuk... Allemaal bedankt!

Maak je borst maar nat dan

mvc is 'redelijk' gecompliceerd

[Woy]

Dat valt toch wel mee. Gewoon een Observer en een Observable om het een beetje makkelijk te zeggen

[MisterData]

Alarmnummer schreef op 08 augustus 2002 @ 16:09:
verder moet je er veel commentaar bij zetten.. desnoods achter iedere regel een hele lading. Zodat je niet elke keer hoeft te redeneren wat je aan het doen bent..

[edit]
trouwens parametrisering is geloof ik niet het goeie woord. Dat gebruik je bij geparametriseerde polymorphisme

Generics dus?

[Alarmnummer]

rwb schreef op 08 augustus 2002 @ 17:29:
Dat valt toch wel mee. Gewoon een Observer en een Observable om het een beetje makkelijk te zeggen

Je moet je ff indenken in de topic starter. Ik beheers intussen mvc wel een klein beetje

[Alarmnummer]

MisterData schreef op 08 augustus 2002 @ 17:32:
[...]

Generics dus?

Zo heet het in Java, maar de dat is niet de officiele naam

[Woy]

Alarmnummer schreef op 08 augustus 2002 @ 17:33:
[...]
Je moet je ff indenken in de topic starter. Ik beheers intussen mvc wel een klein beetje

Ik legde het toch ook heel simpel uit