Hva er rekursjon og når skal jeg bruke det?

stemmer
121

Ett av temaene som synes å komme opp regelmessig på e-postlister og nettdiskusjoner er verdien (eller mangel på sådan) gjør en datavitenskap grad. Et argument som synes å komme opp igjen og igjen for den negative partiet er at de har blitt koding i et visst antall år, og de har aldri brukt rekursjon.

Så spørsmålet er:

  1. Hva er rekursjon?
  2. Når vil jeg bruke rekursjon?
  3. Hvorfor ikke folk bruker rekursjon?
Publisert på 06/08/2008 klokken 02:29
kilden bruker
På andre språk...                            


40 svar

stemmer
86

Det finnes en rekke gode forklaringer på rekursjon i denne tråden, er dette svaret om hvorfor du ikke bør bruke det på de fleste språk. * I de fleste store avgjørende språk implementasjoner (dvs. alle store implementering av C, C ++, Basic, Python , Ruby, Java og C #) iterasjon er langt å foretrekke fremfor rekursjon.

For å se hvorfor, gå gjennom trinnene som de ovennevnte språk bruker å kalle en funksjon:

  1. plass er skåret ut på stakken for funksjonens argumenter og lokale variabler
  2. funksjonens argumenter blir kopiert inn i denne nye plassen
  3. kontroll hopper til funksjonen
  4. funksjonens kode kjøres
  5. funksjonen resultat kopieres til en returverdi
  6. stabelen spoles tilbake til sin tidligere stilling
  7. kontroll hopper tilbake til der funksjonen ble kalt

Gjøre alle disse trinnene tar tid, som regel litt mer enn det tar å iterere gjennom en loop. Imidlertid er det virkelige problemet i trinn 1. Når mange programmer starte, de tildele en enkelt del av minne for sin stack, og når de går ut av minnet (ofte, men ikke alltid på grunn av rekursjon), krasjer programmet på grunn av en stack overflow .

Så i disse språkene rekursjon er tregere, og det gjør deg sårbar for krasj. Det er fortsatt noen argumenter for å bruke det selv. Generelt kode skrevet rekursivt er kortere og litt mer elegant, når du vet hvordan du skal lese den.

Det er en teknikk som språk implementers kan bruke kalles halen samtale optimalisering som kan eliminere noen klasser av stakkoverflyt. Sett konsist: Hvis en funksjon retur uttrykk er rett og slett et resultat av et funksjonskall, så du trenger ikke å legge til et nytt nivå på stakken, kan du bruke den gjeldende for funksjonen blir kalt. Dessverre, noen tvingende språk-implementeringer har hale-call optimalisering innebygd.

* Jeg elsker rekursjon. Min favoritt statisk språket ikke bruker løkker i det hele tatt, er rekursjon den eneste måten å gjøre noe flere ganger. Jeg tror ikke at rekursjon er generelt en god idé på språk som ikke er innstilt for det.

** Forresten Mario, typisk navn for ArrangeString funksjonen er "bli", og jeg vil bli overrasket hvis språket du ønsker ikke allerede har en implementering av det.

Svarte 06/08/2008 kl. 05:09
kilden bruker

stemmer
63

Enkel norsk eksempel på rekursjon.

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.
Svarte 04/05/2010 kl. 16:38
kilden bruker

stemmer
49

I den mest grunnleggende informatikk forstand er rekursjon en funksjon som kaller seg. Si du har en lenket liste struktur:

struct Node {
    Node* next;
};

Og du ønsker å finne ut hvor lenge en lenket liste er at du kan gjøre dette med rekursjon:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(Dette kan selvsagt utføres med et for løkke også, men er nyttig som en illustrasjon av konseptet)

Svarte 04/05/2010 kl. 11:25
kilden bruker

stemmer
46

Når et funksjonskall seg selv, noe som skaper en sløyfe, så er det rekursjon. Som med alt det gode bruksområder og dårlige bruksområder for rekursjon.

Den mest enkelt eksempel er halen rekursjon der den aller siste linjen i funksjonen er en oppfordring til seg selv:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

Men dette er en halt, nesten meningsløst eksempel fordi det kan lett bli erstattet av mer effektive iterasjon. Tross alt, lider rekursjon fra funksjonskallet overhead, som i eksemplet ovenfor, kan være betydelige i forhold til driften inne selve funksjonen.

Så hele grunnen til å gjøre rekursjon i stedet for gjentakelse bør være å dra nytte av kallstakken til å gjøre noen smarte ting. For eksempel, hvis man kalle en funksjon flere ganger med forskjellige parametere i den samme sløyfe da det er en måte å oppnå forgrening . Et klassisk eksempel er Sierpinski trekant .

skriv bildebeskrivelse her

Du kan tegne en av dem veldig enkelt med rekursjon, hvor samtalen stabelen filialer i 3 retninger:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

Hvis du prøver å gjøre det samme med gjentakelse jeg tror du vil finne det tar mye mer kode for å oppnå.

Andre vanlige bruksmåter kan omfatte traversering hierarkier, f.eks nettstedet crawlere, katalog sammenligninger etc.

Konklusjon

I praksis gjør rekursjon mest fornuftig når du trenger iterativ forgrening.

Svarte 04/05/2010 kl. 13:33
kilden bruker

stemmer
28

Rekursjon er en metode for å løse problemer basert på splitt og hersk mentalitet. Den grunnleggende ideen er at du tar det opprinnelige problemet og dele den opp i mindre (lettere løses) tilfeller av seg selv, løse de mindre forekomster (vanligvis ved å bruke samme algoritme igjen) og deretter montere dem inn i den endelige løsningen.

Kanonisk eksempel er en rutine for å frembringe fakultet av n. Den fakultet av n blir beregnet ved å multiplisere alle tallene mellom 1 og n. En iterativ løsning i C # ser slik ut:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

Det er ikke noe overraskende om iterativ løsning, og det bør være fornuftig å noen kjent med C #.

Den rekursive løsning blir funnet ved å erkjenne at den n-te Factorial er n * Fact (n-1). Eller sagt på en annen måte, hvis du vet hva en bestemt Fakultet nummer du kan beregne den neste. Her er den rekursive løsningen i C #:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

Den første delen av denne funksjonen er kjent som en Base case (eller noen ganger Guard punkt) og er det som hindrer algoritmen fra å kjøre for alltid. Den returnerer bare verdien 1 når funksjonen kalles med en verdi på 1 eller mindre. Den andre delen er mer interessant og er kjent som Rekursiv trinn . Her kaller vi den samme metode med en noe modifisert parameter (vi decrement den ved 1) og deretter multiplisere resultatet med vår versjon av n.

Når først oppdaget dette kan være litt forvirrende, så det er lærerikt å undersøke hvordan det fungerer når løp. Tenk deg at vi kaller FactRec (5). Vi går inn i rutinen, blir ikke plukket opp av base case og så ender vi opp som dette:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

Hvis vi gå inn igjen i metoden med parameteren fire vi igjen ikke stoppet av vakten klausulen og slik at vi ender opp på:

// In FactRec(4)
return 4 * FactRec(3);

Hvis vi erstatte denne returverdien til returverdien ovenfor får vi

// In FactRec(5)
return 5 * (4 * FactRec(3));

Dette bør gi deg en anelse om hvordan den endelige løsningen er kommet på så vil vi raskt spore og vise hvert trinn på vei ned:

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

Det endelige substitusjon skjer når basen saken er utløst. På dette punkt har vi en enkel algrebraic formel for å løse noe som tilsvarer direkte til definisjonen av fakulteter i den første plass.

Det er lærerikt å merke seg at hver samtale til metoden resulterer i enten en base case blir utløst eller et kall til samme metode der parametrene er nærmere en base case (ofte kalt en rekursive kall). Hvis dette ikke er tilfelle så metoden vil kjøre for alltid.

Svarte 06/08/2008 kl. 02:54
kilden bruker

stemmer
12

Rekursjon er å løse et problem med en funksjon som kaller seg. Et godt eksempel på dette er et fakultet funksjon. Fakultet er et matematisk problem der fakultetet av 5, for eksempel, er 5 * 4 * 3 * 2 * 1. Denne funksjonen løser dette i C # for positive heltall (ikke testet - det kan være en feil).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}
Svarte 04/05/2010 kl. 11:29
kilden bruker

stemmer
9

Vurder en gammel, velkjent problem :

I matematikk, den største felles divisor (gcd) ... av to eller flere ikke-null heltall, er den største positive heltall som deler tallene uten en rest.

Definisjonen av gcd er overraskende enkel:

gcd definisjon

hvor mod er modulo operatør (dvs. resten etter heltallsdeling).

I engelsk, sier denne definisjonen største felles divisor av et hvilket som helst tall og null er det nummeret, og den største felles divisor av to tall m og n er den største felles divisor for n , og resten etter deling m av n .

Hvis du ønsker å vite hvorfor dette fungerer, se Wikipedia-artikkel på Euklids algoritme .

La oss å beregne gcd (10, 8) i form av et eksempel. Hvert trinn er lik den like før det:

  1. gcd (10, 8)
  2. gcd (10, 10 mod 8)
  3. gcd (8, 2)
  4. gcd (8, 8 mod 2)
  5. gcd (2, 0)
  6. 2

I det første trinn 8 ikke er lik null, slik at den andre delen av den definisjon gjelder. 10 mod 8 = 2, ettersom 8 går over i 10 en gang med en rest på 2. I trinn 3, gjelder den andre del igjen, men denne gangen 8 mod 2 = 0 fordi 2 dividerer 8 uten at noen rest. Ved trinn 5, den andre argumentet er 0, så svaret er to.

La du merke til at gcd vises på både venstre og høyre side av likhetstegnet? En matematiker vil si denne definisjonen er rekursiv fordi uttrykket du definerer gjentar seg inne i sin definisjon.

Rekursive definisjoner tendens til å være elegant. For eksempel, er en rekursiv definisjon for summen av en liste

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

hvor header det første element i en liste og tailer resten av listen. Merk at sumgjentar seg inne i sin definisjon på slutten.

Kanskje du foretrekker den høyeste verdien i en liste i stedet:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

Du kan definere multiplikasjon av ikke-negative heltall rekursivt å slå den inn i en rekke tillegg:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

Hvis det litt om trans multiplikasjon i en serie av tilskuddene ikke gir mening, prøv å utvide noen enkle eksempler for å se hvordan det fungerer.

Flettesortering har en nydelig rekursiv definisjon:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

Rekursive definisjoner er alle rundt hvis du vet hva du skal se etter. Legg merke til hvordan alle disse definisjonene har meget enkle basis tilfeller, for eksempel , gcd (m, 0) = m. Den rekursive tilfeller spikke bort på problemet å komme ned til enkle svar.

Med denne forståelsen, kan du nå sette pris på de andre algoritmene i Wikipedias artikkel om rekursjon !

Svarte 04/05/2010 kl. 13:58
kilden bruker

stemmer
9

Rekursjon refererer til en fremgangsmåte som løser et problem ved å løse en mindre versjon av problemet, og deretter ved hjelp av det resultat pluss noen annen beregning for å formulere svaret på det opprinnelige problem. Ofte ganger, i ferd med å løse den mindre versjonen, metoden vil løse en enda mindre versjon av problemet, og så videre, helt til den når en "base case" som er trivielt å løse.

For eksempel, for å beregne en faktoriell for nummer X, kan man representere det som X times the factorial of X-1. Dermed Metoden "rekursivt" finne fakultetet av X-1, og deretter multipliserer hva det kom av Xå gi et endelig svar. Selvfølgelig, for å finne fakultetet av X-1, vil det først beregne fakultetet av X-2, og så videre. Basen tilfellet ville være når Xer 0 eller 1, og da den vet å komme tilbake 1siden 0! = 1! = 1.

Svarte 04/05/2010 kl. 11:26
kilden bruker

stemmer
9
  1. En funksjon som kaller seg
  2. Når en funksjon kan være (lett) dekomponeres i en enkel operasjon i tillegg til den samme funksjon på en mindre del av problemet. Jeg må si, heller, at dette gjør den til en god kandidat for rekursjon.
  3. De gjør!

Den kanoniske eksempel er fakultetet som ser slik ut:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

Generelt er rekursjon ikke nødvendigvis rask (funksjonskall overhead tendens til å være høy fordi rekursive funksjoner tendens til å være små, se ovenfor) og kan lide av noen problemer (stack overflow anyone?). Noen sier de har en tendens til å være vanskelig å få 'rett' i ikke-trivielle saker, men jeg har egentlig ikke kjøpe inn det. I noen situasjoner, gjør rekursjon mest fornuftig, og er den mest elegante og klar måte å skrive en bestemt funksjon. Det bør bemerkes at noen språk favorisere rekursive løsninger og optimalisere dem mye mer (LISP kommer til hjernen).

Svarte 06/08/2008 kl. 02:35
kilden bruker

stemmer
7

En rekursiv funksjon er en som kaller seg. Den vanligste grunnen til at jeg har funnet til å bruke den krysser en trestruktur. For eksempel, hvis jeg har en Treeview med boksene (tror installasjon av et nytt program, "velge funksjoner som skal installeres" side), jeg vil kanskje en "check all" -knappen som ville være noe sånt som dette (pseudokode):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

Så du kan se at checkRecursively først sjekker node som den er passert, så kaller seg for hver av at node barn.

Du trenger ikke å være litt forsiktig med rekursjon. Hvis du kommer inn i en uendelig rekursiv loop, vil du få en Stack Overflow unntak :)

Jeg kan ikke tenke meg en grunn til at folk ikke skal bruke det, når det passer. Det er nyttig i enkelte tilfeller, og ikke i andre.

Jeg tror at fordi det er en interessant teknikk, noen programmerere kanskje ende opp med å bruke det oftere enn de burde, uten skikkelig begrunnelse. Dette har gitt rekursjon et dårlig navn i enkelte kretser.

Svarte 06/08/2008 kl. 02:44
kilden bruker

stemmer
5

Rekursjon er et uttrykk direkte eller indirekte å registrere seg.

Tenk rekursivt akronym som et enkelt eksempel:

  • GNU står for GNU er ikke Unix
  • PHP står for PHP: Hypertext Preprocessor
  • YAML står for YAML ikke Markup Language
  • WINE står for vin er ikke en Emulator
  • VISA står for Visa International service Association

Flere eksempler på Wikipedia

Svarte 04/05/2010 kl. 11:56
kilden bruker

stemmer
5

Her er et enkelt eksempel: hvor mange elementer i et sett. (Det finnes bedre måter å telle ting, men dette er en fin enkel rekursiv eksempel.)

Først må vi to regler:

  1. hvis settet er tom, antall elementer i settet er null (duh!).
  2. hvis settet ikke er tom, er tellingen en pluss antall elementer i settet etter ett element er fjernet.

Anta at du har et sett som dette: [xxx]. La oss telle hvor mange elementer det er.

  1. settet er [xxx] som ikke er tom, så vi bruke regelen 2. antall elementer er en pluss antall elementer i [xx] (dvs. vi fjernet et element).
  2. settet er [xx], så vi bruke regel to igjen: en + antall elementer i [x].
  3. settet er [x], som fortsatt passer regel to: en + antall elementer i [].
  4. Nå settet er [], som matcher regel 1: tellingen er null!
  5. Nå som vi vet svaret i trinn 4 (0), kan vi løse trinn 3 (1 + 0)
  6. På samme måte, nå som vi vet svaret i trinn 3 (1), kan vi løse trinn 2 (1 + 1)
  7. Og til slutt nå som vi vet svaret i trinn 2 (2), kan vi løse trinn 1 (1 + 2) og få antall elementer i [xxx], som er 3. Hurra!

Vi kan representere dette som:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

Når du søker en rekursiv løsning, du vanligvis har minst 2 regler:

  • grunnlag, enkel sak som sier hva som skjer når du har "brukt opp" alle dine data. Dette er vanligvis en variant av "hvis du er ute av data til prosessen, er svaret X"
  • den rekursive regelen, som sier hva som skjer hvis du fortsatt har data. Dette er vanligvis en slags regel som sier "gjøre noe for å gjøre dataene satt mindre, og på nytt reglene til de mindre datasettet."

Hvis vi oversette ovenfor for å pseudo, får vi:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

Det er mye mer nyttige eksempler (traversering et tre, for eksempel) som jeg er sikker på at andre mennesker vil dekke.

Svarte 06/08/2008 kl. 03:12
kilden bruker

stemmer
5

Rekursjon fungerer best med det jeg liker å kalle "fraktal problemer", der du arbeider med en stor ting som er laget av mindre versjoner av at store ting, som hver er en enda mindre versjon av den store tingen, og så videre. Hvis du noen gang har å krysse eller søke gjennom noe sånt som et tre eller nestede identiske strukturer, har du et problem som kan være en god kandidat for rekursjon.

Folk unngå rekursjon for en rekke årsaker:

  1. De fleste (meg selv inkludert) kuttet sin programmering tenner på prosessuelle eller objektorientert programmering i motsetning til funksjonell programmering. Til slike folk, iterativ tilnærming (typisk ved hjelp av løkker) føles mer naturlig.

  2. De av oss som kutte våre programmerings tenner på prosessuelle eller objektorientert programmering har ofte fått beskjed om å unngå rekursjon fordi det er feil utsatt.

  3. Vi er ofte fortalt at rekursjon er treg. Ringer og retur fra en rutine gjentatte ganger innebærer mye stabel presser og dukker, som er tregere enn looping. Jeg tror noen språk håndtere dette bedre enn andre, og disse språkene er mest sannsynlig ikke de hvor det dominerende paradigmet er prosessuelle eller objektorientert.

  4. For minst et par programmeringsspråk jeg har brukt, husker jeg hørte anbefalinger om ikke å bruke rekursjon hvis det blir utover en viss dybde fordi stack er ikke så dypt.

Svarte 06/08/2008 kl. 03:12
kilden bruker

stemmer
4

1.) En fremgangsmåte er rekursivt om den kan kalle seg; enten direkte:

void f() {
   ... f() ... 
}

eller indirekte:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) Ved å bruke rekursjon

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) Folk bruker rekursjon bare når det er veldig komplisert å skrive iterativ kode. For eksempel, tre traversering teknikker som forhåndsbestilling, Postorder kan gjøres både iterative og rekursive. Men vanligvis bruker vi rekursive på grunn av sin enkelhet.

Svarte 11/03/2014 kl. 09:47
kilden bruker

stemmer
4

En rekursiv uttalelsen er en der du definerer prosessen med hva de skal gjøre som en kombinasjon av inngangene og hva du allerede har gjort.

For eksempel ta fakultet:

factorial(6) = 6*5*4*3*2*1

Men det er lett å se fakultetet (6) også er:

6 * factorial(5) = 6*(5*4*3*2*1).

Så generelt:

factorial(n) = n*factorial(n-1)

Selvfølgelig er det vanskelig ting om rekursjon at hvis du ønsker å definere ting i forhold til hva du allerede har gjort, det må være et sted å begynne.

I dette eksempelet vi bare gjøre en spesiell sak ved å definere fakultet (1) = 1.

Nå ser vi det fra bunnen opp:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Siden vi definert fakultet (1) = 1, kommer vi til "bunnen".

Generelt rekursive prosedyrer har to deler:

1) Det rekursive delen, som definerer noen prosedyre i form av nye innganger kombinert med det du har "allerede gjort" via samme prosedyre. (ie factorial(n) = n*factorial(n-1))

2) En basisdel, noe som sørger for at prosessen ikke gjenta for alltid ved å gi den et sted å starte (ie factorial(1) = 1)

Det kan være litt forvirrende å få hodet rundt på første, men bare se på en haug med eksempler, og det bør alle komme sammen. Hvis du ønsker en dypere forståelse av begrepet, studere matematiske induksjon. Vær også oppmerksom på at enkelte språk optimalisere for rekursive samtaler mens andre ikke gjør det. Det er ganske lett å lage sinnsykt treg rekursive funksjoner hvis du ikke er forsiktig, men det finnes også teknikker for å gjøre dem performant i de fleste tilfeller.

Håper dette hjelper...

Svarte 04/05/2010 kl. 13:30
kilden bruker

stemmer
4

I like denne definisjonen:
I rekursjon, en rutine løser en liten del av et problem i seg selv, deler problemet i mindre biter, og deretter kaller seg å løse hver av de mindre stykker.

Jeg liker også Steve McConnells diskusjon av rekursjon i Code Complete hvor han kritiserer de eksemplene som brukes i Computer Science bøker om Rekursjon.

Ikke bruk rekursjon for fakultetene eller Fibonacci-tallene

Et problem med datavitenskap lærebøker er at de presenterer dumme eksempler på rekursjon. Typiske eksempler er å beregne en faktoriell eller beregning av en Fibonacci sekvens. Rekursjon er et kraftig verktøy, og det er veldig dumt å bruke det i noen av disse tilfellene. Hvis en programmerer som jobbet for meg brukt rekursjon til å beregne et fakultet, vil jeg ansette noen andre.

Jeg trodde dette var en veldig interessant poeng å heve og kan være en grunn til at rekursjon blir ofte misforstått.

EDIT: Dette var ikke en grave på Dav svar - jeg hadde ikke sett at svaret når jeg postet dette

Svarte 04/05/2010 kl. 11:29
kilden bruker

stemmer
3

Et eksempel: en rekursiv definisjon av en trapp er: En trapp består av: - et enkelt trinn og en trapp (rekursjon) - eller bare et enkelt trinn (terminering)

Svarte 04/05/2010 kl. 13:34
kilden bruker

stemmer
3

Vel, det er en ganske grei definisjon du har. Og wikipedia har en god definisjon også. Så jeg vil legge til en annen (sannsynligvis verre) definisjon for deg.

Når folk se "rekursjon", de er som regel snakk om en funksjon de har skrevet som kaller seg gjentatte ganger til den er ferdig med sitt arbeid. Rekursjon kan være nyttig når man traverserer hierarkier i datastrukturer.

Svarte 04/05/2010 kl. 11:27
kilden bruker

stemmer
3

Å recurse på et løst problem: ikke gjør noe, er du ferdig.
Å recurse på en åpen problem: gjøre det neste trinnet, deretter recurse på resten.

Svarte 06/08/2008 kl. 03:32
kilden bruker

stemmer
2

Dette er en gammel spørsmålet, men jeg ønsker å legge til et svar fra logistisk synspunkt (dvs. ikke fra algoritmen korrekthet synspunkt eller ytelse synspunkt).

Jeg bruker Java for arbeid, og Java ikke støtter nestet funksjon. Som sådan, hvis jeg ønsker å gjøre rekursjon, kanskje jeg må definere en ekstern funksjon (som bare eksisterer fordi min kode støter mot Java byråkratisk regel), eller jeg må kanskje refactor koden helt (som jeg virkelig hater å gjøre).

Således, jeg ofte unngå rekursjon, og bruk stabel drift i stedet, fordi rekursjon i seg selv er i det vesentlige en stabel operasjon.

Svarte 30/08/2014 kl. 10:09
kilden bruker

stemmer
2

En rekursiv funksjon er en funksjon som inneholder en oppfordring til seg selv. En rekursiv struct er en struct som inneholder en forekomst av seg selv. Du kan kombinere de to som en rekursiv klasse. Den viktigste del av en rekursiv element er at det inneholder en forekomst / ring av seg selv.

Tenk to speil mot hverandre. Vi har sett ryddig uendelig effekt de gjør. Hver refleksjon er et eksempel på et speil, som er inneholdt i et annet tilfelle hvor et speil, etc. speil som inneholder en refleksjon av i seg selv er rekursjon.

En binært søketre er en god programmering eksempel på rekursjon. Strukturen er rekursiv med hvert knutepunkt inneholder 2 forekomster av en node. Funksjoner for å jobbe på et binært søketre er også rekursiv.

Svarte 04/05/2010 kl. 16:46
kilden bruker

stemmer
2

I vanlig engelsk: Anta at du kan gjøre 3 ting:

  1. Ta en eple
  2. Skriv ned regnskap med
  3. Count regnskap med

Du har mye epler foran deg på et bord, og du vil vite hvor mange epler det er.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

Prosessen med å gjenta det samme til du er ferdig kalles rekursjon.

Jeg håper dette er "vanlig engelsk" svaret du er ute etter!

Svarte 04/05/2010 kl. 13:09
kilden bruker

stemmer
1

Den enkleste definisjonen av rekursjon er "self-referanse". En funksjon som refererer til seg selv, det vil si kaller seg er rekursiv. Det viktigste å huske på, er at en rekursiv funksjon må ha en "base case", dvs. en tilstand som hvis sant fører det ikke til å kalle seg selv, og dermed avslutte rekursjon. Ellers vil du ha uendelig rekursjon:

rekursjon http://cart.kolix.de/wp-content/uploads/2009/12/infinite-recursion.jpg

Svarte 04/05/2010 kl. 16:10
kilden bruker

stemmer
1

Rekursjon er når du har en operasjon som bruker seg selv. Det vil sannsynligvis ha en stoppunktet, ellers ville det gå på for alltid.

La oss si at du ønsker å slå opp et ord i ordlisten. Du har en operasjon kalt "look-up" til din disposisjon.

Din venn sier "Jeg kunne virkelig skje opp noen pudding akkurat nå!" Du vet ikke hva han mener, slik at du ser opp "skjeen" i ordboken, og den leser noe sånt som dette:

Spoon: substantiv - en redskap med en runde scoop på slutten. Spoon: verb - for å bruke en skje på noe Spoon: verb - å kose tett bakfra

Nå, er at du egentlig ikke bra med engelsk, påpeker dette deg i riktig retning, men du trenger mer info. Så du velger "redskap" og "kos" å se opp for litt mer informasjon.

Cuddle: verb - å kose Utensil: substantiv - et verktøy, ofte en spiseredskap

Hei! Du vet hva kos er, og det har ingenting å gjøre med pudding. Du vet også at pudding er noe du spiser, så det er fornuftig nå. Din venn må ønske å spise pudding med en skje.

Ok, ok, dette var en veldig halt eksempel, men det illustrerer (kanskje dårlig) de to viktigste delene av rekursjon. 1) Den bruker i seg selv. I dette eksemplet har du ikke egentlig så opp et ord menings til du forstår det, og det kan bety å se opp flere ord. Dette bringer oss til punkt to, 2) Det stopper et sted. Det må ha en slags base-case. Ellers ville du bare ende opp som ser opp hvert ord i ordboka, som trolig ikke er for nyttig. Vår base-case var at du fikk nok informasjon til å lage en forbindelse mellom hva du tidligere gjorde, og ikke forsto.

Den tradisjonelle eksemplet som er gitt er faktoriell, hvor 5 faktoriell er 1 * 2 * 3 * 4 * 5 (som er 120). Basen tilfellet ville være 0 (eller 1, avhengig). Så, for alle heltall n, gjør du følgende

er n lik 0? returnere en annen måte, returnere n * (fakultet av n-1)

la oss gjøre dette med eksempel på 4 (som vi vet på forhånd er 1 * 2 * 3 * 4 = 24).

fakultetet av fire ... er det 0? nei, så det må være 4 * fakultetet av tre, men hva er fakultetet av tre? det er 3 * fakultetet av to fakultetet av to er 2 * fakultetet av en fakultetet av en er en * fakultetet av 0, og vi vet fakultetet av 0! -D det er en, er at definisjonen fakultet av 1 er 1 * faktoriell fra 0, som var 1 ... så 1 * 1 = 1 fakultet av 2 er 2 * faktoriell av 1, som var 1 ... så 2 * 1 = 2 faktoriell av tre er 3 * faktoriell på 2, som var 2 ... så 3 * 2 = 6 faktoriell av 4 (endelig !!) er 4 * fakultet av tre, som var 6 ... 4 * 6 er 24

Fakultet er et enkelt tilfelle av "base case, og bruker seg selv".

Nå merker vi fortsatt jobber med fakultetet av fire hele veien ned ... Hvis vi ønsket fakultetet av 100, ville vi måtte gå hele veien ned til 0 ... som kan ha mye overhead til det. På samme måte, hvis vi finner en obskur ord å slå opp i ordboken, det kan ta så opp andre ord og skanning for kontekst ledetråder til vi finner en sammenheng vi er kjent med. Rekursive metoder kan ta lang tid å jobbe seg gjennom. Men når de brukes på riktig måte, og forstått, kan de gjøre komplisert arbeid overraskende enkelt.

Svarte 04/05/2010 kl. 16:04
kilden bruker

stemmer
1

Svært mange problemer kan betraktes i to typer brikker:

  1. Base tilfeller, som er elementære ting som du kan løse ved å bare se på dem, og
  2. Rekursive tilfeller, som bygger et større problem ut av mindre biter (elementære eller på annen måte).

Så hva er en rekursiv funksjon? Vel, det er der du har en funksjon som er definert i form av seg selv, direkte eller indirekte. OK, det høres latterlig før du skjønner at det er fornuftig for problemene med den typen som er beskrevet ovenfor: du løse grunn tilfeller direkte og håndtere de rekursive tilfeller ved hjelp av rekursive samtaler for å løse de mindre stykker av problemet innebygd i.

Den virkelig klassisk eksempel på hvor du trenger rekursjon (eller noe som lukter veldig mye som det) er når du arbeider med et tre. Bladene på treet er ved basisprosessen, og grenene er den tilbakevendende tilfelle. (I pseudo-C.)

struct Tree {
    int leaf;
    Tree *leftBranch;
    Tree *rightBranch;
};

Den enkleste måten å skrive ut dette i orden er å bruke rekursjon:

function printTreeInOrder(Tree *tree) {
    if (tree->leftBranch) {
        printTreeInOrder(tree->leftBranch);
    }
    print(tree->leaf);
    if (tree->rightBranch) {
        printTreeInOrder(tree->rightBranch);
    }
}

Det er dødt lett å se at det kommer til å fungere, siden det er krystallklart. (Den ikke-rekursive tilsvarende er ganske mye mer komplisert, krever en stabel struktur internt til å administrere listen over ting å behandle.) Vel, forutsatt at ingen har gjort en sirkulær tilkobling av kurset.

Matematisk er kunsten å vise at rekursjon er temmet fokusere på å finne en beregning for størrelsen av argumentene. For vårt eksempel tre, er den enkleste metrisk den maksimale dybde av treet under den aktuelle noden. På blader, er det null. På en gren med bare blader under den, det er en, etc. Deretter kan du bare vise at det er strengt ordnet rekkefølge på størrelsen av argumentene at funksjonen er påberopt på for å behandle treet; argumentene til rekursive samtaler er alltid "mindre" i den forstand at det metriske enn argumentet til den generelle samtalen. Med et strengt avtagende kardinal beregning, er du sortert.

Det er også mulig å ha uendelig rekursjon. Det er rotete og på mange språk vil ikke fungere fordi stabelen blåser opp. (Der det fungerer, må språket motoren bestemme at funksjonen liksom ikke tilbake og er i stand derfor å optimalisere bort føring av stabelen Tricky ting generelt,. Tail-rekursjon er bare de mest trivielle måte å gjøre dette .)

Svarte 04/05/2010 kl. 15:29
kilden bruker

stemmer
1

Rekursjon er teknikken med å definere en funksjon, et sett eller en algoritme i form av seg selv.

For eksempel

n! = n(n-1)(n-2)(n-3)...........*3*2*1

Nå kan det bli definert rekursivt som: -

n! = n(n-1)!   for n>=1

I programmerings vilkår, når en funksjon eller metode kaller seg gjentatte ganger, helt til noen spesifikke betingelse blir oppfylt, denne prosessen kalles Rekursjon. Men det må være en avsluttende tilstand og funksjon eller metode må ikke gå inn i en uendelig løkke.

Svarte 04/05/2010 kl. 15:22
kilden bruker

stemmer
1

Rekursjon i databehandling er en teknikk som brukes til å beregne et resultat eller bivirkning samsvar med den normale retur fra en enkelt funksjon (metode, prosedyre eller blokk) påkalling.

Den rekursive funksjonen, ved definisjon, må ha evnen til å påkalle seg enten direkte eller indirekte (via andre funksjoner) avhengig av en utgang betingelse eller de betingelser ikke er oppfylt. Hvis en exit betingelse er oppfylt bestemte anrops tilbake til sin innringeren. Dette fortsetter inntil den opprinnelige påkallingen returneres fra, hvoretter det ønskede resultat eller bivirkning vil være tilgjengelig.

Som et eksempel, her er en funksjon for å utføre quicksort algoritmen i Scala ( kopiert fra Wikipedia-oppføring for Scala )

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

I dette tilfellet avkjørselen tilstanden er en tom liste.

Svarte 04/05/2010 kl. 14:14
kilden bruker

stemmer
1

funksjon kalle seg eller bruke sin egen definisjon.

Svarte 04/05/2010 kl. 13:59
kilden bruker

stemmer
1

Enhver algoritme utviser strukturell rekursjon på en datatype hvis utgangspunktet består av en bryter-setningen med en sak for hvert tilfelle av datatypen.

for eksempel når du arbeider på en type

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

en strukturell rekursiv algoritme vil ha form

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

Dette er virkelig den mest opplagte måten å skrive noen algorith som fungerer på en datastruktur.

nå, når du ser på heltall (vel, de naturlige tall) som er definert ved hjelp av peanos aksiomer

 integer = 0 | succ(integer)

du ser at en strukturell rekursiv algoritme på tall ser slik ut

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

den altfor velkjente faktoriell funksjon er den mest trivielle eksempel på denne form.

Svarte 04/05/2010 kl. 13:53
kilden bruker

stemmer
1

hei, beklager hvis min mening er enig med noen, jeg prøver bare å forklare rekursjon i vanlig engelsk.

anta at du har tre ledere - Jack, John og Morgan. Jack klarer 2 programmerere, John - 3, og Morgan - 5. Du kommer til å gi enhver leder 300 $ og ønsker å vite hva det ville koste. Svaret er opplagt - men hva hvis to av Morgan-medarbeidere er også ledere?

Her kommer rekursjon. du starter fra toppen av hierarkiet. Sommerlig kostnaden er 0 $. du starter med Jack, så sjekk om han har noen ledere som ansatte. hvis du finner noen av dem, sjekke om de har noen ledere som ansatte og så videre. Legg 300 $ til den sommerlige kostnaden hver gang du finner en manager. når du er ferdig med Jack, gå til John, hans ansatte og deretter til Morgan.

Du vet aldri hvor mye sykluser vil du gå før du får et svar, om du vet hvor mange ledere du har og hvor mange budsjett kan du bruke.

Rekursjon er et tre, med henholdsvis grener og blader, kalt foreldre og barn. Når du bruker en rekursjon algoritme, du mer eller mindre bevisst er å bygge et tre fra dataene.

Svarte 04/05/2010 kl. 12:50
kilden bruker

stemmer
1

I vanlig engelsk, betyr rekursjon å gjenta some igjen og igjen.

I programmering ett eksempel er å kalle funksjonen i seg selv.

Se på følgende eksempel beregne fakultetet av et tall:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}
Svarte 04/05/2010 kl. 12:48
kilden bruker

stemmer
1

Rekursjon er prosessen hvor en metodekall iself å være i stand til å utføre en viss oppgave. Det reduserer redundency med kode. De fleste recurssive funksjoner eller metoder må ha en condifiton å bryte recussive kaller dvs. stoppe den fra å kalle seg selv hvis en betingelse er oppfylt - dette forhindrer oppretting av en uendelig loop. Ikke alle funksjoner som er egnet for å brukes rekursivt.

Svarte 04/05/2010 kl. 12:42
kilden bruker

stemmer
1

det er en måte å gjøre ting om og om igjen i det uendelige, slik at hver alternativet brukes.

for eksempel hvis du ønsket å få alle linkene på en html-side du vil ønske å ha rekursjon fordi når du får alle linker på side 1 vil du ønsker å få alle koblinger på hver av linkene som finnes på den første siden. deretter for hver kobling til en nyside vil du ønsker disse koblingene og så videre ... med andre ord er det en funksjon som kaller seg fra innsiden selv.

når du gjør dette trenger du en måte å vite når du skal stoppe eller annet du vil være i en endeløs løkke slik at du legger til et heltall param til funksjonen for å spore antall sykluser.

i C # vil du ha noe som dette:

private void findlinks(string URL, int reccursiveCycleNumb)    {
   if (reccursiveCycleNumb == 0)
        {
            return;
        }

        //recursive action here
        foreach (LinkItem i in LinkFinder.Find(URL))
        {
            //see what links are being caught...
            lblResults.Text += i.Href + "<BR>";

            findlinks(i.Href, reccursiveCycleNumb - 1);
        }

        reccursiveCycleNumb -= reccursiveCycleNumb;
}
Svarte 04/05/2010 kl. 12:02
kilden bruker

stemmer
1

"Hvis jeg har en hammer, gjøre alt ser ut som en spiker."

Rekursjon er en problemløsende strategi for store problemer, hvor hvert skritt bare, "snu 2 små ting i en større ting," hver gang med samme hammer.

Eksempel

Anta at skrivebordet er dekket med en uorganisert rot av 1024 papirer. Hvordan du gjør en ryddig, rent bunke med papirer fra rot, ved hjelp av rekursjon?

  1. Divide: Spre alle arkene ut, så du har bare ett ark i hver "stack".
  2. Erobre:
    1. Gå rundt, setter hvert ark oppå en annen ark. Du har nå stabler av to.
    2. Gå rundt, setter hver 2-stabel oppå hverandre to-stack. Du har nå stabler av fire.
    3. Gå rundt, setter hver 4-stabel på toppen av en annen 4-stabel. Du har nå stabler av åtte.
    4. ... igjen og igjen ...
    5. Du har nå en stor bunke med 1024 ark!

Legg merke til at dette er ganske intuitive, bortsett fra å telle alt (som ikke er strengt nødvendig). Du kan ikke gå hele veien ned til 1-arks stabler, i virkeligheten, men du kan og det vil fortsatt fungere. Den viktigste delen er hammer: Med armene, kan du alltids sette en stabel på toppen av den andre for å gjøre en større stack, og det spiller ingen rolle (innenfor rimelighetens grenser) hvor stor enten stack er.

Svarte 04/05/2010 kl. 11:54
kilden bruker

stemmer
1

Rekursjon som det gjelder for programmeringen er i utgangspunktet å kalle en funksjon fra inne i sin egen definisjon (inne i seg selv), med ulike parametere, slik som for å utføre en oppgave.

Svarte 04/05/2010 kl. 11:25
kilden bruker

stemmer
1

Du ønsker å bruke den når du har en trestruktur. Det er veldig nyttig i å lese XML.

Svarte 21/08/2008 kl. 13:18
kilden bruker

stemmer
1

Mario, jeg forstår ikke hvorfor du brukte rekursjon for at f.eks .. Hvorfor ikke bare sløyfe gjennom hver oppføring? Noe sånt som dette:

String ArrangeString(TStringList* items, String separator)
{
    String result = items->Strings[0];

    for (int position=1; position < items->count; position++) {
        result += separator + items->Strings[position];
    }

    return result;
}

Ovennevnte metode vil være raskere og enklere. Det er ikke nødvendig å bruke rekursjon i stedet for en enkel sløyfe. Jeg tror disse slags eksempler er derfor rekursjon får en dårlig rap. Selv den kanoniske faktorielle funksjon eksempel er bedre implementert med en løkke.

Svarte 06/08/2008 kl. 03:19
kilden bruker

stemmer
0

Egentlig bedre rekursive løsningen for fakultetet bør være:

int factorial_accumulate(int n, int accum) {
    return (n < 2 ? accum : factorial_accumulate(n - 1, n * accum));
}

int factorial(int n) {
    return factorial_accumulate(n, 1);
}

Fordi denne versjonen er Tail Recursive

Svarte 21/08/2008 kl. 13:39
kilden bruker

stemmer
0

Jeg bruker rekursjon. Hva har det å gjøre med å ha en CS grad ... (som jeg ikke gjør det, forresten)

Vanlige bruksområder jeg har funnet:

  1. kartene - Recurse gjennom filsystemet starter på dokument rot
  2. edderkopper - gjennomgang gjennom et nettsted for å finne e-postadresse, lenker, etc.
  3. ?
Svarte 06/08/2008 kl. 03:13
kilden bruker

stemmer
0

Jeg har laget en rekursiv funksjon for å sette sammen en liste over strenger med en separator mellom dem. Jeg bruker det meste for å lage SQL-uttrykk, ved å sende en liste over områder som ' elementer ' og en ' komma + space ' som separator. Her er funksjonen (Den bruker noen Borland Builder innfødte datatyper, men kan tilpasses andre miljøer):

String ArrangeString(TStringList* items, int position, String separator)
{
  String result;

  result = items->Strings[position];

  if (position <= items->Count)
    result += separator + ArrangeString(items, position + 1, separator);

  return result;
}

Jeg kaller det på denne måten:

String columnsList;
columnsList = ArrangeString(columns, 0, ", ");

Tenk deg at du har en rekke navngitte ' felt ' med data i det: ' NAME ', ' release ', ' labelId '. Så du kaller funksjonen:

ArrangeString(fields, 0, ", ");

Som funksjon begynner å arbeide, den variable ' resultat mottar' verdien til stilling 0 i matrisen, som er ' NAME '.

Deretter sjekker den om den posisjonen den er å håndtere er den siste. Som det er ikke, så det slår sammen resultatet med separator og resultatet av en funksjon, som, oh Gud, dette er samme funksjon. Men denne gangen, sjekk det ut, det kalle seg å legge en til stillingen.

ArrangeString(fields, 1, ", ");

Det holder å gjenta, og skaper en LIFO haug, til den når et punkt hvor den posisjon som behandles er den siste, slik at funksjonen returnerer eneste elementet på den posisjonen på listen, ikke sette sammen lenger. Da hoper er sammensatt bakover.

Har det? Hvis du ikke gjør det, jeg har en annen måte å forklare det. : O)

Svarte 06/08/2008 kl. 03:00
kilden bruker

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more