Co je rekurze a když bych měl použít?

hlasů
121

Jedním z témat, která se zdá přijít pravidelně na e-mailové konference a on-line diskuse je skutková podstata (nebo nedostatek iontů) dělá Computer Science. Argument, který vypadá, že přijde čas a znovu pro negativní strany je, že byly kódování pro určitý počet let a nikdy použity rekurzi.

Takže otázka zní:

  1. Co je rekurze?
  2. Kdy se používá rekurzi?
  3. Proč se lidé používat rekurzi?
Položena 06/08/2008 v 03:29
zdroj uživatelem
V jiných jazycích...                            


40 odpovědí

hlasů
86

Existuje celá řada dobrých vysvětlení rekurze v tomto vlákně, tato odpověď je asi důvod, proč byste neměli používat ve většině jazyků. * Ve většině velkých implementací imperativem jazyka (tedy každý major implementace C, C ++, Basic, Python , Ruby, Java a C #) iterace je mnohem lepší než rekurze.

Chcete-li zjistit, proč projít kroky, které výše uvedené jazyky používají k volání funkce:

  1. Prostor je vybojoval na stohu argumentů Funkce a místních proměnných
  2. Argumenty Funkce jsou zkopírovány do tohoto nového prostoru
  3. ovládání skočí na funkci
  4. kód spustí funkci v
  5. Výsledek Funkce je zkopírována do návratové hodnoty
  6. stoh se přetočí do své předchozí polohy
  7. ovládání se vrátí zpět na místo, kde byla volána funkce

Dělá všechny tyto kroky vyžaduje určitý čas, obvykle o trochu víc, než je potřeba k iteraci smyčky. Nicméně, skutečný problém je v kroku # 1. Při spuštění mnoho programů, které přidělit jeden kus paměti pro jejich stohu, a když dojdou, že paměť (často, ale ne vždy kvůli rekurze), program havaruje kvůli přetečení zásobníku .

Takže v těchto jazycích rekurze je pomalejší, a to dělá náchylné k havárii. Existují ještě nějaké argumenty pro jeho použití ačkoli. Obecně platí, že kód napsaný rekurzivně je kratší a poněkud elegantnější, když víte, jak to číst.

K dispozici je technika, která jazyk realizátoři lze použít nazývá optimalizace ocas volání , které mohou eliminovat některé třídy přetečení zásobníku. Dal stručně: Jestliže funkce návrat výraz je prostě výsledek volání funkce, pak nemusíte přidávat nové úrovně do zásobníku, můžete znovu použít stávající pro funkci volána. Bohužel, málo naléhavé jazykově implementace mít optimalizace tail pohotovosti postavena v roce.

* I love rekurzi. Můj oblíbený statický jazyk nepoužívá smyčky vůbec, rekurze je jediný způsob, jak dělat něco opakovaně. Prostě si nemyslím, že rekurze je obecně dobrý nápad, v jazycích, které nejsou naladěni na to.

** Mimochodem Mario, typický název pro funkci ArrangeString je „připojit“, a já bych se nedivil, kdyby váš jazyk volby již nemá implementaci ní.

Odpovězeno 06/08/2008 v 06:09
zdroj uživatelem

hlasů
63

Jednoduché anglický příklad rekurze.

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.
Odpovězeno 04/05/2010 v 17:38
zdroj uživatelem

hlasů
49

V té nejzákladnější počítačové vědy smyslu, rekurze je funkce, která sama sebe nazývá. Řekněme, že máte připojený seznam strukturu:

struct Node {
    Node* next;
};

A chcete zjistit, jak dlouho bude spojový seznam je můžete to udělat s rekurze:

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

(To by mohlo být samozřejmě provedeno cyklu for také, ale je užitečný jako ilustraci konceptu)

Odpovězeno 04/05/2010 v 12:25
zdroj uživatelem

hlasů
46

Kdykoli funkce volá sama sebe, vytváří smyčku, pak je to rekurze. Jak se něco existují dobré a špatné použití použití pro rekurze.

Nejjednodušším příkladem je rekurze ocasu, kde je úplně poslední řádek funkce je výzvou pro sebe:

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

Nicméně, to je lame, téměř zbytečné příklad, protože to může být snadno nahrazena účinnějším iteraci. Koneckonců, rekurze trpí volání funkce režií, který ve výše uvedeném příkladu by mohl být značný ve srovnání s provozem uvnitř samotné funkce.

Takže celá důvod dělat rekurzi namísto opakování by mělo být využít zásobníku volání udělat nějaké chytré věci. Například, pokud volání funkce, několikrát s různými parametry uvnitř stejné smyčce pak je to způsob, jak dosáhnout větvení . Klasickým příkladem je Sierpinski trojúhelník .

zadejte popis obrázku zde

Můžete čerpat jeden z těch velmi jednoduše pomocí rekurze, kde zásobník volání pobočky ve 3 směrech:

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);
    }
}

Pokud se pokusíte udělat totéž s iteraci Myslím, že zjistíte, že má mnohem více kódu dosáhnout.

Ostatní případy běžné použití by mohlo zahrnovat pojezdové hierarchie, například webové stránky prohledávačům, adresář srovnání atd

Závěr

V praxi to znamená, rekurze dává největší smysl, kdykoliv budete potřebovat iterativní větvení.

Odpovězeno 04/05/2010 v 14:33
zdroj uživatelem

hlasů
28

Rekurze je způsob řešení problémů na základě rozděl a panuj mentality. Základní myšlenkou je, že budete mít původní problém a rozdělit jej na menší (snadněji vyřešených případů) samo o sobě vyřešit ty menší instance (obvykle opětovným použitím stejného algoritmu) a pak znovu složit do výsledného řešení.

Kanonický příklad je rutinní pro generování faktoriálem n. Faktoriál n se vypočítá vynásobením všechna čísla mezi 1 a n. Iterativní řešení v C # vypadá takto:

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

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

  return fact;
}

Na tom není nic divného iterační řešení a mělo by smysl, aby někdo obeznámen s C #.

Rekurzivní nalezeno řešení tím, že rozpozná, že n-tý Factorial je n * Fakt (n-1). Nebo jinak řečeno, pokud víte, co je konkrétní číslo Factorial je můžete vypočítat další. Zde je rekurzivní řešení v C #:

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

  return n * FactRec( n - 1 );
}

První část této funkce je známý jako základního modelu (nebo někdy stráž bodu) a je to, co brání algoritmus v běhu navždy. Je to prostě vrátí hodnotu 1, když je tato funkce volána s hodnotou 1 nebo méně. Druhá část je mnohem zajímavější a je známý jako rekurzivní kroku . Zde říkáme stejnou metodu s mírně modifikovanou parametru (my ji decrement o 1) a pak násobí výsledek s naší kopii n.

Když se poprvé setkal to může být trochu matoucí, takže je to poučné zkoumat, jak to funguje, když je spuštěn. Představme si, že říkáme FactRec (5). Jsme se vstoupit do rutiny, které nejsou vyzvednout u základního scénáře, a tak jsme skončili takhle:

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

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

Budeme-li znovu zadat metodu s parametrem 4 jsme opět nepřestala doložkou strážní, a tak jsme skončili na adrese:

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

Dosadíme-li tento návratovou hodnotu do návratové hodnoty výše dostaneme

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

To by mělo dát ponětí o tom, jak je konečné řešení dorazil takže budeme rychle sledovat a ukázat, každý krok na cestě dolů:

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

To v konečném substituce se stane, když je základní případ spuštěna. V tomto okamžiku máme jednoduchý algrebraic vzorec pro řešení, které odpovídá přímo s definicí Faktoriály na prvním místě.

Je poučné si uvědomit, že každé volání do metoda vede buď základní případ je spuštěna nebo volání stejným způsobem, kde parametry jsou blíže k základnímu případu (často nazývaný rekurzivní volání). Pokud toto není ten případ, pak tato metoda poběží navždy.

Odpovězeno 06/08/2008 v 03:54
zdroj uživatelem

hlasů
12

Rekurze je vyřešit problém s funkcí, která sama volá. Dobrým příkladem toho je faktoriál funkce. Faktoriál je problém matematický kde faktorová 5, například, je 5 * 4 * 3 * 2 * 1. Tato funkce řeší tento v C # pro pozitivní celá čísla (netestováno - může být chyba).

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

    return n * Factorial(n - 1);
}
Odpovězeno 04/05/2010 v 12:29
zdroj uživatelem

hlasů
9

Vezměme si starý známý problém :

V matematice, největší společný dělitel (GCD) ... ze dvou nebo více non-nula celá čísla, je největší kladné číslo, které dělí čísla beze zbytku.

Definice GCD je překvapivě jednoduchá:

definice gcd

kde mod je operátor modulo (to znamená, že zbytek po celočíselné dělení).

V angličtině, tato definice říká, že největší společný dělitel libovolného počtu a nula je to, že počet a největší společný dělitel dvou čísel m a n je největší společný dělitel n a zbytek po dělení m o n .

Pokud byste chtěli vědět, proč to funguje, naleznete ve Wikipedii na algoritmu euklidovské .

Pojďme počítat gcd (10, 8), jako příklad. Každý krok je roven jedné těsně před ním:

  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

V prvním kroku 8 se nerovná nule, takže se použije druhý součástí definice. 10 mod 8 = 2, protože 8 přejde do 10, jakmile se zbytkem 2. V kroku 3, druhá část se použije znovu, ale tentokrát 8 mod 2 = 0, protože 2 dělí 8 beze zbytku. V kroku 5, druhý argument je 0, tak odpověď je 2.

Všimli jste si, že se objeví gcd na levé i pravé straně rovnítka? Matematik by řekl této definice je rekurzivní, protože výraz jste vymezení se vrací ve své definici.

Rekurzivní definice mají tendenci být elegantní. Například rekurzivní definice součet seznamu je

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

kde headje první prvek v seznamu a tailje zbytek seznamu. Všimněte si, že sumse vrací ve své definici koncem.

Možná byste raději maximální hodnotu ze seznamu, místo:

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

Dalo by se definovat množení non-záporná celá čísla rekurzivně proměnit série přídavků:

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

V případě, že něco o transformaci násobení do série přídavků nemá smysl, zkuste rozšířit několik jednoduchých příkladů vidět, jak to funguje.

Merge sort má krásný rekurzivní definici:

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

Rekurzivní definice jsou všude kolem, pokud víte, co hledat. Všimněte si, jak všechny tyto definice mají velmi jednoduché základní případ, například , gcd (m, 0) = m. Rekurzivní případy zmenšit na problém se dostat dolů do jednoduchých odpovědí.

S tímto pochopením, si nyní můžete ocenit další algoritmy v Wikipedie článek o rekurze !

Odpovězeno 04/05/2010 v 14:58
zdroj uživatelem

hlasů
9

Rekurze odkazuje na metodu, která řeší problém tím, že řeší menší verzi tohoto problému a pak používat tento výsledek a navíc některé další výpočty formulovat odpověď na původní problém. Často se v procesu řešení menší verzi, tato metoda bude řešit ještě menší verze tohoto problému, a tak dále, dokud nedosáhne „základní případ“, který je triviální řešení.

Například, pro výpočet faktoriálu pro číslo X, lze reprezentovat jako X times the factorial of X-1. To znamená, že metoda „recurses“ najít faktoriál X-1, a pak násobí bez ohledu na to dostal tím Xdát konečnou odpověď. Samozřejmě, najít faktoriál X-1, bude to poprvé vypočítat faktoriál X-2, a tak dále. Referenční případ, bude-li Xje 0 nebo 1, přičemž v tomto případě ví vrátit 1, protože 0! = 1! = 1.

Odpovězeno 04/05/2010 v 12:26
zdroj uživatelem

hlasů
9
  1. Funkce, která sama sebe nazývá
  2. Když funkce může být (snadno) rozložit na jednoduché operace plus stejné funkce na několik menších částí problému. Řekl bych spíše, že to dělá to vhodným kandidátem pro rekurze.
  3. Dělají!

Kanonický příklad je faktoriál, který vypadá takto:

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

  return a*fact(a-1);
}

Obecně platí, že rekurze není nutně rychle (volání funkce režii bývá vysoká, protože rekurzivní funkce mají tendenci být malé, viz výše) a mohou trpět některými problémy (přetečení zásobníku někdo?). Někteří říkají, že mají tendenci být těžké se dostat ‚pravdu‘ v netriviálních případech, ale nemám opravdu koupit do toho. V některých situacích, rekurze dává největší smysl a je nejvíce elegantní a jasný způsob, jak napsat konkrétní funkci. Je třeba poznamenat, že některé jazyky upřednostňují rekurzivní řešení a optimalizovat jejich e-mail (LISP přijde na mysl).

Odpovězeno 06/08/2008 v 03:35
zdroj uživatelem

hlasů
7

Rekurzivní funkce je ten, který sám nazývá. Nejčastějším důvodem Zjistil jsem, použít je křížení stromovou strukturu. Například, když mám TreeView s rámečky (myslím instalaci nového programu „vyberte funkce k instalaci“ strana), možná chci tlačítko „zkontrolovat všechny“, který by něco takového (pseudokódu):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

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

Takže vidíte, že checkRecursively nejprve zkontroluje uzel, který je předán, pak sama volá po každé z dětí, které uzlu.

Je potřeba být trochu opatrný s rekurze. Pokud se dostanete do nekonečné rekurzivní smyčky, dostanete výjimku přetečením zásobníku :)

Já si nemyslím, že důvod, proč by se lidé neměli používat, pokud je to vhodné. To je užitečné v některých případech, a ne v jiných.

Myslím, že proto, že se jedná o zajímavou technikou, někteří programátoři třeba skončit s použitím jej častěji, než by měly, a to bez skutečného opodstatnění. Toto dalo rekurze špatnou pověst v některých kruzích.

Odpovězeno 06/08/2008 v 03:44
zdroj uživatelem

hlasů
5

Rekurze je výraz se přímo, či nepřímo odkazovat.

Vezměme rekurzivní zkratky jako jednoduchý příklad:

  • GNU znamená GNU Not Unix
  • PHP je zkratka pro PHP: Hypertext Preprocessor
  • YAML znamená YAML Není Markup Language
  • WINE znamená Víno není emulátor
  • VISA zkratka pro Visa International Service Association

Další příklady na Wikipedii

Odpovězeno 04/05/2010 v 12:56
zdroj uživatelem

hlasů
5

Zde je jednoduchý příklad: kolik prvků v sadě. (Existují lepší způsoby, jak počítat věci, ale to je hezký jednoduchý rekurzivní příklad.)

Za prvé, musíme dvě pravidla:

  1. v případě, že soubor je prázdný, počet kusů v sadě je nula (duh!).
  2. v případě, že množina není prázdná, počet je jedna plus počet kusů v sadě po jednom položka je odstraněn.

Předpokládejme, že máte nastaveny takto: [xxx]. nechal spočítat to, kolik položek existují.

  1. množina je [xxx], která není prázdná, takže platí pravidlo 2. počet položek je jedna plus počet kusů [XX] (tj jsme odstranili položky).
  2. množina je [XX], takže opět platí pravidlo 2: jedno číslo + položek v [x].
  3. množina je [x], která ještě odpovídá pravidlo 2: jedna + počet kusů [].
  4. Nyní je souprava [], který odpovídá pravidlo 1: počet je nula!
  5. Teď, když víme, že odpověď v kroku 4 (0), můžeme vyřešit krok 3 (1 + 0)
  6. Stejně tak, když teď víme, že odpověď v kroku 3 (1), můžeme vyřešit krok 2 (1 + 1)
  7. A konečně teď, když víme, že odpověď v kroku 2 (2), můžeme vyřešit krok 1 (1 + 2) a získat počet položek v [xxx], který je 3. Hurá!

Můžeme reprezentovat to jako:

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

Při aplikaci rekurzivní řešení, které obvykle mají alespoň 2 pravidla:

  • Základem je jednoduchý případ, který stanoví, co se stane, když máte „spotřeboval“ všechna vaše data. To je obvykle nějaká změna „pokud jste mimo údajů do procesu, vaše odpověď je X“
  • rekurzivní pravidlo, které říká, co se stane, pokud máte stále data. To je obvykle nějaká pravidla, které říká, že „něco udělat, aby se vaše data nastavena menší, a znovu vaše pravidla pro menší sady dat.“

Budeme-li přeložit výše pseudokódu, dostaneme:

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

Je tu mnohem více užitečné příklady (projíždějící strom, například), které jsem si jist, že ostatní lidé se budou týkat.

Odpovězeno 06/08/2008 v 04:12
zdroj uživatelem

hlasů
5

Rekurze funguje nejlépe s tím, co jsem chtěl volat „fraktální problémy“, kde máte co do činění s velkou věc, která je vyrobena z menších verzí té velké věci, z nichž každý je ještě menší verze velké věci, a tak dále. Pokud budete mít projít nebo prohledat něco jako strom nebo vnořené stejné struktury, máte problém, který by mohl být dobrým kandidátem pro rekurze.

Lidé vyhýbají rekurzi z řady důvodů:

  1. Většina lidí (včetně mě) snížit své zuby na programovací procedurální nebo objektově orientované programování na rozdíl od funkcionální programování. Chcete-li takové lidi, iterační přístup (typicky pomocí smyčky) cítí přirozeněji.

  2. Ti z nás, kteří snížit naše programové zuby na procedurální nebo objektově orientované programování často bylo řečeno, aby se zabránilo rekurzi, protože je náchylný k chybám.

  3. Jsme často říkal, že rekurze je pomalý. Volání a návratu z rutiny opakovaně zahrnuje mnoho stoh tlačení a popping, který je pomalejší než opakování. Myslím, že některé jazyky zvládnout lépe než ostatní, a ty jazyky jsou s největší pravděpodobností ne ty, kde je dominantní vzor je procedurální nebo objektově orientované.

  4. Alespoň několik programovacích jazyků jsem použil, Pamatuji si, že slyšel doporučení nepoužívat rekurzi, pokud se dostane nad určitou hloubku, protože jeho stack není tak hluboká.

Odpovězeno 06/08/2008 v 04:12
zdroj uživatelem

hlasů
4

1.) Způsob je rekurzivní, pokud sám může volat; buď přímo:

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

nebo nepřímo:

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

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

2) Při použití rekurze

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.) Lidé používají rekurzi, pouze pokud to je velmi složité psát iterační kód. Například strom traversal techniky, jako je předobjednávku, postorder mohou být vyrobeny jak iterativní a rekurzivní. Ale obvykle používáme rekurzivní díky své jednoduchosti.

Odpovězeno 11/03/2014 v 10:47
zdroj uživatelem

hlasů
4

Rekurzivní výrok je ten, ve kterém můžete definovat proces, co dělat dál jako kombinace vstupů a to, co jste již udělal.

Například, vzít faktoriál:

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

Ale to je snadné pochopit, faktoriálu (6) je také:

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

Takže obecně:

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

Samozřejmě, že ošemetná věc, o rekurze je, že pokud chcete definovat, co se týče toho, co jste již udělali, musí existovat nějaké místo, kde začít.

V tomto příkladu jsme prostě udělat zvláštní případ definováním faktoriál (1) = 1.

Nyní vidíme to od zdola nahoru:

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

Vzhledem k tomu, jsme definovali faktoriál (1) = 1, dosáhneme „dno“.

Obecně lze říci, rekurzivní procedury mít dvě části:

1) rekurzivní část, která definuje určité postupy, pokud jde o nových vstupů v kombinaci s tím, co jste „již učinili“ stejným postupem. (tj factorial(n) = n*factorial(n-1))

2) základní část, která zajišťuje, že proces nebude opakovat navždy tím, že mu nějaké místo pro start (tj factorial(1) = 1)

To může být trochu matoucí se dostat hlavu kolem na první pohled, ale stačí se podívat na spoustu příkladů, a to by mělo všechno dohromady. Pokud chcete, mnohem hlubší pochopení konceptu, studovat matematické indukce. Také být vědomi, že některé jazyky optimalizovat pro rekurzivní volání, zatímco jiní ne. Je to docela snadné, aby se šíleně pomalé rekurzivní funkce, pokud si nedáte pozor, ale jsou zde i techniky aby tyto výkonný ve většině případů.

Snad to pomůže...

Odpovězeno 04/05/2010 v 14:30
zdroj uživatelem

hlasů
4

Líbí se mi tato definice:
V rekurze, rutinní řeší malou část problému samotného, rozděluje problém na menší kousky, a pak volá sám k vyřešení každé z menších kusů.

Také se mi líbí Steve McConnells diskusi o rekurze v zákoníku Kompletní kde kritizuje příklady používaných v oblasti počítačové vědy knih o rekurze.

Nepoužívat rekurzi pro faktoriálů nebo čísla Fibonacci

Jedním z problémů s počítačem vědeckých učebnicích je, že představí hloupé příklady rekurze. Typické příklady jsou výpočetní faktorového nebo vypočítání Fibonacci sekvenci. Rekurze je mocný nástroj, a je to opravdu hloupý, aby jej použít v žádném z těchto případů. Je-li programátor, který pracoval pro mě používá rekurzi pro výpočet faktoriálu, tak bych najmout někoho jiného.

Myslel jsem, že to bylo velmi zajímavým bodem zvyšovat a může být důvodem, proč se rekurze často nepochopen.

EDIT: To nebyl dig v Dav je odpověď - jsem neviděl, že odpověď, když jsem vyslán to

Odpovězeno 04/05/2010 v 12:29
zdroj uživatelem

hlasů
3

Příklad: Rekurzivní definice schodiště je: Schodiště se skládá z: - jediný krok a schodiště (rekurze) -, nebo pouze jeden krok (ukončení)

Odpovězeno 04/05/2010 v 14:34
zdroj uživatelem

hlasů
3

No, to je docela slušné definice máte. A wikipedia má dobrou definici příliš. Takže budu přidat další (asi horší) definici pro vás.

Když se lidé odkazují na „rekurze“, oni jsou obvykle mluví o funkce, které jste napsali, která sama sebe nazývá, dokud se to dělá svou práci. Rekurze může být užitečné při přecházení hierarchie v datových strukturách.

Odpovězeno 04/05/2010 v 12:27
zdroj uživatelem

hlasů
3

Na recurse na řešeného problému: nedělat nic, máte hotovo.
Na recurse na otevřeném problém: udělat další krok, pak rekurzivně na zbytek.

Odpovězeno 06/08/2008 v 04:32
zdroj uživatelem

hlasů
2

Jedná se o starou otázku, ale chci přidat odpověď z logistického hlediska (tedy nikoli z algoritmus správnost hlediska nebo hlediska výkonu).

Používám Javu pro práci, a Java nepodporuje vnořené funkci. Jako takový, jestli chci dělat rekurzi, možná budu muset definovat externí funkci (který existuje jen proto, že můj kód narazí proti byrokratickému pravidlu Java), nebo budu muset refaktorovat kód úplně (což jsem opravdu nenávidím dělat).

Proto se často vyhnout rekurzi, a provoz použití zásobníku místo, protože je sám o sobě v podstatě rekurze operace zásobník.

Odpovězeno 30/08/2014 v 11:09
zdroj uživatelem

hlasů
2

Rekurzivní funkce je funkce, která obsahuje výzvu k sobě. Rekurzivní struct je struct, který obsahuje instanci sebe. Můžete kombinovat dva jako rekurzivní třídě. Klíčovou součástí rekurzivní položky je, že obsahuje instance / volání sebe sama.

Vezměme si dvě zrcadla proti sobě. Viděli jsme čisté nekonečný efekt oni dělají. Každý odraz je instancí zrcadla, který je obsažen v jiné instanci zrcadlo, atd. Zrcadlo, obsahující odraz je samo o sobě rekurze.

Binární vyhledávací strom je dobrý programovací příklad rekurze. Struktura je rekurzivní s každým uzlem, který obsahuje 2 instance uzlu. Funkce pro práci na binárního vyhledávacího stromu jsou také rekurzivní.

Odpovězeno 04/05/2010 v 17:46
zdroj uživatelem

hlasů
2

V jednoduché angličtině: Předpokládejme, že si můžete dělat 3 věci:

  1. Vezměte jedno jablko
  2. Zapište ověřovací značky
  3. Počítat ověřovací značky

Máte spoustu jablek před vámi na stole a chcete vědět, kolik jablek existují.

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

Proces opakuje totéž, až budete hotovi, se nazývá rekurze.

Doufám, že to je „plain anglicky“ odpověď, kterou hledáte!

Odpovězeno 04/05/2010 v 14:09
zdroj uživatelem

hlasů
1

Nejjednodušší definice rekurze je „self-reference“. Funkce, která se odkazuje na sebe, tj volání sám je rekurzivní. Nejdůležitější věc, kterou byste měli mít na mysli, je to, že rekurzivní funkce musí mít „základní případ“, tedy podmínku, že pokud je pravdivá způsobuje, že není nazývat se, a tím ukončit rekurzi. V opačném případě budete mít nekonečnou rekurzi:

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

Odpovězeno 04/05/2010 v 17:10
zdroj uživatelem

hlasů
1

Rekurze je, když máte operaci, která používá sám. Pravděpodobně to bude mít zastavovací bod, jinak by to trvat věčně.

Řekněme, že chcete vyhledat slovo ve slovníku. Máte operaci s názvem „look-up“ k dispozici.

Váš kamarád říká: „Nemohl jsem opravdu lžíce nějaký pudink právě teď!“ Vy nevíte, co tím myslí, takže se podívat do „lžíci“ ve slovníku, a to zní asi takto:

Spoon: podstatné jméno - A nádoba s kulatým naběračka na konci. Spoon: sloveso - používat lžíci na něco Spoon: sloveso - mazlit těsně zpoza

Nyní je, že jste opravdu není dobré s angličtinou, to vám ukazuje správným směrem, ale je třeba více informací. Takže si vyberte „nádoba“ a „mazlit“ podívat do nějaké další informace.

Hýčkat: sloveso - tulit nádoba: podstatné jméno - nástroj, často jíst nádobí

Ahoj! Víš, co je přítulný, a to nemá nic společného s pudinkem. Také víte, že pudink je něco, co budete jíst, tak to dává smysl. Váš přítel musí chtít jíst pudink s lžící.

Dobře, dobře, to bylo velmi lame příklad, ale to ilustruje (možná špatně) obě hlavní části rekurze. 1) Používá sám. V tomto příkladu jste opravdu vzhlédl slovo smysluplně, dokud ji pochopit, a to by mohlo znamenat, hledá se další slova. To nás přivádí k bodu dva, 2) se zastaví někde. Musí to mít nějaký base-případu. V opačném případě byste prostě skončit vzhlédl každé slovo ve slovníku, který pravděpodobně není příliš užitečné. Naše základna případ byl, že máte dostatek informací, aby se spojení mezi tím, co jste předtím se a nechápal.

Tradiční příklad, který je uveden je faktoriál, kde 5 faktoriální je 1 * 2 * 3 * 4 * 5 (což je 120). Základna případ by být 0 (nebo 1, v závislosti). Takže pro jakékoliv celé číslo n, můžete provést následující kroky

je n rovno 0? vrátí 1 jinak, vrátí n * (faktoriál n-1)

jdeme na to s příkladem 4 (který známe dopředu je 1 * 2 * 3 * 4 = 24).

factorial 4 ... je to 0? Ne, tak to musí být 4 * faktoriál 3, ale to, co je faktoriál 3? je to 3 * factorial 2 faktoriálem 2 je 2 * faktoriál 1 faktoriálem 1 1 * factorial 0 a víme factorial 0! :-D to je 1, to je definice faktoriál 1 je 1 * faktoriál 0, který byl 1 ... tak 1 * 1 = 1 faktoriál 2 je 2 * faktoriál 1, který byl 1 ... tak 2 * 1 = 2 faktoriál 3 je 3 * faktoriál 2, který byl 2 ... tak, 3 * 2 = 6 faktoriál 4 (konečně !!) je 4 * faktoriál 3, který byl 6 ... 4 * 6 24

Faktoriál je jednoduchý případ „základního scénáře, a využívá sebe“.

Nyní si všimněte, byli jsme stále pracujeme na faktoriálem 4. celou cestu dolů ... Pokud bychom chtěli faktoriál 100, museli bychom jít celou cestu až do 0 ..., které by mohly mít hodně nad hlavou k němu. Stejným způsobem, pokud zjistíme, obskurní slovo se podívat do slovníku, to může trvat vyhledávání dalších slov a skenování pro kontextových záchytných bodů, dokud nenajdeme spojení Jsme zvyklí. Rekurzivní metody může trvat dlouhou dobu pracovat svou cestu. Nicméně, když jsou používány správně, a pochopil, že může dělat složité práce překvapivě jednoduchá.

Odpovězeno 04/05/2010 v 17:04
zdroj uživatelem

hlasů
1

Velmi mnoho problémů si lze představit ve dvou kusů:

  1. Základnové případy, které jsou základní věci, které můžete vyřešit tím, že jen při pohledu na ně, a
  2. Rekurzivní případy, které staví větší problém ven z menších kusů (základní nebo jinak).

Takže to, co je rekurzivní funkce? No, to je místo, kde budete mít funkci, která je definována, pokud jde o sobě, přímo nebo nepřímo. OK, to zní směšně, až si uvědomíte, že je to rozumné, problémy výše popsaného druhu: vyřešit případy základny přímo a vypořádat se s rekurzivních případech použití rekurzivní volání řešit menší kusy problému vložený uvnitř.

Skutečně Klasickým příkladem, kde je potřeba rekurze (nebo něco, co voní velmi podobně jako to) je, když máte co do činění se stromem. Listy stromu jsou základem případ a větve jsou rekurzivní případ. (V pseudo-C.)

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

Nejjednodušší způsob tisku na to, aby je použití rekurze:

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

Je to mrtvé snadné vidět, že to bude fungovat, protože je to naprosto jasné. (Non-rekurzivní ekvivalent je poměrně hodně složitější, vyžaduje konstrukce zásobníku interně spravovat seznam věcí, které zpracovávají.) No, za předpokladu, že nikdo to udělal kruhový propojení kurzu.

Matematicky je trik, což ukazuje, že rekurze je zkrocené je zaměřit se na nalezení metriku pro velikost argumentů. Pro náš strom Například nejjednodušší metrika je maximální hloubka stromu pod aktuální uzel. Na listí, je to nula. Na pobočce zbývá pouze pod ním, je to jedno, atd. Pak můžete jednoduše ukázat, že je striktně nařízeno sekvenci o velikosti argumentů, že funkce je odvolává na za účelem zpracování stromu; argumenty rekurzivní volání jsou vždy „menší“ v tom smyslu, že se metrika než argument k celkové hovoru. S striktně klesající kardinál metriky, budete třídit.

Je také možné mít nekonečnou rekurzi. To je chaotický a v mnoha jazycích nebude fungovat, protože zásobník vybouchne. (V případě, že funguje, musí být jazyk motor určuje, že funkce nějak nevrací a je schopen proto optimalizovat pryč vedení stohu Tricky věci obecně;. Tail-rekurze je jen velmi triviální způsob, jak toho dosáhnout, .)

Odpovězeno 04/05/2010 v 16:29
zdroj uživatelem

hlasů
1

Rekurze je technika definování funkce, sadu nebo algoritmus, pokud jde o sobě.

Například

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

Teď to může být definována rekurzivně jako: -

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

Z hlediska programování, když se funkce nebo metoda opakovaně volá sebe, až dostane splněny některé zvláštní podmínky, tento proces se nazývá rekurze. Ale musí být podmínka ukončení a funkci nebo způsob musí ne vstoupit do nekonečné smyčky.

Odpovězeno 04/05/2010 v 16:22
zdroj uživatelem

hlasů
1

Rekurze v práci na počítači je technika používaná pro výpočet výsledku, nebo vedlejší účinek po normálním návratu z jedné funkce (metoda, postup nebo blok) vyvolání.

Rekurzivní funkci, samozřejmě musí mít schopnost vyvolat sebe buď přímo, nebo nepřímo (prostřednictvím jiné funkce) v závislosti na stavu výstupu nebo podmínky nejsou splněny. Je-li splněna ukončovací podmínka splněna na zavolání se vrátí do Je to volajícího. Tento postup se opakuje, dokud se výchozí vyvolání se vrací z, kdy požadovaný výsledek nebo nežádoucí účinek bude k dispozici.

Jako příklad, tady je funkce, která umožňuje provádět algoritmus Quicksort v Scala ( zkopírovaný ze vstupu Wikipedia pro Scala )

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

V tomto případě je splněna ukončovací podmínka je prázdný seznam.

Odpovězeno 04/05/2010 v 15:14
zdroj uživatelem

hlasů
1

Funkce volat sebe nebo použít svou vlastní definici.

Odpovězeno 04/05/2010 v 14:59
zdroj uživatelem

hlasů
1

Jakýkoliv algoritmus vykazuje strukturální rekurze na datový typ, jestliže se v podstatě skládá ze spínacího příkazu s případem pro každý případ datový typ.

Například, když pracujete na typu

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

strukturální rekurzivní algoritmus bude mít podobu

 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

To je opravdu nejvíce zřejmý způsob, jak psát nějaký algorith, který pracuje na datové struktury.

Nyní, když se podíváte na celá čísla (dobře, přirozená čísla), jak jsou definovány pomocí Peano axiómy

 integer = 0 | succ(integer)

uvidíte, že strukturální rekurzivní algoritmus na celých vypadá následovně

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

příliš známý faktoriální funkce je o nejvíce triviální příklad této formy.

Odpovězeno 04/05/2010 v 14:53
zdroj uživatelem

hlasů
1

hej, je mi líto, jestli jsem toho názoru souhlasí s někým, jen se snažím vysvětlit, rekurze v plain anglicky.

Předpokládám, že máte tři manažery - Jack John a Morgan. Jack zvládá 2 programátoři, John - 3 a Morgan - 5. hodláte dát každý manažer $ 300 a chcete vědět, co by to stálo. Odpověď je zřejmá - ale co když 2 Morgan-s zaměstnanci jsou rovněž manažeři?

Zde přichází rekurze. začnete od vrcholu hierarchie. Summery náklady 0 $. začnete s Jackem, pak zkontrolujte, zda má nějaké manažery jako zaměstnanci. pokud zjistíte, že některý z nich, zkontrolujte, zda mají nějaké manažery jako zaměstnanci, a tak dále. Přidat 300 dolarů na letním cenu pokaždé, když najít manažera. když jste skončil s Jackem, přejděte na Johna, jeho zaměstnanci a pak se Morgan.

Už nikdy nebudete vědět, kolik cyklů půjdeš, než se dostane odpověď, i když víte, kolik manažerů máte a kolik rozpočtu můžete strávit.

Rekurze je strom s větvemi a listím, tzv rodiči a dětmi, resp. Použijete-li algoritmus rekurze, můžete více či méně vědomě se staví strom z dat.

Odpovězeno 04/05/2010 v 13:50
zdroj uživatelem

hlasů
1

V jednoduché angličtině, rekurze znamená, že znovu a znovu opakovat someting.

Při programování jedním příkladem je volání funkce v sobě.

Podívejte se na následující příklad výpočtu faktoriál čísla:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}
Odpovězeno 04/05/2010 v 13:48
zdroj uživatelem

hlasů
1

Rekurze je proces, při kterém volání metody iself, aby bylo možné provést určitý úkol. Snižuje redundency kódu. Většina recurssive funkce nebo metody musí mít condifiton rozbít recussive volat tedy přestat ji z volat sám, pokud je splněna podmínka - to brání vytvoření jednotných nekonečné smyčce. Ne všechny funkce jsou vhodné pro použití rekurzivně.

Odpovězeno 04/05/2010 v 13:42
zdroj uživatelem

hlasů
1

jeho způsob, jak dělat věci znovu a znovu do nekonečna, takže se používá každý možnost.

Například pokud jste chtěli získat všechny odkazy na html stránky, budete chtít mít rekurze, protože když se dostanete všechny odkazy na straně 1, budete chtít získat všechny odkazy na každý z odkazů nalézt na první stránce. pak pro každý odkaz na newpage budete chtít tyto odkazy a tak dále ... jinými slovy, jedná se o funkci, která sama sebe nazývá zevnitř sebe.

když to budete potřebovat způsob, jak vědět, kdy přestat, jinak budete v nekonečné smyčce tak přidáte integer param funkci, ke sledování počtu cyklů.

v jazyce C #, budete mít něco takového:

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;
}
Odpovězeno 04/05/2010 v 13:02
zdroj uživatelem

hlasů
1

„Mám-li kladivo, aby všechno vypadat jako hřebík.“

Rekurze je problém-řešit strategii pro obrovské problémy, kde na každém kroku jen „otočit 2 malé věci do jedné větší věc,“ pokaždé, když se stejným kladivem.

Příklad

Předpokládejme, že vaše deska je pokryta zmatený nepořádek 1024 příspěvků. Jak si udělat jeden úhledný, čistý stoh papírů z nepořádek, použití rekurze?

  1. Divide: Máslo ze všech čtyř listů ven, takže budete mít jen jeden list v každé „stack“.
  2. Dobýt:
    1. Objet, dávat každý list na vrcholu jednoho dalšího listu. Nyní máte stohy 2.
    2. Objet, dávat každému 2-stack na vršek dalšího 2-stack. Nyní máte stohy 4.
    3. Objet, uvedení každé 4-stack na vršek dalšího 4-stack. Nyní máte stohy 8.
    4. ... dál a dál ...
    5. Nyní máte jeden velký stoh 1024 listů!

Všimněte si, že to je docela intuitivní, kromě počítání vše (což není nezbytně nutné). V některých případech nemusí jít celou cestu dolů na 1 listů hromádek, ve skutečnosti, ale ty by mohly a to by ještě fungovat. Důležitou součástí je kladivo: S rukama, můžete vždy dát jednu hromadu na horní straně druhé, aby se větší stack, a nezáleží na tom, (v rozumných mezích), jak velký jeden stoh.

Odpovězeno 04/05/2010 v 12:54
zdroj uživatelem

hlasů
1

Rekurze, jak to platí pro programování je v podstatě volání funkce zevnitř své vlastní definici (uvnitř sebe sama), s odlišnými parametry tak, aby splnění úkolu.

Odpovězeno 04/05/2010 v 12:25
zdroj uživatelem

hlasů
1

Chcete-li ji použít kdykoliv budete mít stromovou strukturu. To je velmi užitečné při čtení XML.

Odpovězeno 21/08/2008 v 14:18
zdroj uživatelem

hlasů
1

Mario, nechápu, proč se používá rekurzi pro tuto např .. Proč jednoduše smyčku přes každou položku? Něco takového:

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;
}

Výše uvedená metoda by být rychlejší a jednodušší. Není třeba používat rekurzi namísto jednoduchého smyčky. Myslím, že tyto druhy příkladů je důvod, proč rekurze dostane špatný rap. Dokonce i kanonický faktorial funkce příklad je lépe provádět s poutkem.

Odpovězeno 06/08/2008 v 04:19
zdroj uživatelem

hlasů
0

Ve skutečnosti, tím lépe rekurzivní řešení pro faktoriálem by měla být:

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);
}

Vzhledem k tomu, tato verze je ocas rekurzivní

Odpovězeno 21/08/2008 v 14:39
zdroj uživatelem

hlasů
0

I používat rekurzi. Co to má co do činění s mající stupeň CS ... (což nemám, mimochodem)

Běžná používání jsem nalezl:

  1. mapy stránek - recurse pomocí souborového systému začíná na kořen dokumentu
  2. pavouci - lezoucí prostřednictvím internetových stránek najít e-mailovou adresu, odkazy, atd
  3. ?
Odpovězeno 06/08/2008 v 04:13
zdroj uživatelem

hlasů
0

Vytvořil jsem rekurzivní funkce zřetězit seznam řetězců s oddělovač mezi nimi. Používám ji hlavně pro vytvoření SQL výrazů, tím, že projde seznam polí jako ‚ položky ‘ a ‚ čárka + prostor ‘ jako oddělovač. Zde je funkce (to používá některé Borland Builder nativní datové typy, ale mohou být přizpůsobeny, aby se vešly jakékoli jiné prostředí):

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;
}

Nazval jsem to takhle:

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

Představte si, že máte pole s názvem ‚ pole ‘ s těmito údaji uvnitř ní: ‚ albumName ‘, ‚ releasedate ‘, ‚ labelId ‘. Pak volání funkce:

ArrangeString(fields, 0, ", ");

Jako funkce začne pracovat, proměnná ‚ výsledku ‘ přijímá hodnotu polohy 0 matice, která je ‚ albumName ‘.

Pak se zkontroluje, zda je poloha to se zabývá, je ten poslední. Protože tomu tak není, pak se zřetězí výsledek s odlučovačem a výsledek funkce, která ach bože, je to stejná funkce. Ale tentokrát, podívat se na to, že nazývat přičtením 1 do polohy.

ArrangeString(fields, 1, ", ");

To se opakuje, vytváří LIFO hromadu, dokud nedosáhne bod, ve kterém je pozice zabýval je poslední, takže funkce vrátí pouze položky na této pozici v seznamu, už ne zřetězení. Pak vlas zřetězen zpět.

Mám to? Pokud tak neučiníte, mám jiný způsob, jak to vysvětlit. :Ó)

Odpovězeno 06/08/2008 v 04:00
zdroj uživatelem

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