Rekursiv programering?
Dubb
*ungefär* vad det handlar om. Dvs jag vet att det är optimerad kod det
handlar om (eller?). Men jag är inte riktigt insatt i principen av hur
man ska tänka. Jag är väl sådär halvbra på programering, och har goda
kunskaper i matematik och logiskt tänkande. Hur ska jag göra för att
lära mig skriva rekursiv kod? Dvs hur man ska tänka... Nått exempel
vore guld värt! Gärna i java, eftersom det är det jag använder mest
nu.
Ett litet testprogram jag gjort (för att öva mig att programera) var
att ta en textsträng (från prompten) och visa alla tänkbara
kombinationer (omkastningar) av bokstäverna. T.ex. "abc" ger "abc",
"acb", "bac", "bca", "cab" och "cba". Och man kan skriva in hur lång
sträng som helst (i princip, input kan ju inte vara hur långt som
helst...). Men skriver man in 9 tecken så tar det ca 20 minuter (på
min AMD 600Mhz) att generera alla kombinationerna (362880 st).
För att visa hur jag gjort så hade jag tänkt att posta min kod här.
Men den är så rörig och har en del ofärrdig kod (t.ex. möjligheten att
skriva ut alla kombinationerna till en fil...) så jag skippar det. Men
om nån vill se så kan jag ju förstås posta den...
Men vad jag undrar är hur man ska tänka om man ska lösa detta
programerings-problem med rekursiv programering. Jag har löst själva
uppgiften, men jag vet inte om jag använt mig av just rekursiv
programering. Särskillt optimerad tror jag inte koden är...
Dubb
Anders Dahlgren
>
> Någon som kan förklara rekursiv programering för mig?
Nåt exempel i Java kan jag tyvärr inte prestera. Med rekursivt tänker
jag på rekursiva anrop av funktioner (finns det mer?). Det innebär att
en funktion anropar sig själv. Fördelen med detta är att det går att
skapa en del "snygga" lösningar. Oftast (alltid?) går det att göra samma
sak i en iteration, vilket som är effektivast vet jag inte.
Vill man tex ha reda på största talet i a[5] = 4 1 5 2 3 rekursivt blir
det kanske så här i C++ (ifall jag inte gjort fel ;):
int max (int a[], int antal){
if (antal == 1)
return a[0];
int tmp = max(a, antal - 1);
if (a[antal] > tmp)
return a[antal];
return tmp;
}
Funktionen jämför 3 med högsta värdet av tidigare värden (genom att
anropa sig själv). Det skapas då en ny instans av max som jämför 2 med
högsta värdet av tidigare värden. Osv tills det bara är 4:an kvar, då
returneras den till instansen som jämförde 1:an med tidigare. Av
jämförelsen 1 och 4 returneras fyra till instansen som jämför 5 med
tidigare. Osv.
Hoppas det hjälper
--
/Anders
You have the right to remain silent. Anything you say will be
misquoted, then used against you.
Dubb
wrote:
Njae... Jag blev inte speciellt klokare på det... Jag kan inte förstå
hur den kan anropa sig själv. Den borde ju bara bli en evighetsloop,
eftersom när den kommer ner till "int tmp = max(a, antal-1);" så
hoppar den ju upp igen. Och dom sista raderna körs ju aldrig. Jag vet
att det inte är så, men jag ser inte logiken alls.
--
Dubb
Torkel Franzen
>Någon som kan förklara rekursiv programering för mig?
Att programmera och tänka rekursivt innebär att man beskriver hur
en uppgift ska utföras genom att reducera uppgiften till ett enklare
fall av samma uppgift.
Ditt permutationsexempel passar bra som illustration. Hur får man en
permutation av a1,..,an? Varje permutation kan fås genom att man först
bestämmer vilket av a1,..,an som ska komma först i den permuterade
följden. Därefter kommer en permutation av de återstående elementen.
Om det inte finns några återstående element, dvs om n=1, så finns
det bara en permutation.
Här har vi alltså reducerat uppgiften att plocka fram en permutation
av n element till uppgiften att plocka fram en permutation av n-1
element, om n>1. Om n=1 har vi det s.k. basfallet, som lätt hanteras.
När vi väl hittat en sådan reduktion (kommit fram, som man säger,
till ett rekursivt samband) är det en enkel sak att skriva ett program
som utför uppgiften. Detta är typiskt för rekursiv programmering.
Allt som kan programmeras rekursivt kan också programmeras
iterativt. Somliga programmeringsspråk har emellertid ingen iteration,
utan alla loopar måste skrivas rekursivt.
I ett språk som Java kan man välja mellan iterativ och rekursiv
programmering när man ska skriva en metod. Rekursiv programmering är
i många fall det som ligger närmast till hands, och är ofta enklare
att skriva och begripa än iterativ programmering. Detta gäller i all
synnerhet då man arbetar med rekursivt definierade datastrukturer,
som t.ex. träd eller listor av olika slag. Att en datastruktur, t.ex.
Fnork, är rekursivt definierad innebär att en fnork består av
ett antal komponenter varav minst en också är en fnork. Exempel:
en lista (i klassisk funktionell mening) är en struktur som har
ett huvud, som är ett värde av något slag, och en svans, som också
är en lista.
Det är inte så att rekursiva definitioner i allmänhet ger optimerad
kod (dvs leder till program som exekveras snabbt och använder lite
minne). I stället är det lätt att med rekursion skriva procedurer som
är ineffektiva. Observera: det är ingalunda någon nödvändighet att rekursiva
implementeringar är ineffektiva, men i och med att rekursiv
programmering har högre abstraktionsnivå än iterativ programmering
blir det lättare att inte uppmärksamma ineffektiviteten hos den
algoritm som man faktiskt implementerar.
Här följer ett exempel på hur den rekursiva algoritmen ovan kan
implementeras i Java. Algoritmen är här inkorporerad i en klass
Stringpermuterare. En instans av klassen är en s.k. iterator, som
förstår sig på att leverera (med metoden next) permutationer av
en given sträng på begäran, en efter en.
import java.util.*;
public class Stringpermuterare implements Iterator{
// En strängpermuterare anlitar en underleverantör, som också
// är en strängpermuterare, för att permutera resten av strängen.
public Stringpermuterare(String s){
sträng=s;
längd=sträng.length();
pos=0;
if(längd>0){
första=sträng.charAt(0);
restpermuterare=new Stringpermuterare(sträng.substring(1));
}
}
private String sträng;
private char första;
private int pos;
private Stringpermuterare restpermuterare;
private int längd;
// Innebörden av hasNext är att det finns fler permutationer att
// leverera om vi ännu inte valt det sista tecknet, eller om
// det finns fler permutationer av resten. Fallet då strängen
// är tom eller bara har ett tecken specialbehandlas.
public boolean hasNext(){
if(längd==0)
return false;
if(längd==1)
return pos!=1;
return (pos!=längd-1||restpermuterare.hasNext());
}
// Nästa permutation fås genom att sätta tecknet först först, och
// därefter en permutation av resten. När det inte längre finns
// fler permutationer av resten väljer vi ett nytt första tecken.
public Object next(){
if(!hasNext())
throw new NoSuchElementException();
if(längd==1){
pos++;
return sträng;
}
if(!restpermuterare.hasNext()){
pos++;
första=sträng.charAt(pos);
restpermuterare=new Stringpermuterare(resten(sträng,pos));
}
return första+(String)restpermuterare.next();
}
// Returnerar den sträng man får genom att plocka bort tecknet i
// position pos.
private String resten(String s,int pos){
if(pos==0)
return s.substring(1);
else
return s.substring(0,pos)+s.substring(pos+1);
}
// remove finns bara med för att tillfredsställa kompilatorn
public void remove(){
throw new UnsupportedOperationException();
}
// Metod för att testa klassen
public static void main(String argv[]){
Stringpermuterare perm=new Stringpermuterare(argv[0]);
while(perm.hasNext())
System.out.println(perm.next());
}
}
Alexander Backlund
>
> Dubb wrote:
> >
> > Någon som kan förklara rekursiv programering för mig?
>
> jag på rekursiva anrop av funktioner (finns det mer?). Det innebär att
> en funktion anropar sig själv. Fördelen med detta är att det går att
> skapa en del "snygga" lösningar. Oftast (alltid?) går det att göra samma
> sak i en iteration,
Det går alltid att göra samma sak utan rekursion.
> vilket som är effektivast vet jag inte.
Vanligen den iterativa varianten.
Anders K
>Någon som kan förklara rekursiv programering för mig? Jag vet
det klassiska exemplet på en rekursiv funktion är fakultet,
n!=n*(n-1)..*1
om man tittar på uppgiften att multiplicera med föregående
nummer kan se att man kanske kan förenkla det hela till en
multiplikation n*(n-1)
alltså:
public final int fak(int n) {
if (n == 1) return 1; // slut - ändpunkt av rekurs
else return fak(n-1)*n; // ropa grannen
}
int hundratjugo = fak(5);
den ropar sig själv tills den når 1, först då börjar de egentliga
multiplikationerna på återvägen
5
4
3
2
1 <- nu börjar multiplikationerna, funktionerna returnerar
2
6
24
120
tja, ingen vidare vetenskaplig förklaring =)
själv har jag nästan aldrig använt rekursivitet sedan jag lärde det i
skolan eftersom det är oftast(läs:alltid) långsammare än motsvarande
iterativ metod.
</anders>
Daniel Herlitz
> > if (antal == 1)
> > return a[0];
> > int tmp = max(a, antal - 1);
> > if (a[antal] > tmp)
> > return a[antal];
> > return tmp;
> >}
> >
>
> hur den kan anropa sig själv. Den borde ju bara bli en evighetsloop,
> eftersom när den kommer ner till "int tmp = max(a, antal-1);" så
> hoppar den ju upp igen. Och dom sista raderna körs ju aldrig. Jag vet
> att det inte är så, men jag ser inte logiken alls.
>
När den kommer till "int tmp = max(a, antal-1);" så _hoppar_ den inte alls.
Den _anropar_ sig själv. Skillnaden mellan ett hopp och ett funktionsanrop
är bl.a. att man i det senare fallet kommer ihåg varifrån man hoppade (kan
t.ex. lagras på stacken) och vid "return" återvänder till stället man
hoppade från. Starta med ett litet värde på antal, t.ex. 3 och gå igenom
koden rad för rad så kommer du att inse hur det fungerar.
/DH
Torkel Franzen
> n!=n*(n-1)..*1
>
> om man tittar på uppgiften att multiplicera med föregående
> nummer kan se att man kanske kan förenkla det hela till en
> multiplikation n*(n-1)
Du menar väl n*(n-1)!
> själv har jag nästan aldrig använt rekursivitet sedan jag lärde det i
> skolan eftersom det är oftast(läs:alltid) långsammare än motsvarande
> iterativ metod.
Med många rekursiva anrop blir det förvisso en del merarbete
(förutom att stackutrymmet kan ta slut), men det behöver inte vara
märkbart. Den stora vinsten med rekursiva definitioner är att de
är enklare att programmera och att begripa.
aXEmAN
så innebär det att när antal har fått värdet 1, så skickas det värdet
tillbaka till föregående anrop. Sedan görs jämförelsen med
returnvärdet från föregående funktion och skickar tillbaka det största
värdet. Därför blir det ingen evig loop.
Lite grafiskt borde det väl se ut nånting sånt här :)
Main()
|
\/
Max(a, 5)
//Minska antal med ett
Max(a, 4)
//Minska antal med ett
Max(a, 3)
//Miska antal med ett
Max(a, 2)
//Minska antal med ett
Max(a, 1)
//börja retrurnera värdena
Max(a, 2) <--'
//Jämför a[1] med a[2]
Max(a, 3) <--'
//Jämför a[2] med a[3] och det största värdet
Max(a, 4) <--'
//Jämför a[3] med a[4] och det största värdet
Max(a, 5) <--'
//Jämför a[1] med a[0] och med det största värdet
|
\/
Main()
Vad som händer är alltså att returvärdet hela tiden skickas till
"tmp" i föregående nivå och utför resten av koden i funktionen.
Sedan fortsätter så tills man har nått main() (eller vad det nu heter
i Java :) )
Hoppas att du förstår någonting av vad jag har skrivit.
On Fri, 10 Mar 2000 08:03:13 GMT, Dubb <du...@pzz.duh..pi> wrote:
>>Vill man tex ha reda på största talet i a[5] = 4 1 5 2 3 rekursivt blir
>>det kanske så här i C++ (ifall jag inte gjort fel ;):
>>
>>int max (int a[], int antal){
>> if (antal == 1)
>> return a[0];
>> int tmp = max(a, antal - 1);
>> if (a[antal] > tmp)
>> return a[antal];
>> return tmp;
>>}
>>
>
>Njae... Jag blev inte speciellt klokare på det... Jag kan inte förstå
>hur den kan anropa sig själv. Den borde ju bara bli en evighetsloop,
>eftersom när den kommer ner till "int tmp = max(a, antal-1);" så
>hoppar den ju upp igen. Och dom sista raderna körs ju aldrig. Jag vet
>att det inte är så, men jag ser inte logiken alls.
>
>--
>
>Dubb
Anders K
wrote:
>Anders K <a...@workmail.com> writes:
>
> > n!=n*(n-1)..*1
> >
> > om man tittar på uppgiften att multiplicera med föregående
> > nummer kan se att man kanske kan förenkla det hela till en
> > multiplikation n*(n-1)
>
> Du menar väl n*(n-1)!
>
nä egentligen inte, ville förklara så lätt som möjligt (så att jag
själv förstår det) fast rent matematiskt har du förstås rätt =)
> > själv har jag nästan aldrig använt rekursivitet sedan jag lärde det i
> > skolan eftersom det är oftast(läs:alltid) långsammare än motsvarande
> > iterativ metod.
>
> Med många rekursiva anrop blir det förvisso en del merarbete
>(förutom att stackutrymmet kan ta slut), men det behöver inte vara
>märkbart.
"inte märkbart" ? det lät lite flummigt.. skulle du kunna precisera
dig lite?
>Den stora vinsten med rekursiva definitioner är att de
>är enklare att programmera och att begripa.
>
endast inom den akademiska världen och det är uppenbarligen inte så
självförklarande eftersom han frågar..
ne c'est pas?
/anders
Torkel Franzen
> nä egentligen inte, ville förklara så lätt som möjligt (så att jag
> själv förstår det) fast rent matematiskt har du förstås rätt =)
Inte bara "rent matematiskt", utan hela tanken med rekursiva
definitioner är att reducera uppgiften till samma uppgift i enklare
fall.
> "inte märkbart" ? det lät lite flummigt.. skulle du kunna precisera
> dig lite?
Jag menar bokstavligen "inte märkbart", dvs att användaren inte
märker någon skillnad.
> endast inom den akademiska världen och det är uppenbarligen inte så
> självförklarande eftersom han frågar..
"Den akademiska världen" har ingenting med saken att göara, utan
mitt påstående var att rekursiv programmering (givetvis: när man
förstått begreppet rekursion) är enklare och lättbegripligare i många
fall. Om du betvivlar detta kan du ju till att börja med ge en
iterativ definition av klassen Stringiterator.
Dubb
<d94...@d.kth.se> wrote:
>> >int max (int a[], int antal){
>> > if (antal == 1)
>> > return a[0];
>> > int tmp = max(a, antal - 1);
>> > if (a[antal] > tmp)
>> > return a[antal];
>> > return tmp;
>> >}
>> >
>>
>> Njae... Jag blev inte speciellt klokare på det... Jag kan inte förstå
>> hur den kan anropa sig själv. Den borde ju bara bli en evighetsloop,
>> eftersom när den kommer ner till "int tmp = max(a, antal-1);" så
>> hoppar den ju upp igen. Och dom sista raderna körs ju aldrig. Jag vet
>> att det inte är så, men jag ser inte logiken alls.
>>
>
>När den kommer till "int tmp = max(a, antal-1);" så _hoppar_ den inte alls.
>Den _anropar_ sig själv. Skillnaden mellan ett hopp och ett funktionsanrop
>är bl.a. att man i det senare fallet kommer ihåg varifrån man hoppade (kan
>t.ex. lagras på stacken) och vid "return" återvänder till stället man
>hoppade från. Starta med ett litet värde på antal, t.ex. 3 och gå igenom
>koden rad för rad så kommer du att inse hur det fungerar.
Tyvär så förstår jag inte även om jag börjar med antal=3 och går
igenom rad för rad. Jag kan inte förstå hur den kan komma ihåg gammla
värden... Om jag ska använda mig av gamla värden måste jag altid
definiera en temp variabel t.ex....
--
Dubb
Dubb
<alex...@ida.his.se> wrote:
>Anders Dahlgren wrote:
>>
>> Dubb wrote:
>> >
>> > Någon som kan förklara rekursiv programering för mig?
>>
>> Nåt exempel i Java kan jag tyvärr inte prestera. Med rekursivt tänker
>> jag på rekursiva anrop av funktioner (finns det mer?). Det innebär att
>> en funktion anropar sig själv. Fördelen med detta är att det går att
>> skapa en del "snygga" lösningar. Oftast (alltid?) går det att göra samma
>> sak i en iteration,
>
>Det går alltid att göra samma sak utan rekursion.
>
>> vilket som är effektivast vet jag inte.
>
>Vanligen den iterativa varianten.
Jag förstår inte skillnaden...
--
Dubb
Dubb
wrote:
>Dubb <du...@pzz.duh..pi> writes:
>
> >Någon som kan förklara rekursiv programering för mig?
>
Jag kan inte alls sätta mig in i din kod. Det är MASSOR som jag inte
förstår alls... Jag förstår inte hur en funktion kan anropa sig själv.
Och hur den kan komma ihåg värden.
--
Dubb
Dubb
>On Thu, 09 Mar 2000 23:12:08 GMT, Dubb <du...@pzz.duh..pi> wrote:
>
>>Någon som kan förklara rekursiv programering för mig? Jag vet
>
>det klassiska exemplet på en rekursiv funktion är fakultet,
>
>n!=n*(n-1)..*1
>
>om man tittar på uppgiften att multiplicera med föregående
>nummer kan se att man kanske kan förenkla det hela till en
>multiplikation n*(n-1)
>
>alltså:
>
>public final int fak(int n) {
> if (n == 1) return 1; // slut - ändpunkt av rekurs
> else return fak(n-1)*n; // ropa grannen
>}
>
>int hundratjugo = fak(5);
>
>den ropar sig själv tills den når 1, först då börjar de egentliga
>multiplikationerna på återvägen
>
>5
>4
>3
>2
>1 <- nu börjar multiplikationerna, funktionerna returnerar
>2
>6
>24
>120
>
>tja, ingen vidare vetenskaplig förklaring =)
>
>själv har jag nästan aldrig använt rekursivitet sedan jag lärde det i
>skolan eftersom det är oftast(läs:alltid) långsammare än motsvarande
>iterativ metod.
Även den här förklaringen var för krånglig för mig...
--
Dubb
Dubb
wrote:
Tyvär så gör jag inte det...
--
Dubb
Carl Nettelblad
news:epcicskplkjam235n...@4ax.com...
Se metoden/funktionen/proceduren som ett objekt. Den har variabler. Varje
instans (anrop, alltså) av objektet/metoden har sin EGEN kopia av
variablerna. Om du skapar ett nytt objekt av någon klass och sätter något
värde till något påverkar inte det befintliga objekt, eller hur? (Saken blir
naturligtvis en annan om vi har statiska variabler i funktionen, fast det
har man ju som standard inte)
Om du har möjlighet att köra det hela i en debugger men möjlighet att stega
rad för rad kan du ju kolla vad som händer, om du inte själv kan tänka dig
det.
/Carl
Dubb
Jag måste väl vara dum eller nått... :(
För jag fattar fortfarande inte. Och det där du sa med "Om du skapar
ett nytt objekt av någon klass och sätter något värde till något
påverkar inte det befintliga objekt, eller hur?" förstod jag inte
heller... Du säger att varje instans har sin egen kopia av
variablerna. Men hur håller den koll på alla värden? Någon nämde
stack, vad är det?
--
Dubb
Anders Dahlgren
>
> Njae... Jag blev inte speciellt klokare på det... Jag kan inte förstå
> hur den kan anropa sig själv. Den borde ju bara bli en evighetsloop,
> eftersom när den kommer ner till "int tmp = max(a, antal-1);" så
> hoppar den ju upp igen. Och dom sista raderna körs ju aldrig. Jag vet
> att det inte är så, men jag ser inte logiken alls.
Såg att du fått en del svar, men jag försöker mig på en förklaring.
Detta var funktionen jag skrev (korrigerad för fel)
1. int max (int a[], int antal){
2. if (antal == 1)
3. return a[0];
4. int tmp = max(a, antal - 1);
5. if (a[antal - 1] > tmp) //Var inget -1 i ursprungliga
6. return a[antal - 1]; //dito
7. return tmp;
8. }
Om vi i huvudprogrammet har en variabel b[3] som innehåller värdena 1, 3
och 2. Jag vill ha reda på högsta värdet av dessa tre med hjälp av
funktionen max, anropet blir:
int high = max(b, 3); //high är variablen där jag sparar högsta värdet
Antal är inte lika med ett. Rad 4 körs nästa gång. Där anropas
funktionen max. I minnet skapas då en ny instans (funktion, objekt) av
max som har egna variabler. De heter likadant som i första max, men de
är inte samma. I denna nya instans är antal lika med två och det skapas
ytterligare en instans av max, även den med egna variabler. I denna
sista instans är antal lika med ett. Då returneras a[0], det vill säga
en etta. Nu avslutas den sista instansen av max (pga return-satsen på
rad 3). Ettan returneras till den andra instansen av max, och sparas i
tmp. Den är nu nere på rad 5 där jämförelsen sker. Den jämför i fall
andra värdet (antal - 1) (3) är större än tmp (som ju var 1). Detta är
sant och tre:an returneras till den första instansen (den som anropades
av main) där tre:an sparas i tmp. Nu har den kommit till rad 5 där
jämförelsen sker. 2 är mindre än 3 och rad 7 körs istället. Den
returnerar tre:an till main.
Problemet är att inse att det skapas nya instanser av funktionen. Varje
instans har sina egna variabler. I detta fall har de array:n gemensam,
men dess längd är olika.
Fördelen med rekursion är att jag inte behöver lösa hela problemet, att
få reda på högsta värdet i fältet. Istället löser jag ett mindre
problem, att få reda på högsta talet av två tal. Detta lilla problem
löser jag sedan så många gånger som det är nödvändigt.
Hoppas det hjälper. Tyvärr kan jag inte Java ännu, så jag kan inte ge
dig ett exempel i Java.
Stefan Larsson
>
>Jag kan inte alls sätta mig in i din kod. Det är MASSOR som jag inte
>förstår alls... Jag förstår inte hur en funktion kan anropa sig själv.
>Och hur den kan komma ihåg värden.
Ett lite enklare exempel är:
void func( int x ) {
/* använd x */
annan_func( x - 1 );
/* här finns x fortfarande */
}
Jag hoppas att det är klart att x inte "glöms bort" över anropet till
annan_func. Inte heller minskar x på grund av att man skickar x-1
till annan_func.
låt oss nu anropa _samma_ funktion (rekursion)
void func( int x ) {
/* här finns x */
func( x - 1 );
/* här finns x fortfarande */
}
Det finns ingen skillnad mot det första exemplet. x ändras inte av
att skickas till en funktion även om funktionen i det här fallet
är densamma. Funktionen som anropas, även om det är samma, får
en parameter som den kallar x men det har ingenting med vad parametern
som skickas _in_ heter.
Den andra svårigheten är att inse att man kan anropa sig själv utan
att programmet loopar för evigt. Det måste därför finnas en väg genom
funktionen som _inte_ anropar funktionen ytterligare en gång.
void func( int x ) {
if( x == 1 ) {
return;
}
func( x - 1 );
}
Om func anropas med argumentet 1 kommer den _inte_ att anropa sig själv.
Om func däremot anropas med ett värde större än 1 (säg 3) kommer följande
att hända:
func( x = 3 )
x är inte 0 -> anropa func( 2 ) OBS! x ändras inte.
func( x = 2 )
x är inte 0 -> anropa func( 1 )
func( x = 1 )
x är 1 -> returnera utan att anropa func
tillbaka i func( x = 2 ) -> funktionen slut -> returnera
tillbaka i func( x = 3 ) -> funktionen slut -> returnera
Är det fortfarande oklart hur rekursion funkar? Annars är det dags
att börja gå in på vad man ska använda det till :)
/stefan
--
- stefan larsson -- http://www.dtek.chalmers.se/~d95stela -- ...och hör sen! -
Here come the Martian Martians, and they're riding on their Martian bikes
and we have to find out right now, what kind of ice cream do the Martians like?
Carl Nettelblad
dem) på stacken. Som en hög (stack) med tallrikar eller byggklossar eller
vad som helst. Sedan finns det alltid en global pekare (i allmänhet som ett
register, fast det är oviktigt) som pekar på den senaste stackpositionen.
När något läggs till stacken ökas den pekaren, när något tas bort från den
minskas den. Ett funktionsarop skulle alltså i pseudokod se ut ungefär som
följande
{
/* riktig kod: a(1,2)*/
Lägg 1 på stacken
Lägg 2 på stacken
Anropa a
{
Hämta värdena 1 och 2
Ordna minnesutrymme lokala variabler, antingen på stacken eller på
annat sätt
(egentligen kan de inte vara två separata, blir i allmänhet
"ihopbakade")
Gör lite kul med värdena
Ta bort allt vi la in på stacken, utom eventuellt returvärde som vi
till slut lägger dit
Returnera
}
}
Jag vet nu inte om det gjorde dig så mycket klokare. Men hur tänker du dig
att det fungerar vid det FÖRSTA anropet av funktionen, var lagrar den då
sina egna variabler? Den gör på samma sätt varje gång, fast får naturligtvis
nya adresser, eftersom det är ett nytt anrop, och de gamla adresserna är
upptagna. Det spelar ingen roll om funktionen a anropar sig själv eller
funktionen b, det går ändå till på samma sätt och den kommer ändå ihåg
värdena på allt. Lite grann samma sak som att om du har en variabel x i en
metod i en klass som också har variabeln x så ändras inte objektets värde på
x bara för att metoden ändrar värdet på "sitt" x.
Om inte detta heller hjälper borde du kanske läsa lite om "scopes", eller
något.
/Carl
Dubb
wrote:
>Dubb wrote:
Jo, jag har förstått nu att det skapas en ny instans. Vad jag däremot
inte förstår är HUR det hela fungerar... det känns som man inte har
full koll på något sett... Och jag förstår inte heller hur man ska
tänka när man ska angripa ett problem på detta sett. Att lösa t.ex.
mitt problem med att få alla kombinationer av en viss sträng löste jag
efter lite grubbel med nästlade for-satser. Jag kan inte alls tänka
hur jag skulle kunna lösa det med rekursion.
--
Dubb
Dubb
Larsson) wrote:
>Fri, 10 Mar 2000 17:44:24 GMT, du...@pzz.duh..pi (Dubb) ->
>>
>>Jag kan inte alls sätta mig in i din kod. Det är MASSOR som jag inte
>>förstår alls... Jag förstår inte hur en funktion kan anropa sig själv.
>>Och hur den kan komma ihåg värden.
>
Det börjar klarna LITE nu... Men fortfarande MYCKET oklart för mig.
Jag ser det fortfarande som en logisk omöjlighet att få sådana
funktioner att fungera.
--
Dubb
aXEmAN
Se det som att funktionsdefinitionen är ett höghus och att varje
rekursivt anrop får funktionen att gå upp en trappa. När funktionen
har kommit högst upp så kastar den ned ett värde till våningen under,
som i sin tur kastar ner värdet en våning osv, tills värdet har nått
bottenvåningen.
Att det sedan känns ganska meningslöst att nyttja rekusiva funktioner
är en helt annan femma. Det är väl väldigt sällan det är nödvändigt
att använda sig av en sådan, vad jag har förstått, men det kan väl
vara bra att kunna OM det nån gång skulle dyka upp ett sådant problem.
:-)
Jan Erik Moström
Här ha du två enkla Java exempel att titta på
http://www.cs.umu.se/kurser/TDBA42/VT00/mom1/jem/e/ex28.html
http://www.cs.umu.se/kurser/TDBA42/VT00/mom1/jem/e/ex29.html
jem
Torkel Franzen
> Att det sedan känns ganska meningslöst att nyttja rekusiva funktioner
> är en helt annan femma. Det är väl väldigt sällan det är nödvändigt
> att använda sig av en sådan, vad jag har förstått, men det kan väl
> vara bra att kunna OM det nån gång skulle dyka upp ett sådant problem.
Det är aldrig (teoretiskt) nödvändigt, precis som det aldrig är
nödvändigt att använda sig av något annat än maskinspråk vid
programmering.
Torkel Franzen
> Här ha du två enkla Java exempel att titta på
>
> http://www.cs.umu.se/kurser/TDBA42/VT00/mom1/jem/e/ex28.html
>
> http://www.cs.umu.se/kurser/TDBA42/VT00/mom1/jem/e/ex29.html
Dina exempel är förträffliga, men jag har ett litet klagomål på en
kommentar i det andra programmet: "OBS detta är INGET BRA sätt att
göra det i Java !!". Den speciella rekursiva algoritm du använder
("naive reverse") är förvisso ineffektiv, men detta har inget
speciellt med Java att göra. Även i Java kan man ju i stället använda
en effektivare rekursiv metod.
Dubb
wrote:
>>Någon som kan förklara rekursiv programering för mig?
>
>Här ha du två enkla Java exempel att titta på
>
>http://www.cs.umu.se/kurser/TDBA42/VT00/mom1/jem/e/ex28.html
>
>http://www.cs.umu.se/kurser/TDBA42/VT00/mom1/jem/e/ex29.html
>
Jag fattar absolut ingenting av det där... :(
--
Dubb
Dubb
wrote:
>On Fri, 10 Mar 2000 22:25:44 GMT, Dubb <du...@pzz.duh..pi> wrote:
>
>Se det som att funktionsdefinitionen är ett höghus och att varje
>rekursivt anrop får funktionen att gå upp en trappa. När funktionen
>har kommit högst upp så kastar den ned ett värde till våningen under,
>som i sin tur kastar ner värdet en våning osv, tills värdet har nått
>bottenvåningen.
Jo jag har förstått ungefär vad rekursion innebär. Men jag fattar
fortfarande inte alls hur det fungerar... :(
--
Dubb
Dubb
<cne...@hem.passagen.se> wrote:
>Stacken: När en funktion anropas läggs alla parametrar (eller pekare till
>dem) på stacken. Som en hög (stack) med tallrikar eller byggklossar eller
>vad som helst. Sedan finns det alltid en global pekare (i allmänhet som ett
>register, fast det är oviktigt) som pekar på den senaste stackpositionen.
>När något läggs till stacken ökas den pekaren, när något tas bort från den
>minskas den. Ett funktionsarop skulle alltså i pseudokod se ut ungefär som
>följande
Fast jag förstår inte VAR i koden värdena läggs in i och tas ifrån
stacken.
>Jag vet nu inte om det gjorde dig så mycket klokare. Men hur tänker du dig
>att det fungerar vid det FÖRSTA anropet av funktionen, var lagrar den då
>sina egna variabler? Den gör på samma sätt varje gång, fast får naturligtvis
>nya adresser, eftersom det är ett nytt anrop, och de gamla adresserna är
>upptagna. Det spelar ingen roll om funktionen a anropar sig själv eller
>funktionen b, det går ändå till på samma sätt och den kommer ändå ihåg
>värdena på allt. Lite grann samma sak som att om du har en variabel x i en
>metod i en klass som också har variabeln x så ändras inte objektets värde på
>x bara för att metoden ändrar värdet på "sitt" x.
Det jag inte fattar är hur funktionen håller koll på alla gamla
värden, och hur man kan använda sig utav dom. Dvs hur funktionen kan
veta att den ska ta det gamla värdet och göra något med det samtidigt
som den gör något med det aktuella värdet...
>Om inte detta heller hjälper borde du kanske läsa lite om "scopes", eller
>något.
Scopes? Vad är det för något?
--
Dubb
Magnus Bäck
Dubb <du...@pzz.duh..pi> wrote:
> On Fri, 10 Mar 2000 21:48:02 GMT, "Carl Nettelblad"
> <cne...@hem.passagen.se> wrote:
>
> >Stacken: När en funktion anropas läggs alla parametrar (eller pekare till
> >dem) på stacken. Som en hög (stack) med tallrikar eller byggklossar eller
> >vad som helst. Sedan finns det alltid en global pekare (i allmänhet som ett
> >register, fast det är oviktigt) som pekar på den senaste stackpositionen.
> >När något läggs till stacken ökas den pekaren, när något tas bort från den
> >minskas den. Ett funktionsarop skulle alltså i pseudokod se ut ungefär som
> >följande
>
> Fast jag förstår inte VAR i koden värdena läggs in i och tas ifrån
> stacken.
Nej, men sånt fixar ju kompilatorn åt dig. Exakt hur det går till när
funktioner anropas rekursivt behöver du inte bry dig om just nu, utan
koncentrera dig på principen.
Acceptera att funktioner kan anropas rekursivt och att det skapas
minnesutrymme för nya instanser av de lokala variablerna för varje
anrop till funktionen.
> Det jag inte fattar är hur funktionen håller koll på alla gamla
> värden, och hur man kan använda sig utav dom. Dvs hur funktionen kan
> veta att den ska ta det gamla värdet och göra något med det samtidigt
> som den gör något med det aktuella värdet...
Eftersom de gamla värdena ligger undansparade hela tiden (även när
funktioner anropas) och när kontrollen återgår till det ursprungliga
anropet så ligger de kvar på samma plats. En funktions lokala vari-
abler finns inte på en fix plats i minnet utan placeras där de råkar
få plats.
Tänk dig anropen som en hög där alla förändringar sker högst upp. Ett
nytt anrop gör högen lite högre, och när det anropet körts färdigt
minskar höjden till vad det var tidigare.
> >Om inte detta heller hjälper borde du kanske läsa lite om "scopes", eller
> >något.
>
> Scopes? Vad är det för något?
Scopes talar om var variabler och andra identifierare är kända och
åtkomliga. Till exempel har lokala variabler ett scope (lämplig svensk
översättning?) som bara sträcker sig över den aktuella metoden.
public void foo() {
int i = 10; // (*)
}
public void bar() {
System.out.println(i); // Fel om det är (*) som åsyftas
}
--
Magnus Bäck
ba...@swipnet.se
Carl Nettelblad
> > Scopes? Vad är det för något?
>
> Scopes talar om var variabler och andra identifierare är kända och
> åtkomliga. Till exempel har lokala variabler ett scope (lämplig svensk
> översättning?) som bara sträcker sig över den aktuella metoden.
>
känner inte till något vedertaget svenskt ord, och den mesta dokumentation
är ju ändå på engelska (så han hade större nytta av att få höra det engelska
ordet än någon okänd hemmaöversättning)
/Carl
Carl Nettelblad
> >dem) på stacken. Som en hög (stack) med tallrikar eller byggklossar eller
> >vad som helst. Sedan finns det alltid en global pekare (i allmänhet som
ett
> >register, fast det är oviktigt) som pekar på den senaste stackpositionen.
> >När något läggs till stacken ökas den pekaren, när något tas bort från
den
> >minskas den. Ett funktionsarop skulle alltså i pseudokod se ut ungefär
som
> >följande
>
> Fast jag förstår inte VAR i koden värdena läggs in i och tas ifrån
> stacken.
>
dig
> >att det fungerar vid det FÖRSTA anropet av funktionen, var lagrar den då
> >sina egna variabler? Den gör på samma sätt varje gång, fast får
naturligtvis
> >nya adresser, eftersom det är ett nytt anrop, och de gamla adresserna är
> >upptagna. Det spelar ingen roll om funktionen a anropar sig själv eller
> >funktionen b, det går ändå till på samma sätt och den kommer ändå ihåg
> >värdena på allt. Lite grann samma sak som att om du har en variabel x i
en
> >metod i en klass som också har variabeln x så ändras inte objektets värde
på
> >x bara för att metoden ändrar värdet på "sitt" x.
>
> värden, och hur man kan använda sig utav dom. Dvs hur funktionen kan
> veta att den ska ta det gamla värdet och göra något med det samtidigt
> som den gör något med det aktuella värdet...
>
> >något.
>
Magnus svarade väl bra på allt detta. Jag har väl bara en grej att tillägga:
Du tycker att det här låter konstigt och att du inte begriper det, men har
du tänkt på att du ställs inför EXAKT samma problem den första gången
funktionen anropas, eller är det så självklart att allt funkar då att du
inte tänker på det?
/Carl
TG
news:pgvy4.1243$74.1...@newsc.telia.net...
>
> > > Scopes? Vad är det för något?
> >
Räckvidd är väl det vedertagna svenska ordet för scope om jag inte
missminner mig.
/ TG
Dubb
>> Scopes? Vad är det för något?
>
>Magnus svarade väl bra på allt detta. Jag har väl bara en grej att tillägga:
>Du tycker att det här låter konstigt och att du inte begriper det, men har
>du tänkt på att du ställs inför EXAKT samma problem den första gången
>funktionen anropas, eller är det så självklart att allt funkar då att du
>inte tänker på det?
Vad jag inte förstår är att samma variabel kan ha flera olika värden,
och hur 17 man ska veta VILKET värde man räknar med...
--
Dubb
Magnus Bäck
Man räknar alltid med det värde som hör ihop med det aktuella anropet,
och då kan du inte komma åt de värden som gällde när funktionen
anropades (även om det är samma funktion).
Lokala variabler hör inte till en *funktion*, de hör till ett *enskilt
anrop*.
Tänk det som att variabelnamnet inte innehåller värdet utan att det
snarare identifierar en plats i minnet där värdet finns. Vilken
minnesplats som pekas ut beror på vilket anrop det gäller.
--
Magnus Bäck
ba...@swipnet.se
Lars-Åke Aspelin
>On Fri, 10 Mar 2000 21:48:02 GMT, "Carl Nettelblad"
><cne...@hem.passagen.se> wrote:
>
>>Stacken: När en funktion anropas läggs alla parametrar (eller pekare till
>>dem) på stacken. Som en hög (stack) med tallrikar eller byggklossar eller
>>vad som helst. Sedan finns det alltid en global pekare (i allmänhet som ett
>>register, fast det är oviktigt) som pekar på den senaste stackpositionen.
>>När något läggs till stacken ökas den pekaren, när något tas bort från den
>>minskas den. Ett funktionsarop skulle alltså i pseudokod se ut ungefär som
>>följande
>
>Fast jag förstår inte VAR i koden värdena läggs in i och tas ifrån
>stacken.
Så här fungerar en stack. Stacken är den del av datorns minne.
När programexkeveringen kommer till anropet av en funktion i koden
händer följande (i princip) med stacken. Varje rad nedan motsvarar
en adress i minnet. Pilen (--->) motsvarar stackpekaren, dvs den
information som talar om var gränsen mellan använt och ledig minne
i stacken går.
Stacken består i praktiken av tusentals minnesord men här visas
bara tio av orden närmast omkring gränsen mellan använt och ledigt
minne.
Före (A)
=====
Använd del av stacken
-->Använd del av stacken
Ledigt minne
Ledigt minne
Ledigt minne
Ledigt minne
Ledigt minne
Ledigt minne
Ledigt minne
Ledigt minne
Precis när funktionen har anropats (B)
=============================
Använd del av stacken
Använd del av stacken
Återhoppsadress
Parameter 1
-->Parameter 2
Ledigt minne
Ledigt minne
Ledigt minne
Ledigt minne
Ledigt minne
Precis när funktionen är klar (C)
=======================
Använd del av stacken
Använd del av stacken
-->Resultatet av funktionen
Ledigt minne
Ledigt minne
Ledigt minne
Ledigt minne
Ledigt minne
Ledigt minne
Ledigt minne
Ovanstående illustrerar det icke-rekursiva fallet, dvs ett enkelt
anrop av en funktion med två parametrar och ett resultat.
Resultatet av funktionen som ligger på stacken kan sedan
användas i det fortsatta programmet.
Nu kommer vi till fallet att den anropade funktionen i sin tur
anropar en funktion.
Skillnad är att programexekveringen inne i funktionen nu innebär
ett nytt funktionsanrop INNAN dem är klar.
Nu ser stacken alltså ut som B före det nya funktionsanropet
och precis när det andra funktionsanropet har gjorts ser det ut så här
Precis när det andra funktionsanropet gjorts (B2)
====================================
Använd del av stacken
Använd del av stacken
Återhoppsadress
Parameter 1
Parameter 2
Ny återhoppsadress
Ny parameter 1
-->Ny parameter 2
Ledigt minne
Ledigt minne
Sen kan man hålla på sådär så länge man vill (och det lediga
minnet i stacken ej har tagit slut).
Man fyller alltså på med nya parametrar och återhoppsadresser
för varje funktionsanrop och på 'tillbakavägen' så städas stacken
genom att stackpekaren återställs och minnet alltså åter blir ledigt.
Vid det 'näst sista ' återhoppet ser stacken ut så här:
Precis när funktionen är klar (C2)
=======================
Använd del av stacken
Använd del av stacken
Återhoppsadress
Parameter 1
Parameter 2
-->Resultatet av funktionen (näst sista)
Ledigt minne
Ledigt minne
Ledigt minne
Ledigt minne
De som är vanligt vid REKURSION är att det är SAMMA funktion
som anropas 'från sig själv'. Detta innebär bara att Återhoppsadress
och 'Ny återhoppsadress' i själva verket är samma prgramadress.
Men det bryr sig ju inte datorn om, den bara hoppar dit programmet
säger att den ska hoppa. :-)
Ovanstående beskriver hur stacken kan se ut i princip.
Du frågar om " VAR i koden värdena läggs in i och tas ifrån stacken" .
Allt detta görs av de maskininstruktioner som exkveras när programmet
kommer till det ställe då en funktion anropas.
Först görs A->B enligt ovan, sedan görs alla instruktioner som behövs
för att komma fram till funktionens resultat, och sist görs B->C
enligt ovan.
Förslagsvis kan du torrsimma ett enkelt rekursivt program för att
beräkna N-fakultet med den rekursiva definitionen:
fak(n) = fak(n-1) * n (om n >1)
fak(n) = 1 (om n=1)
I detta fall är det ju endast 1 parameter och varje anrop av
funktionen fak resulterar i ett nytt anrop av samma funktion men
med parametern minskad med 1. Undantaget är när parametern är
1.
Då görs inget nytt funktionsanrop utan funktionen returnerar värdet
1 (på stacken)
Så här blir utseendet på stacken när funktionen fak anropas med
parametern 4, tex myresult = fak(4).
A markerar tidigare använt minne.
L markerar ledigt minne.
R markerar återhoppsadressen.
Den position i stacken som stackpekaren pekar på är markerad (.)
A A A (A) L L L L L L L L L L L L L L L L före myresult = fak(4)
A A A A R (4) L L L L L L L L L L L L L L fak(4)
A A A A R 4 R (3) L L L L L L L L L L L fak(4-1)=fak(3)
A A A A R 4 R 3 R (2) L L L L L L L L L fak(3-1)=fak(2)
A A A A R 4 R 3 R 2 R (1) L L L L L L L fak(2-1)=fak(1)
A A A A R 4 R 3 R 2 (1) L L L L L L L L 1 är resultatet fak(1)
A A A A R 4 R 3 R 2 1 (2) L L L L L L L fak(1)*2
A A A A R 4 R 3 R (2) L L L L L L L L = 2
A A A A R 4 R 3 (2) L L L L L L L L L fak(2)=2
A A A A R 4 R 3 2 (3) L L L L L L L L L fak(2)*3
A A A A R 4 R 3 (6) L L L L L L L L L L = 6
A A A A R 4 (6) L L L L L L L L L L L L fak(3)=6
A A A A R 4 6 (4) L L L L L L L L L L L fak(3)*4
A A A A R 4 (24) L L L L L L L L L L L = 24
A A A A (24) L L L L L L L L L L L L L L fak(4)=24
A A A (A) L L L L L L L L L L L L L L L myresult = 24
resultatet (24) har flyttats från stacken till variabeln myresult.
Nu är stacken återställd till läget före anropet myresult = fak(4)
Egentligen ser stacken ut så här
A A A (A) 24 4 24 4 6 3 1 2 L L L L L L
men allt till höger om (A) är ju ledigt igen för nya beräkningar
och kan därför skrivas över vid kommande programexekvering.
Hoppas allt blev kristallklart nu! Se även nedan om att 'hålla koll'
>
>>Jag vet nu inte om det gjorde dig så mycket klokare. Men hur tänker du dig
>>att det fungerar vid det FÖRSTA anropet av funktionen, var lagrar den då
>>sina egna variabler? Den gör på samma sätt varje gång, fast får naturligtvis
>>nya adresser, eftersom det är ett nytt anrop, och de gamla adresserna är
>>upptagna. Det spelar ingen roll om funktionen a anropar sig själv eller
>>funktionen b, det går ändå till på samma sätt och den kommer ändå ihåg
>>värdena på allt. Lite grann samma sak som att om du har en variabel x i en
>>metod i en klass som också har variabeln x så ändras inte objektets värde på
>>x bara för att metoden ändrar värdet på "sitt" x.
>
>Det jag inte fattar är hur funktionen håller koll på alla gamla
>värden, och hur man kan använda sig utav dom. Dvs hur funktionen kan
>veta att den ska ta det gamla värdet och göra något med det samtidigt
>som den gör något med det aktuella värdet...
Funktionen i exemplet ovan med Parameter 1 och parameter 2
'känner endast till' dessa parametrar och var de finns.
Finessen är ju att de alltid finns på samma ställe relativt
relativt stackpekare. Alla instruktioner 'inne i' funktionen som
behöver tillgång till Parameter 1 och Parameter 2 kan nå dessa
indirekt via stackpekaren.
Funktionen känner också till var resultatet från anropade funktioner
finns. I exemplet ovan finns det alltid på samma plats relativt
stackpekaren.
En anropad funktion vet ingenting om den anropande funktionens
parametrar (annat än ev via sina egna parametrar).
En anropande funktion känner till vilka parametrar som nvänds i
funktionsanropet samt resultatet av den anropade funktionen, men
känner inte till något om vad anropande funktionen 'gör'.
Funktionen håller alltså inte 'koll på alla gamla värden', däremot så
håller datorn 'koll på' samtliga värden i den använda delen av
stacken och programexkeveringen ser till att stackpekaren ändras
så att rätt information alltid finns på rätt RELATIV plats och
tillgängliga för den för aktuella funktionen.
>
>>Om inte detta heller hjälper borde du kanske läsa lite om "scopes", eller
>>något.
>
>Scopes? Vad är det för något?
>
>--
>
>Dubb
TG
>
> Vad jag inte förstår är att samma variabel kan ha flera olika värden,
> och hur 17 man ska veta VILKET värde man räknar med...
>
En variabels "scope" (räckvidd) refererar till platsen där variabeln
existerar. Om man generaliserar lite finns det bara två typer av "scopes":
lokalt och globalt. En variabel som har "globalt scope" är synlig i alla
delar av programmet medan en variabel med "lokalt scope" endast existerar i
den del av koden eller funktionen där den är deklarerad.
Variabler deklarerade inuti en funktion (mellan { och }) är lokala (gäller i
alla fall i C++). Dessa variabler är endast giltiga inanför dessa
"krull"-paranteser. "Krull"-paranteser kan vara nästade och då gäller den
"mest lokala" variabeln.
Om vi tittar lite närmare på följande kodsnutt (i C++ då mina kunskaper i
java tyvärr är bristfälliga),
#include <iostream>
int j = 0;
int main( ) {
int j = 10;
{
int j = 30;
{
int j = 50;
cout << j << ", ";
}
cout << j << ", ";
}
cout << j;
return 1;
}
ger den vid körning följande: 50, 30, 10
Som du ser har jag deklarerat j fyra gånger alla med olika "scope" och det
är detta som gör att inte alla utskrifter av j blir 50 (som ju är den
senaste tilldelningen av j innan vi börjar skriva ut den).
Observera att det här med scope kan skilja sig lite mellan olika
programspråk men detta borde ge dig en liten bild av hur det hela fungerar.
/ TG
Dubb
>...
<en lång och tålmodig förklaring av hur en stack fungerar>
>---
Njae... Att säga det vore att ta i... Jag tycker det är fortfarande
mycket oklart. Men jag kan inte riktigt beskriva VAD jag inte
förstår...
Parameter 2? Det var ju bara 1 parameter... n, eller vad menar du?
--
Dubb
Dubb
Trots allt så har jag faktiskt lärt mig något.
Men jag är fortfarande ENORMT förrvirrad över det hela...
Är det bara JAG som tycker 100 rader kod med med ett 10-tal nästlade
for- och if-satser är enklare att följa och förstå en 10 raders
rekursiv kod?
Grejen är ju den att jag verkligen VILL förstå. Jag blir så ENORMT
förbannad på mig själv att jag inte fattar. Jag känner mig helt
värdelös. Usch...
--
Dubb
Carl Nettelblad
> >Magnus svarade väl bra på allt detta. Jag har väl bara en grej att
tillägga:
> >Du tycker att det här låter konstigt och att du inte begriper det, men
har
> >du tänkt på att du ställs inför EXAKT samma problem den första gången
> >funktionen anropas, eller är det så självklart att allt funkar då att du
> >inte tänker på det?
>
> och hur 17 man ska veta VILKET värde man räknar med...
Men det är inte SAMMA variabel. Om du har en array av objekt y som alla har
variabeln x ändras inte y[0].x bara för att y[1].x ändras. Samma sak gäller
för funktioner. Variabeln x i anrop 1 av funktionen f ändras inte för att
variabeln x i anrop2 av funktionen f ändras. De har lika lite med varandra
att göra som om det var variabeln x i funktionen f och variabeln x i
funktionen p. Att det råkar vara samma funktion, som anropar sig själv,
ändrar inte på detta, variablernas värden ligger ändå på olika ställen i
minnet.
/Carl
Dubb
Ok, inte samma variabel. men den har ju iallafall samma NAMN. Och det
är det som gör att jag blir helt förvirrad när jag försöker stega mig
igenom dom kodexempel som givits här...
--
Dubb
Set Lonnert
<rekursion>
Många har lagt ned ett stort arbete på dettta, och det visar ju också hur
svårt det kan vara att försöka förklara ngt. Jag tror nu att jag också
misslyckas, men kan ju åtminstone försöka sälla mig till den skara som
försökt.
(Inte helt korrekt exempel, men det ger åtminstone en hygglig analogi.)
Tänker man just på hur en stack fungerar så kan man på sätt och vis se
rekursionen "inifrån".
Tänk dig att du har en hög med numrerade kort (el. dyl). En stack innebär
att du lägger dessa kort i en hög. Längst ned får du det kort du la först.
Överst får du det kort du la senast.
Antag att du lägger ett kort med siffran "5" på ett bord. Sedan lägger du
dit siffran "6" ovanpå kort med siffran "5". Sedan tar du ett kort till
som har siffran "9" och lägger ovanpå siffran "6":
9 -> 6 -> 5 -> bord
Sedan frågar du din kompis som bara kan addera två kort åt gången att
hjälpa dig med additionen (ovanligt infantil kamrat) av alla kort.
Han tar upp första kortet "9" och sedan det andra "6" adderar dessa, och
lägger ett kort med siffrorna "15" överst. Sedan tar han de två korten
"15" och "5" och adderar och lägger ett kort med siffran "20" överst.
Sedan försöker ha ta upp två kort igen, men misslyckas, han har nått
bordet. Slut.
Ok. Nu har alla kort adderats.
På sätt och vis har kamraten nu följt en (tänkbart) rekursiv procedur.
Denne kan bara addera två kort åt gången varför han gör det upprepade
gånger. När additionen har skett kollar denne om det finns ngt kort kvar.
Finns inget så stoppar denne (motsvarar den där utgångspunkten vilket ofta
brukar vara null eller 0) som ngt exempel varit i beskrivningarna
tidigare. Resultatet finns nu oavsett hur många kort högen från början
innehöll.
Ja, ungefär så där kanske man kan resonera.
Säg att du lär upp kamraten att också t.ex. skriva upp (mellan) resultaten
på en tavla. Då kommer detta att likna även de exempel som har skisserats
i denna tråd ... osv.
mvh!
/Set Lonnert
--
set_l...@algonet.se (to get a signature)
add simplicity
PS. Nu får ngn förklara "funktionell programmering" :)
Lars-Åke Aspelin
> Lars-Åke Aspelin) skrev:
>
>>...
><en lång och tålmodig förklaring av hur en stack fungerar>
>>---
>>
>Njae... Att säga det vore att ta i... Jag tycker det är fortfarande
>mycket oklart. Men jag kan inte riktigt beskriva VAD jag inte
>förstår...
>
>Parameter 2? Det var ju bara 1 parameter... n, eller vad menar du?
>
I förklaringen av hur stacken används (som du klippt bort här ovan)
så var det två parametrar, 'Parameter 1' och 'Parameter 2'.
Det var det jag avsåg. I exemplet med fakultetsberäkningen är
det bara en parameter.
>--
>
>Dubb
Dubb
Ok! Nu var det lite mer i "min nivå"... Tack! Nu förstår jag PRINCIPEN
bakom rekursion, åtminstånde någorlunda. Sen gäller det bara att lära
sig göra det ren kod-mässigt. Och det blir nog svårare...
--
Dubb
TG
> är det som gör att jag blir helt förvirrad när jag försöker stega mig
> igenom dom kodexempel som givits här...
>
(eller om vi har otur, krånglar till det mer).
Det finns två (ja, jag vet att det finns fler men vi kan strunta i dem då de
inte är väsentliga i detta fall då java bara använder dessa två) olika sätt
att skicka variabler till en funktion/procedur/metod (vilket språk du nu
använder). Dessa är call-by-value och call-by-reference.
I de exempel som visats tidigare för dig så använder man call-by-value
(vilket är default för att skicka alla typer utom objekt till en metod i
java har jag för mig).
Call-by-value fungerar på sådant sätt att när ett argument skickas till en
funktion så kopieras det aktuella värdet av variabeln och sedan skickas
kopian in i den anropade metoden. Om man sedan i den anropade metoden ändrar
värdet på den variabeln ändras endast kopians värde medan orginalet behåller
sitt värde.
Ett exempel:
void foo( int i ) {
i++; // den lokala kopian av i ökas på med ett, orginalet är fortfarande
0
// den instans av i som vi jobbar med här har ingen som helst koppling
till "orginalet" utan är en kopia som ligger på en helt annan minnesadress
}
int main() {
int i = 0; // vi kallar denna i för "orginalet"
foo( i ); // "orginalet" kopieras och skickas in till foo
// nu är vi tillbaka i main, kopian är borta i och med att vi lämnade
foo, "orginalet" är 0
return( 1 );
}
/ TG
Lars-Åke Aspelin
Det här med spelkort kanske är ett bra sätt att illustrera rekursion.
För att använda detta i exemplet med fakultetsberäkningen så skulle
förklaringen bli så här.
Definitionen är precis som förut att
fak(n) = fak(n-1) * n (om n > 1)
fak(n) = 1 (om n = 1)
För att beräkna fak(n) ska man alltså anropa en (rekursiv) funktion.
Med spelkorten så kan ett funktionsanrop göras så att man
på ett spelkort skriver
"Undrar vad fak(n) är" och lägger kortet överst i högen.
Sen tittar man på definitionen som säger att fak(n) = fak(n-1) * n
Detta betyder att man ska lägga två kort på högen, ett med fak(n-1)
och ett med n på och sedan ber man kompisen multiplicera det som står
på de två översta korten och skriva det på nästa kort (under de två
överst).
Men nu var det ju så att på det första kortet står det "Undrar vad
fak(n-1) är. Innan vi lägger på kortet som det står n på så måste vi
alltså 'beräkna' fak(n-1).
Detta görs genom att lägga på ett kort med texten "Undrar vad fak(n-2)
är" och ett kort med n-1 på. Men innan vi lägger på kortet med n-1 på
så måste vi 'beräkna' fak(n-2). Osv, osv ända tills vi har en hel hög
med kort som det står "Undrar vad fak(n-nåt) är" på.
Och överst ligger ett kort som det står "Undrar vad fak(1) är".
Det ges ju av definitionen på fak(). Så vi skriver 1 på det kortet.
När nu fak(1) är beröknad så lägger vi så på kortet med siffran 2 på.
Sen ber vi kompisen multiplicera de två översta korten i högen och
skriva ner resultatet på kortet under. Överst i bunten ligger ett kort
med en 2:a, under det ligger ett kort med en 1:a och under det ligger
ett kort med "Undrar vad fak(2) är". Kompisen multiplicerar 2 med 1
och noterar resultatet, dvs 2, på kortet som det stod "Undrar vad
fak(2) är" på. Nu när vi har 'beräknat' fak(2), som ju var den första
faktorn i beräkningen av fak(3) så är det dags att lägga på ett kort
med den andra faktorn i fak(3) som ju är 3. Kompisen gör sen
multiplikationen av de två översta korten, 3 och 2, och noterar
resultatet, 6, på kortet som ligger under och på vilket det står
"Undrar vad fak(3) är".
Så där håller man på och multiplicerar tills man har två kort kvar.
På det översta stod det tidigare "Undrar vad fak(n-1) är" och
det har kompisen nu beräknat och skrivit dit.
På det understa står det "Undrar vad fak(n) är".
Den sista sekvensen är att lägga på kortet med den
andra faktorn i beräkningen av fak(n) och det är ju n.
Sista gången som kompisen kallas in multipliceras talen på
det två översta korten, dvs fak(n-1) och n. Resultatet blir såklart
fak(n) och det noteras på det understa kortet.
Sen är rekursionen slut.
/Lars-Åke
P.S. Jag klarar inte heller att addera (eller multiplicera) mer än två
(små) tal åt gången. (Svårt att tänka mig nån som kan det).
Om talen är lika så klarar jag dock en 'simultan addition'
genom att använda multiplikation. ;-)
Set Lonnert
>>(Inte helt korrekt exempel, men det ger åtminstone en hygglig analogi.)
> Ok! Nu var det lite mer i "min nivå"... Tack! Nu förstår jag PRINCIPEN
> bakom rekursion, åtminstånde någorlunda. Sen gäller det bara att lära
> sig göra det ren kod-mässigt. Och det blir nog svårare...
OK, nu kom jag på ett mer adekvat exempel.
Säg att du har återigen samma kompis (det kan vara bra att ha en mindre
kunnig kamrat). Denne har nu fått instruktioner av dig att söka reda på en
kamera (tja, det bara uppfann jag nu) som ligger i ett floddelta. Dvs. det
är en flod som delar upp sig som ett "träd" ju längre ut man kommer.
Senare blir det smärre och fler uppdelningar liksom.
Så du har glömt den på en flodkant ngnstans.
Kompisen får med sig en mängd saker som denne kan ha för att hitta
tillbaka också, en boll, ett dragspel, en Palm V och ett äpple (motsvarar
returstacken för rekursiva funktioner).
Så kompisen börjar.
Nu delar sig deltat i två avfarter, en går åt höger och en går åt vänster.
Han tar den högra, men lägger samtidigt en boll vid floddelningen (ett
binärt träd).
Hittar fortfarande inget. Så uppträder en ny floddelning (finns bara
binära delningar här). Kompisen tar till höger igen, och lägger samtidigt
ett dragspel vid delningen.
Men så tar floden slut, och komisen får ro tillbaka. Nu tar denne upp
dragspelet igen, men fortsätter i stället till vänster där denne inte hade
varit förut.
Floden verkar dela upp sig och en ny sak kan placeras ut ...
Nåja, hoppar vi fram i rapporten från kompisen så säger vi att denne
hittar tillslut kamran, men vill vara säker på att det inte finns fler, så
hela deltat kollas igenom på samma sätt.
Tillbaka så har denne alla saker som användes för att markera delningar
(omvända returadresser) samt alla dina ev. glömda kameror.
Hur ser då detta ut i programmering?
Ja, ta detta träd och syna metoden inorderWalk() i det följande:
---
abstract class Node { }
class TreeNode extends Node {
Object value;
int key;
TreeNode left, right, parent;
TreeNode(int _key, Object _value) {
key = _key;
value = _value;
}
}
class BinarySearchTree {
TreeNode root;
TreeNode nil = new TreeNode(0, "nil"); // special
boolean isEmpty() {
return (root == null);
}
TreeNode minimum(TreeNode x) {
while (x.left != null) {
x = x.left;
}
return x;
}
TreeNode maximum(TreeNode x) {
while (x.right != null) {
x = x.right;
}
return x;
}
TreeNode successor(TreeNode x) {
if (x.right != null) {
return minimum(x.right);
}
TreeNode y = x.parent;
while ((y != null) && (x == y.right)) {
x = y;
y = x.parent; // alt: y.parent :)
}
return y;
}
TreeNode predecessor(TreeNode x) {
if (x.left != null) {
return maximum(x.left);
}
TreeNode y = x.parent;
while ((y != null) && (x == y.left)) {
x = y;
y = x.parent; // alt: y.parent :)
}
return y;
}
TreeNode insert(TreeNode z) {
TreeNode x = root, y = null;
while (x != null) {
y = x;
if (z.key < x.key) {
x = x.left;
} else {
x = x.right;
}
}
z.parent = y;
if (y == null) {
root = z;
} else {
if (z.key < y.key) {
y.left = z;
} else if (z.key > y.key) {
y.right = z;
} else {
Object t = z.value;
z.value = y.value;
y.value = t;
return z;
}
}
return null;
}
TreeNode delete(TreeNode z) {
TreeNode x = null, y = null;
if ((z.left == null) || (z.right == null)) {
y = z;
} else {
y = successor(z);
}
if (y.left != null) {
x = y.left;
} else {
if (y.right == null) {
x = nil;
} else {
x = y.right;
}
}
if (x != null) {
x.parent = y.parent;
}
if (y.parent == null) {
if (x == nil) {
root = null;
} else {
root = x;
}
} else {
if (y == y.parent.left) {
if (x == nil) {
y.parent.left = null;
} else {
y.parent.left = x;
}
} else {
if (x == nil) {
y.parent.right = null;
} else {
y.parent.right = x;
}
}
}
if (y != z) {
z.key = y.key;
z.value = y.value; // if more fields copy them!
}
return y;
}
void inorderWalk(TreeNode x) {
if (x != null) {
inorderWalk(x.left);
System.out.println(" For key: " + x.key + ", value: " + x.value);
inorderWalk(x.right);
}
}
TreeNode search(TreeNode x, int k) {
if ((x == null) || (k == x.key)) {
return x;
}
if (k < x.key) {
return search(x.left, k);
} else {
return search(x.right, k);
}
}
}
public class Main {
public static void main(String args[]) {
BinarySearchTree b = new BinarySearchTree();
// the order of insertion random
TreeNode s = new TreeNode(6, "Macaper");
b.insert(new TreeNode(10, "Hyperbolis"));
b.insert(new TreeNode(2, "Margolia"));
b.insert(s);
b.insert(new TreeNode(8, "Hyperbolis"));
b.insert(new TreeNode(12, "Moree"));
b.insert(new TreeNode(4, "Grounded"));
// walk and print
b.inorderWalk(b.root);
System.out.println();
// search no 12
System.out.println(" Search no 12 " + b.search(b.root, 12).value);
System.out.println();
// delete no 6 and walk and print
b.delete(s);
System.out.println();
b.inorderWalk(b.root);
System.out.println();
// replace no 4 and walk and print
b.insert(new TreeNode(4, "Poff!"));
System.out.println();
b.inorderWalk(b.root);
}
}
--
Du ser förmodligen att sökningen genom trädet går igenom varje delning
och söker vidare rekursivt åt vänster och sedan vid returerna från
flodåtervändskanterna till höger, denna gång.
Set Lonnert
<mer bla bla>
> OK, nu kom jag på ett mer adekvat exempel.
Och, nu när hjärnsläppet inträtt så ett ännu mer förbättrat ex.
Istället för en "omvänd returstack" som rekursionen arbetar efter så är
det nu en mer proper analogi med mer äkta returstack ...
Samma BinarySearchTree ...
Nu är det så att vi har en Recursator som letar efter en viss Sarah. I
satden dit Recursator har kommit så är vägarna endast tudelade. Men vid
varje vägkorsning så finns två skyltar. En som pekar åt vänster och en som
pekar åt höger. Ok, vi har ett villaområde där Sarah bor med en inkörsväg
(rot).
Recursator arbetar nu efter principen att först titta åt vänster och rycka
ned skylten som pekar åt vänster (push returadress). Sedan vandra gatan
ner och se om Sarah finns där. Möjligen möter Recursator en återvändsgränd
och får gå tillbaka. På tillbakavägen spikar Recursator upp
vänsterpekarskylten igen (pop returadress), men river ned
högerpekarskylten på väg nedåt gatan till höger. På så vis traverserar
Recursator hela området, och kanske hittar flera Sarah (närmare bestämt
tre) på vägen.
Ja, under tiden Recursator har vandra igenom hela området ryckt ner alla
skyltar och spikat up dessa igen, så har denne använt en s.k. "returstack"
att placera skyltarna i. Dvs. Recursator behövde bara lägga skyltarna som
i en kortlek och spika upp de vartefter -- ingen typ av sortering behövs.
Dessutom kommer Recursator inte ha någon skylt över när allt är färdigt.
Det är detta som är det eleganta med rekursiva funktioner. Man behöver
liksom inte bekymra sig om att hålla rätt på nivåer etc. Recursator
behöver heller inte vara särskilt klyftig och spara ngt. Denne spara
visserligen i detta fall alla returadresser, men i Javas fall så sköts det
automatiskt genom det sätt på vilket metoder fungerar.
Vid en återvändsgränd så sker ju return.
Till slut yttrar Recursator: I'll be back. Vilket ju är sant :)
Carl Nettelblad
"Dubb" <du...@pzz.duh..pi> wrote in message
> Tack alla ni som försökt hjälpa mig förstå rekursiv programering!
> Trots allt så har jag faktiskt lärt mig något.
> Men jag är fortfarande ENORMT förrvirrad över det hela...
>
> Är det bara JAG som tycker 100 rader kod med med ett 10-tal nästlade
> for- och if-satser är enklare att följa och förstå en 10 raders
> rekursiv kod?
Jag föredrar helt klart den rekursiva. Kort och koncist. Också ur ett
underhållsperspektiv, om du upptäcker att något behöver ändras behöver du
bara ändra en rad i rekursionslösningen, mot tio rader i den andra. Men,
använd det du förstår. Som många har sagt är rekursion aldrig den optimala
lösningen, då bland annat allt läggande på stacken faktiskt är lite långsamt
(kanske särskilt i Java). Hur lång tid det "borde" ta att hitta dina
kombinationer vet jag tyvärr inte.Om jag får tid över kan jag ju testa att
skriva ett program själv och köra på min Celeron 466. Om min tid kommer
under din visar det ju då att det finns någon fantastisk liten optimering
som du har glömt.
/Carl
Torkel Franzen
>Som många har sagt är rekursion aldrig den optimala lösningen, då
>bland annat allt läggande på stacken faktiskt är lite långsamt >
>(kanske särskilt i Java).
Varför just i Java?
>Hur lång tid det "borde" ta att hitta dina
>kombinationer vet jag tyvärr inte.Om jag får tid över kan jag ju testa att
>skriva ett program själv och köra på min Celeron 466.
För den rekursivt definierade strängpermuteraren jag gav tar det en
minut att leverera permutationerna av 9 element på en Sparc 5.
Dubb
Tyvär är det där ett på tok för krångligt kod-exempel för mig... Jag
fattar i princip ingenting av det...
--
Dubb
Dubb
>Set Lonnert <set...@algonet.se> skrev:
><mer bla bla>
>
>> OK, nu kom jag på ett mer adekvat exempel.
Du får nog ge upp med mig nu. Vi är på helt olika nivåer... Jag känner
mig bara dum när jag läser det du skriver. Sorry :(
--
Dubb
Dubb
<cne...@hem.passagen.se> wrote:
>
>"Dubb" <du...@pzz.duh..pi> wrote in message
>news:66elcs0ed35oakhot...@4ax.com...
>> Tack alla ni som försökt hjälpa mig förstå rekursiv programering!
>> Trots allt så har jag faktiskt lärt mig något.
>> Men jag är fortfarande ENORMT förrvirrad över det hela...
>>
>> Är det bara JAG som tycker 100 rader kod med med ett 10-tal nästlade
>> for- och if-satser är enklare att följa och förstå en 10 raders
>> rekursiv kod?
>
>Jag föredrar helt klart den rekursiva. Kort och koncist. Också ur ett
>underhållsperspektiv, om du upptäcker att något behöver ändras behöver du
>bara ändra en rad i rekursionslösningen, mot tio rader i den andra. Men,
>använd det du förstår. Som många har sagt är rekursion aldrig den optimala
>lösningen, då bland annat allt läggande på stacken faktiskt är lite långsamt
>(kanske särskilt i Java).
Grejen är ju den all jag VILL förstå. Jag VILL lära mig rekursion. men
jag förstår inte hur man ska tänka rent kod.mässigt helt enkelt.
När ni ger exempel på rekursiv programering verkar ni se det som en
barnlek. Men jag ser det som relativitetsteorin. Jag har förståt att
det ÄR så. Men inte hur eller varför.
--
Dubb
Dubb
wrote:
>"Carl Nettelblad" <cne...@hem.passagen.se> writes:
>
> >Som många har sagt är rekursion aldrig den optimala lösningen, då
> >bland annat allt läggande på stacken faktiskt är lite långsamt >
> >(kanske särskilt i Java).
>
> Varför just i Java?
>
> >Hur lång tid det "borde" ta att hitta dina
> >kombinationer vet jag tyvärr inte.Om jag får tid över kan jag ju testa att
> >skriva ett program själv och köra på min Celeron 466.
>
> För den rekursivt definierade strängpermuteraren jag gav tar det en
>minut att leverera permutationerna av 9 element på en Sparc 5.
Hur snabb är en Sparc 5 jämfört med en PC med Athlon 600Mhz? SÅ man
kan jämföra menar jag...
--
Dubb
Christian Sunesson
>lösningen, då bland annat allt läggande på stacken faktiskt är lite långsamt
Hur kommer det sig att ingen har nämnt tail-recursion än? En
svansrekursiv funktion anropar sig själv som det sista den gör,
vilket gör att de lokala variablerna inte behövs längre och stacken
behövs inte stegas upp.
Sen finns det ju språk där man eliminerar risken att ett funktions-
anrop kommer tillbaks och därmed struntar att spara sina stack-
variabler. Men det är inte 100% förknippat med rekursion.
Tomas Ogren
Haha.. Sparc 5:an är väl ungf som en 486:a ... inte speciellt jämförbar
alls.
/Tomas
--
Tomas Ögren, st...@ing.umu.se, http://www.ing.umu.se/~stric/
|- Student at Computing Science, University of Umeå
`- Sysadmin at {cs,ing,acc}.umu.se
Torkel Franzen
> Tyvär är det där ett på tok för krångligt kod-exempel för mig... Jag
> fattar i princip ingenting av det...
>
Men du citerade alltihop!
Torkel Franzen
> Hur snabb är en Sparc 5 jämfört med en PC med Athlon 600Mhz? SÅ man
> kan jämföra menar jag...
En Sparc 5 är väl ungefär som en 400 MHz Pentium II.
Mikael Wahlberg
> > Hur snabb är en Sparc 5 jämfört med en PC med Athlon 600Mhz? SÅ man
> > kan jämföra menar jag...
>
> En Sparc 5 är väl ungefär som en 400 MHz Pentium II.
I vilken värld då? (eller menar du kanske Ultra 5? :)
/Mikael
----------------------------------------------------------------------------
Mikael Wahlberg | mik...@acc.umu.se | SysAdm @ {acc|lh}.umu.se
Klaverstråket 17 | mik...@mw.mw | Tel. +46 (0)90 128988
903 53 UMEÅ | http://www.acc.umu.se/~mikael | GSM +46 (0)70 3992496
Torkel Franzen
> I vilken värld då? (eller menar du kanske Ultra 5? :)
Jo, Sparc 5 = Sparc Ultra 5.
Carl Nettelblad
"Torkel Franzen" <tor...@sm.luth.se> wrote in message
news:vcbsnxw...@beta13.sm.luth.se...
> "Carl Nettelblad" <cne...@hem.passagen.se> writes:
>
> >Som många har sagt är rekursion aldrig den optimala lösningen, då
> >bland annat allt läggande på stacken faktiskt är lite långsamt >
> >(kanske särskilt i Java).
>
>
> >Hur lång tid det "borde" ta att hitta dina
att
> >skriva ett program själv och köra på min Celeron 466.
>
> minut att leverera permutationerna av 9 element på en Sparc 5.
Är det Sparc(Station) 5 eller Ultra 5? De med namn på bara Sparc var väl
rätt många år sedan? Och även de nuvarande finns ju i rätt olika
konfigurationer.
Leif Karlsson
> Grejen är ju den all jag VILL förstå. Jag VILL lära mig rekursion. men
> jag förstår inte hur man ska tänka rent kod.mässigt helt enkelt.
> När ni ger exempel på rekursiv programering verkar ni se det som en
> barnlek. Men jag ser det som relativitetsteorin. Jag har förståt att
> det ÄR så. Men inte hur eller varför.
Hum, kanske om du ser det så här, *varje gång* en funktion anropas så
allokerar (hittar ledigt utrymme, skaffar fram...) operativsystemet ett
litet block med minne (tillräckligt mycket för att få plats med all
funktionens variabler osv), exempel:
foo (2, 3); /* anropa foo */
int foo (int a, int b) {
int c; ....
Tillräckligt mycket minne för att få plats med a, b & c (plus några
saker till, för att kunna återställa saker & ting "på vägen till baka",
varifrån du anropar funktionen, var den *anropande* funktionen har sina
variabler etc).
Sedan *kopieras* 2 till plats ett i detta block (kallas 'a' ovan, för
att göra livet lite lättare), 3 till plats två (b ovan) & 'c' är platts
3, slutligen talar man om för CPU'n var någonstans den kan hitta detta
(nya) block med minne.
Sedan kan foo göra vad han vill, om han anropar en funktion (kan vara
vilken som helst, inklusive säg själv) så går man igenom samma procedur
igen, ett nytt block med minne skaffas fram, parametrar kopieras etc.
När foo sedan ska återvända till den plats där ifrån den anropades så,
returneras ev retur värde, man talar om för CPU'n var föregående block
har sina variabler, åter vänder till anropsplatsen, lämnar till backa
minne till operativsystemet etc.
Man hittar ALLTID tillbaka till den *anropande* platsen igenom att
återställa saker och ting med hjälp av information som den anropade
funktionen har sparat åt dig, så du kan ALLTID komma till back till
anrops platsen.
Så, effekten av att anropa sig själv är att man startar om funktionen
från början fast med nya parametrar & variablerna använder ett nytt
område I minnet.
Skriv ut på papper, läs igenom & fundera (eventuellt kan du skissa
lite).
--
Leif
Dubb
Det är lite väl mycket teori för mig, det här. Jag blir bara snurrig.
jag kommer aldrig kunna skriva rekursiv kod om det är så här svårt...
--
Dubb
Lars-Åke Aspelin
Kan du inte posta något litet program som du har skrivit och där du
använder anrop av någon egenprogrammerad funktion med parametrar.
Dvs helt utan rekursion, bara enkla (men flera) funktionsanrop.
Om du inte skrivit något sådant program så kanske det är en bra idé
att börja med det.
Om du har skrivit ett sådant program så kan nästa steg vara att
förstå hur det programmet fungerar i detalj, dvs hur parametrar
lagras på stacken och hur programexekveringen 'hittar tillbaka'
efter funktionsanropet.
Om du vill ha ett uppslag till program så kommer en spec här.
Skriv ett program med en funktion f som har två parametrar,
a och b.
Resultatet av funktionen ska vara produkten av a och b, dvs a*b.
Huvudprogrammet ska först anropa f(10,2) och spara resultatet
i en variabel 'prod1'.
Sen ska huvudprogrammet anropa f(5,3) och spara resultatet
i en variabel 'prod2'.
Slutligen ska huvudprogrammet anropa f(prod1,prod2) och
spara resultatet i en variabel 'resultat'.
Skriv programmet och stega igenom det hela med papper och
penna och notera hur programexekveringen 'hittar parametrar'
och 'hittar tillbaka' vid de olika anropen.
Sen kan du ju skriva om programmet så att det anropar f
på följande sätt: resultat = f( f(10,2), f(5,3) )
och konstatera att resultatet blir detsamma som tidigare
(dvs 300)
OBS! Du har fortfarande inte behövt använda någon rekursiv funktion.
När du förstått detta helt kan du börja tänka på hur rekursiva
funktioner, dvs funktioner som anropar sig själv, fungerar.
Dvs där det i koden som beskriver f finns ett anrop av f.
Det är ju absolut inte nödvändigt, men bra, att förstå hur
datorn hanterar programkod, stack, minne etc i detalj.
Du får väl bestämma dig för om du kan acceptera att
förstå rekursiva algoritmer (och programmering av sådana)
UTAN att hänga upp dig på hur datorn fungera i detalj
eller om du vill veta även detaljerna.
I det senare fallet är det nog lämpligt att börja med något
enklare än rekursiva funktioner.
I den ursprungliga frågan skrev du att du
"har goda kunskaper i matematik och logiskt tänkande".
Då borde det inte vara något större problem att 'abstrahera
bort' de tekniska detaljerna i datorn och helt enkelt acceptera
att datorn klarar av att hålla rätt på detaljerna själv.
Det kluriga på den abstrakta nivån är ju att se till att en rekursiv
algoritm som ska (exekveras i en dator) har ett slut (på ändlig tid).
Det måste alltså finnas något fall då funktionen f INTE anropar
sig själv utan returnerar ett värde beräknat UTAN att (direkt
eller via annan funktion eller procedur) anropa sig själv.
I exemplet med fakultetsberäkningen är detta när parametern till
funktionen är lika med 1, i fallet med floddeltat är det när
floden 'tar slut' och kompisen måste vända kanoten (om den
inte redan gått på grund ;-)
Lycka till!
/ Lars-Åke
Mikael Wahlberg
> > I vilken värld då? (eller menar du kanske Ultra 5? :)
> Jo, Sparc 5 = Sparc Ultra 5.
I min värld (Och många andras) är en Sparc5 = SparcStation5 och en
Ultra 5 en UltraSparc.
Bara så vi är överens om vad vi menar :)
Leif Karlsson
> Det är lite väl mycket teori för mig, det här. Jag blir bara snurrig.
> jag kommer aldrig kunna skriva rekursiv kod om det är så här svårt...
Hur f*n (ursäkta) kan du ha funderat igenom det här på mindre än 90
minuter? Det tar längre tid än så, om du vill förstå det här med
rekursiv programmering, jag tycker att du ska fundera på det här
åtminstone under natten.
Kan du inte tala om exakt var du "tappar tråden"? dvs vad är det du
förstår & vad exakt är det som är svårt att greppa? Jag förklarar gärna
(och antar att andra gör oxå) bara jag (vi) vet *vad* jag (vi) ska
förklara.
Stoppa in frågorna i texten precis där du tycker att det blir
obegripligt, så vi får en chans att förklara.
--
Leif
Dubb
(Lars-Åke Aspelin) wrote:
>>Det är lite väl mycket teori för mig, det här. Jag blir bara snurrig.
>>jag kommer aldrig kunna skriva rekursiv kod om det är så här svårt...
>>
>>--
>>
>>Dubb
>
>Kan du inte posta något litet program som du har skrivit och där du
>använder anrop av någon egenprogrammerad funktion med parametrar.
>Dvs helt utan rekursion, bara enkla (men flera) funktionsanrop.
>Om du inte skrivit något sådant program så kanske det är en bra idé
>att börja med det.
>Om du har skrivit ett sådant program så kan nästa steg vara att
>förstå hur det programmet fungerar i detalj, dvs hur parametrar
>lagras på stacken och hur programexekveringen 'hittar tillbaka'
>efter funktionsanropet.
Jag har skrivit sådana program. Och sånt är inget problem för mig att
hänga med i. Fast jag har bara gjort 4 stycken java-program hittils,
och ingen av dom har varit speciellt små. Det som visar alla
permutationer av en sträng är på 6238 tecken, jag kan ju visserligen
posta det om du vill.
>Om du vill ha ett uppslag till program så kommer en spec här.
>
>Skriv ett program med en funktion f som har två parametrar,
>a och b.
>Resultatet av funktionen ska vara produkten av a och b, dvs a*b.
>Huvudprogrammet ska först anropa f(10,2) och spara resultatet
>i en variabel 'prod1'.
>Sen ska huvudprogrammet anropa f(5,3) och spara resultatet
>i en variabel 'prod2'.
>Slutligen ska huvudprogrammet anropa f(prod1,prod2) och
>spara resultatet i en variabel 'resultat'.
>
>Skriv programmet och stega igenom det hela med papper och
>penna och notera hur programexekveringen 'hittar parametrar'
>och 'hittar tillbaka' vid de olika anropen.
Inga problem här inte...
>Sen kan du ju skriva om programmet så att det anropar f
>på följande sätt: resultat = f( f(10,2), f(5,3) )
>och konstatera att resultatet blir detsamma som tidigare
>(dvs 300)
>OBS! Du har fortfarande inte behövt använda någon rekursiv funktion.
Här hänger jag fortfarande med. Inga problem.
>När du förstått detta helt kan du börja tänka på hur rekursiva
>funktioner, dvs funktioner som anropar sig själv, fungerar.
>Dvs där det i koden som beskriver f finns ett anrop av f.
Nu får du nog visa hur jag ska skriva koden då... med f och så...
>Det är ju absolut inte nödvändigt, men bra, att förstå hur
>datorn hanterar programkod, stack, minne etc i detalj.
Jag har nog redan gett upp på den punkten. Nu försöker jag bara förstå
hur man ska tänka för att skriva rekursiv kod.
>Du får väl bestämma dig för om du kan acceptera att
>förstå rekursiva algoritmer (och programmering av sådana)
>UTAN att hänga upp dig på hur datorn fungera i detalj
>eller om du vill veta även detaljerna.
>I det senare fallet är det nog lämpligt att börja med något
>enklare än rekursiva funktioner.
Som sagt... (se ovan) :)
>I den ursprungliga frågan skrev du att du
>"har goda kunskaper i matematik och logiskt tänkande".
>Då borde det inte vara något större problem att 'abstrahera
>bort' de tekniska detaljerna i datorn och helt enkelt acceptera
>att datorn klarar av att hålla rätt på detaljerna själv.
Problem och problem... Jag bryr mig inte längre om att förstå exakt
hur det fungerar. Men jag förstår ju inte ens hur man ska tänka för
att skriva rekursiv kod. Och det är DET som är problemet....
--
Dubb
Dubb
<leif.k...@mbox332.swipnet.se> wrote:
>Dubb skrev:
>> Det är lite väl mycket teori för mig, det här. Jag blir bara snurrig.
>> jag kommer aldrig kunna skriva rekursiv kod om det är så här svårt...
>
>Hur f*n (ursäkta) kan du ha funderat igenom det här på mindre än 90
>minuter? Det tar längre tid än så, om du vill förstå det här med
>rekursiv programmering, jag tycker att du ska fundera på det här
>åtminstone under natten.
>
>Kan du inte tala om exakt var du "tappar tråden"? dvs vad är det du
>förstår & vad exakt är det som är svårt att greppa? Jag förklarar gärna
>(och antar att andra gör oxå) bara jag (vi) vet *vad* jag (vi) ska
>förklara.
Jag har svårt att beskriva exakt VAD jag inte förstår...
>Stoppa in frågorna i texten precis där du tycker att det blir
>obegripligt, så vi får en chans att förklara.
Ok...
det du skrev:
>Hum, kanske om du ser det så här, *varje gång* en funktion anropas så
>allokerar (hittar ledigt utrymme, skaffar fram...) operativsystemet ett
>litet block med minne (tillräckligt mycket för att få plats med all
>funktionens variabler osv), exempel:
>
>foo (2, 3); /* anropa foo */
>
>int foo (int a, int b) {
>
> int c; ....
>
>Tillräckligt mycket minne för att få plats med a, b & c (plus några
>saker till, för att kunna återställa saker & ting "på vägen till baka",
>varifrån du anropar funktionen, var den *anropande* funktionen har sina
>variabler etc).
>
>Sedan *kopieras* 2 till plats ett i detta block (kallas 'a' ovan, för
>att göra livet lite lättare), 3 till plats två (b ovan) & 'c' är platts
>3, slutligen talar man om för CPU'n var någonstans den kan hitta detta
>(nya) block med minne.
>
>Sedan kan foo göra vad han vill, om han anropar en funktion (kan vara
>vilken som helst, inklusive säg själv) så går man igenom samma procedur
>igen, ett nytt block med minne skaffas fram, parametrar kopieras etc.
>
>När foo sedan ska återvända till den plats där ifrån den anropades så,
>returneras ev retur värde, man talar om för CPU'n var föregående block
>har sina variabler, åter vänder till anropsplatsen, lämnar till backa
>minne till operativsystemet etc.
Det är här (stycket ovanför) jag tappar tråden... Fast jag har redan
gett upp när det gäller att förstå hur datorn arbetar i det här
fallet... Det enda jag vill är att kunna skriva egna rekursiva
funktioner...
--
Dubb
Leif Karlsson
>
> Det är här (stycket ovanför) jag tappar tråden... Fast jag har redan
> gett upp när det gäller att förstå hur datorn arbetar i det här
> fallet...
Så jag låter bli att förklara exakt hur datorn reder ut detaljerna då,
ok?
> Det enda jag vill är att kunna skriva egna rekursiva
> funktioner...
Kan du acceptera att (för att citera mig själv):
"Effekten av att anropa sig själv är att man startar om funktionen
från början fast med nya parametrar & variablerna använder ett nytt
område I minnet."?
Förstår du konsikväserna av detta, dvs att om funktionen anropar sig
själv så kommer funktionens variabler nu ej att använda samma platser i
minnet, trots att dom har samma namn, det vill säga att den ej skriver
över de "ursprungliga" eller "gamla" variablerna?
Låt oss ta ett riktigt enkelt exempel, säg att vi har en funktion som
tar en parameter kallad x, om x är 0 så returnerar den x (dvs 0), annars
så subtraherar den 1 från x, anropar sedan sig själv med x som
parameter, när den återvänder sparas även retur värdet i x. Är du med
såhär långt?
Skulle se ut såhär i C (jag behärskar inte java, fast C är ganska likt):
int foo (int x) {
if (x == 0) {
return (x);
} else {
x = x - 1;
x = foo(x);
return (x)
};
}
Låt oss säga att vi anropar foo med 1 som parameter, foo kommer nu att
testa om x är 0, vilket den inte är, så den subtraherar 1 från x,
anropar foo med x som parameter (vilken nu är 0) foo kommer nu att testa
om x är 0, vilket den är, så foo returnerar x (dvs 0) som sparas i
föregående foo's x vilken returnerar x (dvs 0) till oss.
Fortfarande lika förvirrad?
--
Leif
Bjorn Andersson
Dubb wrote:
>
> On Sun, 12 Mar 2000 22:20:42 +0100, Leif Karlsson
> <leif.k...@mbox332.swipnet.se> wrote:
>
> >Dubb skrev:
> >> Det är lite väl mycket teori för mig, det här. Jag blir bara snurrig.
> >> jag kommer aldrig kunna skriva rekursiv kod om det är så här svårt...
[snip]
> Det enda jag vill är att kunna skriva egna rekursiva
> funktioner...
Okej, om du inte är intresserad av stackar och minneshantering
egentligen, så kan man göra det enklare. Här är ett (ganska banalt)
exempel, som du kan kopiera och köra rätt upp och ner.
Klassen RecursiveSort har två statiska metoder (utöver main).
"swap" byter bara plats på värdena i två element efter varandra i en
array.
"sort" löper igenom arrayen, jämför värdena i två efter varandra
liggande element, och om det första är *högre* än det andra, anropas
"swap".
Rekursiviteten i detta ligger i att "sort" efter denna genomlöpning,
anropar sig själv.
Man skulle lika gärna kunnat lösa det genom ytterligare en loop, men det
var ju rekursivitet du var ute efter...
//-------------------------------------------------------
public class RecursiveSort {
//-------------------------------------------------------
static void sort(int a[])
{
boolean found = false;
for (int i = 0; i < a.length-1; i++ )
{
if( a[i] > a[i+1] )
{
swap(a, i); // Ett byte har skett, så arrayen är
found = true; // ännu inte "färdigsorterad"
}
}
if (found) sort(a); // *** Här sker det rekursiva anropet ***
}
//-------------------------------------------------------
static void swap(int a[], int i)
{
int T;
T = a[i];
a[i] = a[i+1];
a[i+1] = T;
}
//-------------------------------------------------------
public static void main(String[] args)
{
int[] a = new int[11];
for (int i = 0; i < 11; i++) a[i] = 20 - i;
sort(a);
for (int i = 0; i < 10; i++) System.out.println(a[i]);
}
}
//-------------------------------------------------------
Vad gäller stackar, mm, i detta exempel, måste man hålla i minnet att
även om Java faktiskt skickar parametrar "by Value", (dvs kopierar
värdet av parametern), så kopieras i detta fall bara "referensen" till
"objektet" a. I Java är även arrayer objekt.
--
mvh
Björn A
Dubb
<leif.k...@mbox332.swipnet.se> wrote:
>Dubb skrev:
>>
>> Det är här (stycket ovanför) jag tappar tråden... Fast jag har redan
>> gett upp när det gäller att förstå hur datorn arbetar i det här
>> fallet...
>
>Så jag låter bli att förklara exakt hur datorn reder ut detaljerna då,
>ok?
Det låter bra. :)
>> Det enda jag vill är att kunna skriva egna rekursiva
>> funktioner...
>
>Kan du acceptera att (för att citera mig själv):
>
>"Effekten av att anropa sig själv är att man startar om funktionen
>från början fast med nya parametrar & variablerna använder ett nytt
>område I minnet."?
Det kan jag acceptera, ja.
>Förstår du konsikväserna av detta, dvs att om funktionen anropar sig
>själv så kommer funktionens variabler nu ej att använda samma platser i
>minnet, trots att dom har samma namn, det vill säga att den ej skriver
>över de "ursprungliga" eller "gamla" variablerna?
Jag tror jag förstår konsekvenerna, ja.
>Låt oss ta ett riktigt enkelt exempel, säg att vi har en funktion som
>tar en parameter kallad x, om x är 0 så returnerar den x (dvs 0), annars
>så subtraherar den 1 från x, anropar sedan sig själv med x som
>parameter, när den återvänder sparas även retur värdet i x. Är du med
>såhär långt?
Nä... Vad är returvärde för något?
>Skulle se ut såhär i C (jag behärskar inte java, fast C är ganska likt):
>
>int foo (int x) {
> if (x == 0) {
> return (x);
> } else {
> x = x - 1;
> x = foo(x);
> return (x)
> };
>}
>
>
>Låt oss säga att vi anropar foo med 1 som parameter, foo kommer nu att
>testa om x är 0, vilket den inte är, så den subtraherar 1 från x,
>anropar foo med x som parameter (vilken nu är 0) foo kommer nu att testa
>om x är 0, vilket den är, så foo returnerar x (dvs 0) som sparas i
>föregående foo's x vilken returnerar x (dvs 0) till oss.
>
>Fortfarande lika förvirrad?
Ja... hur 17 ska jag kunna hålla reda på om x är "nuvarande" eller
"föregående" foo's x? det bara snurrar runt i skallen....
--
Dubb
Dubb
<bjorn.a...@mdh.se> wrote:
>> Det enda jag vill är att kunna skriva egna rekursiva
>> funktioner...
>
Fortfarande virrigt... Här så förstår jag faktiskt inte vad själva
rekursionen utför över huvud taget. Vad händer om man tar bort den
raden?
--
Dubb
Jan Erik Moström
<tor...@sm.luth.se> wrote:
> Dina exempel är förträffliga, men jag har ett litet klagomål på en
> kommentar i det andra programmet: "OBS detta är INGET BRA sätt att
> göra det i Java !!". Den speciella rekursiva algoritm du använder
> ("naive reverse") är förvisso ineffektiv, men detta har inget
> speciellt med Java att göra. Även i Java kan man ju i stället använda
> en effektivare rekursiv metod.
>
Det jag menar är Javas stränghantering (dvs String) som gör denna rutin
extremt slö. Jag hade läst om att man skulle undvika att använda String
(eller i alla fall skapa nya strängar) pga det var så långsamt men jag
trodde inte på det förrän jag körde detta program.
Sedan går det naturligtvis att göra själva rekursionen bättre (men det
var överkurs i denna del av kursen 8-)
jem
Torkel Franzen
> Det jag menar är Javas stränghantering (dvs String) som gör denna rutin
> extremt slö.
Jo, vid närmare betraktande har du helt rätt i att
strängkonkateneringsoperationen i Java gör hela angreppssättet
olämpligt.
Carl Nettelblad
> Fortfarande virrigt... Här så förstår jag faktiskt inte vad själva
> rekursionen utför över huvud taget. Vad händer om man tar bort den
> raden?
>
Tänk dig att du har följande talserie:
3 2 1
Vid första genomkörningen märker sort att a[0]>a[1], d.v.s. 3 större än 2.
Då har vi: 2 3 1
Vid nästa steg i for-slingan märker den att a[1]>a[2], d.v.s. 3 större än 1.
Då har vi 2 1 3.
Sedan är funktionen klar. Nästan. Den upptäckte att den bytte plats på några
värden, och att det därför inte är säkert att allt stämmer (vilket du också
ser här, 2 1 3 är ju inte korrekt sortering).
Därför anropar den sig själv.
Då upptäcker den att även denna gång är a[0] > a[1], i detta fall 2 större
än 1. Så den byter plats igen. Nästa stämmer, a[1] är inte större än a[2].
Resten stämmer, men i ett fall där det här inte var det första talet som
flyttades skulle vi kunna tänka oss att det listan fortfarande inte var
sorterad. Därför anropas (i detta fall helt i onödan) sort igen, och denna
gång går den bara igenom loopen, utan att göra något.
Inget flyttades, så den anropar inte sig själv (om den alltid gjorde det
skulle vi ju vara fast i en evighetsslinga).
Där slutar anrop 3.
Den går tillbaka till raden efter if-satsen i anrop 2, alltså }, och därmed
tillbaka till samma rad i anrop 1, och slutligen till main.
Du frågade också tidigare vad returvärde är. Det är det värde du skriver
efter return. Returvärdet för en funktion som beräknar sinus för ett tal är
just sinus för det talet, returvärdet för en funktion som tar reda på vilket
av två tal som är störst är det största talet (företrädesvis, naturligtvis
kan vi tänka oss att den returnerar true om det första talet är störst och
annars false, eller något helt annat).
I de flesta rekursionsfunktioner har man ett returvärde, men som du ser inte
i den här ovan. Där skickas data tillbaka genom att det är samma objekt som
används hela tiden, och inte en kopia av det, vilket är fallet andra
parametrar som standard. (Egentligen är det här inte objektet som skickas,
utan en KOPIA av en referens till objektet, som alltså pekar på samma
objekt)
/Carl
Alexander Backlund
> Vad jag inte förstår är att samma variabel kan ha flera olika värden,
> och hur 17 man ska veta VILKET värde man räknar med...
Det är inte samma variabel, bara samma namn på olika variabler. I alla
funktioner och procedurer kan du ha variabler med samma namn - utan att
de tar upp samma minnesutrymme - ens när de anropar andra funktioner som
använder variabler med samma namn.
Alexander Backlund
> Jo, jag har förstått nu att det skapas en ny instans. Vad jag däremot
> inte förstår är HUR det hela fungerar... det känns som man inte har
> full koll på något sett... Och jag förstår inte heller hur man ska
> tänka när man ska angripa ett problem på detta sett. Att lösa t.ex.
> mitt problem med att få alla kombinationer av en viss sträng löste jag
> efter lite grubbel med nästlade for-satser. Jag kan inte alls tänka
> hur jag skulle kunna lösa det med rekursion.
Du säger själv att du har omfattane kunskaper i logik och matematik. Då
föreslår jag att du provar att lära dig logikprogrammeringsspråket
Prolog, där problem ofta löses med hjälp av rekursion.
Jacob Andersen
news:66elcs0ed35oakhot...@4ax.com...
> Tack alla ni som försökt hjälpa mig förstå rekursiv programering!
> Trots allt så har jag faktiskt lärt mig något.
> Men jag är fortfarande ENORMT förrvirrad över det hela...
>
> Är det bara JAG som tycker 100 rader kod med med ett 10-tal nästlade
> for- och if-satser är enklare att följa och förstå en 10 raders
> rekursiv kod?
Njäej. Men så har jag programmerat i Scheme... Där det ända sättet som finns
att iterera är just genom rekursion. Efter det så är man ganska van att
tänka rekursivt :-) Nästlade for- och if-satser är bland det värsta jag vet.
Det är en fråga om vad man är van vid. Vissa typer algoritmer kan man
uttrycka så enormt mycket enklare med hjälp av rekursion - hade du löst
samma problem med iteration (vilket förstås alltid går) hade du helt enkelt
simulerat stackbeteendet som rekursionen ger upphov till.
> Grejen är ju den att jag verkligen VILL förstå. Jag blir så ENORMT
> förbannad på mig själv att jag inte fattar. Jag känner mig helt
> värdelös. Usch...
Det här _är_ inte det enklaste... På sätt och vis tror jag att du skulle
kunna förstå bättre om du förstod hur högnivåprogramkoden (C, Java etc) såg
ut efter den översatts till maskinkod. I maskinkodens värld finns inte
rekursion, och där ser man också hur variablerna sparas på stacken vid varje
nytt hopp till funktionen. Men att lära sig assembler är inte heller det
enklaste :-)
Rekursion är inte bara ett programmeringstekniskt knep. Det används inom den
rena matematiken också, förstås.
Jag funderade på om följande (C-) exempel kunde vara till någon hjälp. Här
har du vad man skulle kunna kalla indirekt rekursion:
int a(int nr)
{
/* stopp-villkor: vi vill stanna om nr överstiger ett visst värde */
if (nr > 10)
{
return nr;
}
/* annars ökar vi nr med ett */
nr = nr + 1;
/* sedan anropar vi b() */
nr = b(nr);
return nr;
}
int b(int nummer)
{
/* öka nummer med två */
nummer = nummer + 2;
/* och anropa sedan funktion a() */
nummer = a(nummer);
return nummer;
}
/* börja här */
void start_funktion()
{
int resultat = a(4)
printf("Det blev:%d", resultat);
}
(Jag har inte orkat läsa andras exempel, det kanske redan är någon som visat
på den här varianten.)
Alltid när man skriver rekursiva funktioner är det viktigt att tänka ut vad
man har för stopp-villkor. När ska funktionen/erna sluta anropa varandra? I
fallet ovanför kommer vi snurra runt mellan a() och b() tills villkoret i
a(), att nr > 10, faller ut. Sedan returnerar vi till start_funktion() och
skriver ut resultatet.
Fundera på hur funktionerna fungerar med olika invärden från
start_funktion(). Om värdet är mer än 10 redan från början? Om värdet är 9?
8? osv. Försök rita upp ett flödesschema, där du kan se hur parametern som
skickas vidare hela tiden ändras.
Sedan kan du också strunta i exakt hur rekursion fungerar tekniskt. Om du
ser varje funktion som en liten svart låda, som gör något för dig, och den
funkar, så är det egentligen ointressant exakt _hur_ den gör det. Det är så
himla mycket som ett högnivåspråk gör åt dig ändå, utan att du behöver bry
dig eller veta hur det går till.
/J
Jacob Andersen
news:9pIy4.1356$74.2...@newsc.telia.net...
>
> "Dubb" <du...@pzz.duh..pi> wrote in message
> news:66elcs0ed35oakhot...@4ax.com...
> > for- och if-satser är enklare att följa och förstå en 10 raders
> > rekursiv kod?
>
> underhållsperspektiv [klipp]
>Som många har sagt är rekursion aldrig den optimala
> lösningen
I termer av exekveringshastighet, nej. Men som du själv också noterar så
finns det andra kriterier på vad som är "bra" kod. I dag är det i de flesta
fall de andra kriterierna som överskuggar rena prestandakrav, dels för att
vi har så fanatiskt snabb hårdvara, dels för att det ofta handlar om
interaktiva program, där datorn ändå står och väntar på användaren 99.99% av
tiden...
Jag misstänker dessutom att om man skulle titta på vilka missar som görs
oftast i programkod, vad gäller dålig effektivitet, så kommer långsam
rekursion ganska långt ner på listan. Fast nu gissar jag bra. Någon som sett
någon dylik undersökning?
, då bland annat allt läggande på stacken faktiskt är lite långsamt
> (kanske särskilt i Java). Hur lång tid det "borde" ta att hitta dina
> kombinationer vet jag tyvärr inte.Om jag får tid över kan jag ju testa att
> skriva ett program själv och köra på min Celeron 466. Om min tid kommer
> under din visar det ju då att det finns någon fantastisk liten optimering
> som du har glömt.
De bästa optimeringarna som görs ligger snarare i problemdomänen än den rena
implementationsditton. Val av (abstrakt) algoritm är viktigare än den teknik
man använder för att implementera densamma.
/J
Alexander Backlund
>
> Tack alla ni som försökt hjälpa mig förstå rekursiv programering!
> Trots allt så har jag faktiskt lärt mig något.
> Men jag är fortfarande ENORMT förrvirrad över det hela...
>
> for- och if-satser är enklare att följa och förstå en 10 raders
> rekursiv kod?
>
> förbannad på mig själv att jag inte fattar. Jag känner mig helt
> värdelös. Usch...
Du säger att du är bra på matematik. Då vet du hur fibonacciserien är
definierad.
f1 = 1
f2 = 1
fn = fn-1 + fn-2
1, 1, 2, 3, 5, 8...
TÄnk dig nu att vi ska skriva ett program som beräknar det n:te
fibonaccitalet.
Vi vet vad de två första talen är, och vi vet att vi kan få talet genom
att multiplicera de två föregående fibonaccitalen med varandra.
Jag skriver den här funktionen i Pascal, vilket du bör förstå även om du
inte kan språket.
function Fibonacci (n : integer) : integer;
(* Denna funktion beräknar det n:te fibonaccitalet. *)
(* Variabeln n anger vilket fibonaccital som skall returneras. *)
begin
if (n < 3) then
Fibonacci := 1
else
Fibonacci := Fibonacci (n - 1) + Fibonacci (n - 2);
end; (* Fibonacci *)
Hur fungerar nu denna kod?
Antag att vi vill veta vilket det tredje fibonaccitalet är. Funktionen
Fibonacci anropas då i vårt program med n=3:
tal := Fibonacci (3);
Vad händer nu? Jo, variabeln n tilldelas värdet 3. Variabeln n är inte
mindre än 3. Därför är det värde som funktionen ska returnera summan av
de två föregående fibonaccitalen. Funktionen anropas då igen för att ge
värdet på de föregående fibonaccitalen, dvs. det n-1:te och det n-2:te
talet i serien. Variabeln n:s värde är 3. 3-1=2. Funktionen anropas
sålunda med argumentet 2. Observera nu att variabeln n i den funktion
som anropas inte är samma variabel som i den funktion som anropar den.
Värdet på n i den funktion vi nu har anropat är 2. 2 är mindre än 3.
Alltså returneras värdet 1. Vi hoppar alltså tillbaka till den
ursprungliga funktionen. Där anropar vi nu återigen funktionen för att
få reda på vilket det n-2:te fibonaccitalet är. n=3. 3-2=1. Funktionen
anropas således med värdet 1. Variabeln n får i det nya funktionsanropet
värdet 1. Eftersom 1 (vilket är det värde n har) är mindre än 3
returneras värdet 1. Vi hoppar alltså tillbaka till den ursprungliga
funktionen. Nu vet vi vad det n-1:te och det n-2:te talet i serien är.
Dessa tal adderas nu. 1+1=2. Således returnerar funktionen värdet 2, och
vi har fått svar på vilket det tredje fibonaccitalet är.
Dag Henriksson
Jacob Andersen wrote:
> "Carl Nettelblad" <cne...@hem.passagen.se> wrote in message
> news:9pIy4.1356$74.2...@newsc.telia.net...
> > Jag föredrar helt klart den rekursiva. Kort och koncist. Också ur ett
> > underhållsperspektiv [klipp]
> >Som många har sagt är rekursion aldrig den optimala
> > lösningen
>
> I termer av exekveringshastighet, nej. Men som du själv också noterar så
> finns det andra kriterier på vad som är "bra" kod. I dag är det i de flesta
> fall de andra kriterierna som överskuggar rena prestandakrav, dels för att
> vi har så fanatiskt snabb hårdvara, dels för att det ofta handlar om
> interaktiva program, där datorn ändå står och väntar på användaren 99.99% av
> tiden...
>
> Jag misstänker dessutom att om man skulle titta på vilka missar som görs
> oftast i programkod, vad gäller dålig effektivitet, så kommer långsam
> rekursion ganska långt ner på listan. Fast nu gissar jag bra. Någon som sett
> någon dylik undersökning?
Ett stort problem med rekusion är att det är svårt att avgöra för vilka
inparametrar en sådan funktion fungerar:
Exempel:
En funktion som summerar alla positiva heltal mellan a och 0 skulle kunna
skrivas så här:
int sum(int a) // a är ett positivt heltal
{
return a ? a+sum(a-1) : 0;
}
För vilka a "fungerar" funktionen?
Funktionen slutar naturligtvis att ge matematiskt rätt resultat om en int inte
kan representera summan,
men det är också stor chans att den falerar tidigare p g a att stacken tar slut.
Även om jag testar att funktionen fungerar i mitt program, på min plattform, med
de inparametrar jag är intressserad av
så kan förutsättningarna snabbt ändras så det inte längre fungrerar
// Modifierad rekursiv funktion
int sum(int a) // a är ett positivt heltal
{
char nonsens[10000];
return a ? a+sum(a-1) : 0;
}
Ops. Funktionen som förut fungerade för tal mellan 0 och 10000 fungerar nu bara
för tal mellan 0-112...
Skriver man istället funktionen utan rekursion:
int sum(int a) // a är ett positivt heltal
{
int sum = 0;
while (a) {
sum += a--;
}
return sum;
}
kan man vara ganska säker på att om den fungerar för t ex a = 6 fungerar den
även för a = 26 000 (om summan får plats i en int).
-- Dag Henriksson
Torkel Franzen
> TÄnk dig nu att vi ska skriva ett program som beräknar det n:te
> fibonaccitalet.
Ditt exempel är förträffligt eftersom det illustrerar hur
fantastiskt ineffektiv en rekursivt definierad procedur kan bli om vi
inte tänker efter vilken algoritm den implementerar.
Torkel Franzen
>Ett stort problem med rekusion är att det är svårt att avgöra för vilka
>inparametrar en sådan funktion fungerar:
Visst är det så att rekursionsdjupet har betydelse, men i vilket
sammanhang är detta faktiskt ett stort problem?
>Ops. Funktionen som förut fungerade för tal mellan 0 och 10000
>fungerar nu bara för tal mellan 0-112...
Här kan nämnas att detta speciella exempel bara gäller språk som skapar
arrayer på stacken.
>Skriver man istället funktionen utan rekursion:
Visst, sådana enkla operationer skrives med fördel iterativt.
Alexander Backlund
Ja, jag tycker att det fint illustrerar principen samtidigt som det
måste stå klart hur olämplig lösningen är i detta fall.
Dag Henriksson
Torkel Franzen wrote:
> Dag Henriksson <dag.hen...@quidsoft.se> writes:
>
> >Ett stort problem med rekusion är att det är svårt att avgöra för vilka
> >inparametrar en sådan funktion fungerar:
>
> Visst är det så att rekursionsdjupet har betydelse, men i vilket
> sammanhang är detta faktiskt ett stort problem?
Problemet är just att det inte är lätt förutsägbart för vilka inparametrar en
rekursiv funktion (där rekursionsdjupet beror av inparametern) fungerar.
(därmed inte sagt att det alltid är lätt för motsvarande icke rekursiva
funktion)
I vilka sammanhang det är ett problem?
Tja, i alla sammanhang funktionen används måste det väl vara ett problem att
inte veta om funktionen fungerar eller inte? Visst kan man i många språk
hantera felet (t ex visa ett felmeddelande), men det löser ju inte problemet.
Även om funktionen är testat att den fungerar inom intevallet a till b är det
ju inte säkert att detta gäller då funktionen anropas nästa gång. Nästa gång
kanske det inte finns lika mycket utrymme på stacken.
Problem med att resurser kan ta slut (heapminne, stackminne,
operativsystemspecifika resurser mm) har man i och för sig alltid, men
förutsättningar för att göra av med "onödigt" mycket resurser finns helt
klart vid rekursion, vilket jag försökte visa med mitt exempel.
Jag menar dock inte att rekursion är något man aldrig bör använda sig av. I
vissa sammanhang "äter" kanske en icke rekursiv version av funktionen, lika
stora resurser, eller kanske t o m mer.
-- Dag Henriksson
Torkel Franzen
> Ja, jag tycker att det fint illustrerar principen samtidigt som det
> måste stå klart hur olämplig lösningen är i detta fall.
En rekursiv metod för beräkning av fibonacci är inte i sig olämplig,
bara den speciella algoritm du valde.
Torkel Franzen
>I vilka sammanhang det är ett problem?
>Tja, i alla sammanhang funktionen används måste det väl vara ett problem att
>inte veta om funktionen fungerar eller inte? Visst kan man i många språk
>hantera felet (t ex visa ett felmeddelande), men det löser ju inte
>problemet.
Nu tänkte jag på faktiska, konkreta sammanhang, alltså exempel
på program som man inte kunnat skriva rekursivt eftersom de inte
fungerade tillfredsställande.
Alexander Backlund
Ja, det var det jag menade. Algoritmen valdes för att vara enkel att
begripa, inte för att vara bra på något annat vis.
aXEmAN
programmering om man inte vet vad ett returvärde är. En funtion som
int EnFunktion(int x) {
x++;
return x;
}
tar en integer variabel till funktionen, plussar på x med ett och
skickar sedan tillbaka ett värde till den kallande funktionen. Så om
det skulle se ut så här
int main()
{
int MinVariabel = 5;
int ReturVariabel;
ReturVariabel = EnFunktion(Minvaribel);
return 0;
}
innebär detta att man deklarerar två variabler (MinVariabel och
ReturVariabel).
Den ena variabelns värde skickar man till funktionen EnFunktion, där
värdet plussas på med ett och sedan skickar man tillbaka det nya
värdet (som i det här fallet är 6) från EnFuntion till main().
I main() tilldelas ReturVariabel värdet av "x".
Dubb
Sätta mig in i ett nytt programeringsspråk är nog inget för mig. Jag
började med Qbasic, sen Visual Basic, nu är det Java och sen ska jag
lära mig C++... Om jag ska kolla på Prolog får det bli senare...
--
Dubb
Dubb
>Hmmm... Det kan nog vara ganska svårt att förstå rekursiv
>programmering om man inte vet vad ett returvärde är.
Ok, jag vet väl vad retuvärde är för något. Man jag var lite vimsig
när jag läste det. Och fick för mig att det var nån slags
minnesaddress eller nått...
--
Dubb
Dubb
Ok. Men funkar det inte lika bra att bara låta loopen börja om från
början om den har utfört en swap?
>Du frågade också tidigare vad returvärde är. Det är det värde du skriver
>efter return. Returvärdet för en funktion som beräknar sinus för ett tal är
>just sinus för det talet, returvärdet för en funktion som tar reda på vilket
>av två tal som är störst är det största talet (företrädesvis, naturligtvis
>kan vi tänka oss att den returnerar true om det första talet är störst och
>annars false, eller något helt annat).
Jo, men som sagt så var jag lite vimsig när jag sa det. Jag VET vad
ett returvärde är. :)
--
Dubb
Dubb
<jand...@FOOsoftronic.se> wrote:
>"Dubb" <du...@pzz.duh..pi> wrote in message
>news:66elcs0ed35oakhot...@4ax.com...
>> Tack alla ni som försökt hjälpa mig förstå rekursiv programering!
>> Trots allt så har jag faktiskt lärt mig något.
>> Men jag är fortfarande ENORMT förrvirrad över det hela...
>>
>> Är det bara JAG som tycker 100 rader kod med med ett 10-tal nästlade
>> for- och if-satser är enklare att följa och förstå en 10 raders
>> rekursiv kod?
>
>Njäej. Men så har jag programmerat i Scheme... Där det ända sättet som finns
>att iterera är just genom rekursion. Efter det så är man ganska van att
>tänka rekursivt :-) Nästlade for- och if-satser är bland det värsta jag vet.
>
>Det är en fråga om vad man är van vid. Vissa typer algoritmer kan man
>uttrycka så enormt mycket enklare med hjälp av rekursion - hade du löst
>samma problem med iteration (vilket förstås alltid går) hade du helt enkelt
>simulerat stackbeteendet som rekursionen ger upphov till.
>
>> Grejen är ju den att jag verkligen VILL förstå. Jag blir så ENORMT
>> förbannad på mig själv att jag inte fattar. Jag känner mig helt
>> värdelös. Usch...
>
Jag har redan gett upp på den punkten. Att förstå exakt _hur_ det
fungerar... Men jag förstår fortfarande inte hur man ska tänka när man
ska skriva rekursiv kod...
--
Dubb
Fredrik Roubert
Dubb <du...@pzz.duh..pi> wrote:
> Men jag förstår fortfarande inte hur man ska tänka när man ska skriva
> rekursiv kod...
Det går nästan alltid utmärkt att tänka precis som man gör när man
skriver rekursiva formler i matematiken.
Hälsningar // Fredrik Roubert
--
rou...@df.lth.se · +46 46 188127
d9...@efd.lth.se · Möllevångsvägen 6c
http://www.efd.lth.se/~d95fr/ · SE-222 40 Lund
Dubb
<alex...@ida.his.se> wrote:
>Dubb wrote:
>>
>> Tack alla ni som försökt hjälpa mig förstå rekursiv programering!
>> Trots allt så har jag faktiskt lärt mig något.
>> Men jag är fortfarande ENORMT förrvirrad över det hela...
>>
>> Är det bara JAG som tycker 100 rader kod med med ett 10-tal nästlade
>> for- och if-satser är enklare att följa och förstå en 10 raders
>> rekursiv kod?
>>
>> Grejen är ju den att jag verkligen VILL förstå. Jag blir så ENORMT
>> förbannad på mig själv att jag inte fattar. Jag känner mig helt
>> värdelös. Usch...
>
>Du säger att du är bra på matematik. Då vet du hur fibonacciserien är
>definierad.
>f1 = 1
>f2 = 1
>fn = fn-1 + fn-2
>
>1, 1, 2, 3, 5, 8...
Den slutsatsen kan du väl inte dra? Jag sa inget om min ålder. Jag
anser mig bra på matematik, jämfört med andra i min åldersgrupp...
Fibonacciserien har jag aldrig hört talas om. Dock så vet jag nu vad
det är. :)
>
>TÄnk dig nu att vi ska skriva ett program som beräknar det n:te
>fibonaccitalet.
>
Ok. Nu tror jag faktiskt jag börjar förstå det här. :)
Jag skrev programmet i java, och det fungerade och jag förstår nu HUR
det fungerar (rent matematiskt alltså). Tack!
Nu återstår bara att kunna använda mig av rekursion vid lite svårare
exempel. Och inte bara när det handlar om beräkningar...
--
Dubb
Dubb
På vilket sett är den dålig? Och hur kan man se det?
--
Dubb
Carl Nettelblad
"Dubb" <du...@pzz.duh..pi> wrote in message
Den gör två anrop av sig själv. Om du tänker på vad varje anrop sedan gör
kommer du nog på att fibonacci(n-1) anropar fibonacci(n-2) och
fibonacci(n-3). Sedan anropar fibonacci(n-2) fibonacci(n-3) och
fibonacci(n-4). fibonacci(n-2) anropas alltå tre gånger... Och det värsta är
att för varje sådant anrop så breder ett helt nytt "träd" ut sig (varje
anrop av -2 anropar ju -3 och -4, som sedan anropar vidare). Exponentiell
prestandasänkning när den är som värst (och onödigast).
Carl Nettelblad
> >>
> >> Tack alla ni som försökt hjälpa mig förstå rekursiv programering!
> >> Trots allt så har jag faktiskt lärt mig något.
> >> Men jag är fortfarande ENORMT förrvirrad över det hela...
> >>
> >> Är det bara JAG som tycker 100 rader kod med med ett 10-tal nästlade
> >> for- och if-satser är enklare att följa och förstå en 10 raders
> >> rekursiv kod?
> >>
> >> Grejen är ju den att jag verkligen VILL förstå. Jag blir så ENORMT
> >> förbannad på mig själv att jag inte fattar. Jag känner mig helt
> >> värdelös. Usch...
> >
> >Du säger att du är bra på matematik. Då vet du hur fibonacciserien är
> >definierad.
> >f1 = 1
> >f2 = 1
> >fn = fn-1 + fn-2
> >
> >1, 1, 2, 3, 5, 8...
>
> Den slutsatsen kan du väl inte dra? Jag sa inget om min ålder. Jag
> anser mig bra på matematik, jämfört med andra i min åldersgrupp...
> Fibonacciserien har jag aldrig hört talas om. Dock så vet jag nu vad
> det är. :)
Jag måste till ditt försvar erkänna att jag inte kände till den tidigare
(eller i varje fall inte kom ihåg den). Å andra sidan är jag SÄKER på att
den inte har tagits upp i den "matematikundervisning" (observera
citationstecknen) jag har fått.
/Carl
Dag Henriksson
Nej, några exempel på program som bevisligen inte går att skriva rekursivt har jag
inte och har aldrig hävdat att det finns.
Vad jag har hävdat är att det kan vara svårare att avgöra för vilka inparametrar
en rekursiv funktion "fungerar" än
motsvarande icke rekursiva funktion och jag har givit ett exempel på en sådan.
Här kommer det igen:
// Fungerar kanske inte för alla tal där summan rymms i en int
int sum(int a) // a är ett positivt heltal
{
return a ? a+sum(a-1) : 0;
}
// Fungerar troligtvis för alla tal där summan rymms i en int
// om den visar sig fungera i något fall. (stackåtgången ökar antagligen inte vid
större värden på a)
int sum(int a) // a är ett positivt heltal
{
int sum = 0;
while (a) {
sum += a--;
}
return sum;
}
Jag har också hävdat att rekursiva funktioner i vissa sammanhang gör av med
onödigt mycket resurser i form av t ex stackminne:
Eftersom fibonacci har varit på tapeten (och du har hävdat att "En rekursiv metod
för beräkning av fibonacci är inte i sig olämplig") så kan vi ta ett sådant
exempel:
// Här har vi en icke rekursiv variant
unsigned long fibonacci(unsigned long n)
{
unsigned long fa = 1;
unsigned long fb = 1;
unsigned long fi = 1;
for (unsigned long i = 2 ; i < n ; i++) {
fi = fa + fb;
fa = fb;
fb = fi;
}
return fi;
}
För mig fungerade denna för att räkna ut fibonacci(1) till fibonacci(47) innan
unsigned long svämmade över.
Jag tror att motsvarande rekursiva variant gör av med betydligt mer stackutrymme
än denna, och jag har svårt att se att den skulle kunna vara bättre på något annat
sätt heller, varför jag anser att du har fel när du säger att "en rekursiv metod
för beräkning av fibonacci är inte i sig olämplig".
-- Dag Henriksson