Pytania dotyczące obiektów, takich jak funkcje, algorytmy lub struktury danych, które są wyrażane za pomocą „mniejszych” wystąpień samych siebie.
Znam ogólną koncepcję rekurencji. Zetknąłem się z koncepcją rekurencji ogona podczas studiowania algorytmu Quicksort. W tym filmie z algorytmem szybkiego sortowania z MIT o godzinie 18:30 profesor mówi, że jest to algorytm rekurencyjny ogona. Nie jest dla mnie jasne, co tak naprawdę oznacza...
Widziałem przepełnienie całego stosu, np. Tutaj , tutaj , tutaj , tutaj , tutaj i kilku innych, których nie chcę wspominać, że „każdy program, który korzysta z rekurencji, można przekonwertować na program wykorzystujący tylko iterację”. Był nawet wysoko oceniany wątek z bardzo pozytywną...
Kiedy są jakieś (względnie) podstawowe przypadki (myślę, że student pierwszego roku CS na studiach), kiedy zamiast pętli można by użyć rekurencji?
Wiem, że algorytm Euclida jest najlepszym algorytmem do uzyskania GCD (wielkiego wspólnego dzielnika) listy dodatnich liczb całkowitych. Ale w praktyce możesz kodować ten algorytm na różne sposoby. (W moim przypadku zdecydowałem się na Javę, ale C / C ++ może być inną opcją). Potrzebuję użyć...
Rozważ typ indukcyjny, który ma pewne rekurencyjne zdarzenia w zagnieżdżonej, ale ściśle dodatniej lokalizacji. Na przykład drzewa ze skończonymi rozgałęzieniami z węzłami używającymi ogólnej struktury danych listy do przechowywania elementów potomnych. Inductive LTree : Set := Node : list LTree...
Dlaczego w konstrukcji kompilatora należy wyeliminować lewą rekurencję w gramatyce? Czytam, że dzieje się tak, ponieważ może powodować nieskończoną rekurencję, ale czy nie jest to prawdą również w przypadku prawidłowej gramatyki
W praktyce rozumiem, że każdą rekurencję można zapisać jako pętlę (i vice versa (?)) I jeśli mierzymy z rzeczywistymi komputerami, stwierdzimy, że pętle są szybsze niż rekurencja dla tego samego problemu. Ale czy istnieje jakaś teoria, która czyni tę różnicę, czy jest to głównie...
Kombinator Y ma typ . Według korespondencji Curry-Howarda, ponieważ typ ( a → a ) → a jest zamieszkały, musi odpowiadać prawdziwemu twierdzeniu. Jednak a → a jest zawsze prawdziwe, więc wydaje się, że typ kombinatora Y odpowiada twierdzeniu a , co nie zawsze jest prawdziwe. Jak to może być?( a → a...
Pół dekady temu siedziałem w klasie struktur danych, w której profesor oferował dodatkowy kredyt, jeśli ktokolwiek mógł przemierzać drzewo bez użycia rekurencji, stosu, kolejki itp. (Lub innych podobnych struktur danych) i tylko kilka wskazówek. Wpadłem na to, co uważałem za oczywistą odpowiedź na...
W częściowym teście na przygotowanie GATE pojawiło się pytanie: f(n): if n is even: f(n) = n/2 else f(n) = f(f(n-1)) Odpowiedziałem: „Zakończy się dla wszystkich liczb całkowitych”, ponieważ nawet w przypadku niektórych liczb całkowitych ujemnych zakończy się jako Błąd przepełnienia stosu...
Wyjaśniłem przyjacielowi słynny deterministyczny algorytm wyboru czasu liniowego (mediana algorytmu median). Rekurencja w tym algorytmie (choć jest bardzo prosta) jest dość skomplikowana. Istnieją dwa wywołania rekurencyjne, każde o różnych parametrach. Próbowałem znaleźć inne przykłady tak...
Znam ideę podstawowej eliminacji rekurencji ogona, w której funkcje, które zwracają bezpośredni wynik wywołania do siebie, można przepisać jako pętle iteracyjne. foo(...): # ... return foo(...) Rozumiem również, że jako szczególny przypadek funkcja może być nadal przepisana, jeśli wywołanie...
Korzystanie z następującego rekurencyjnego algorytmu Fibonacciego: def fib(n): if n==0: return 0 elif n==1 return 1 return (fib(n-1)+fib(n-2)) Jeśli wprowadzę cyfrę 5, aby znaleźć Fib (5), wiem, że to da wynik 5, ale jak zbadać złożoność tego algorytmu? Jak obliczyć wymagane...
Wygląda na to, że znalazłem ogólny sposób na konwersję dowolnej procedury rekurencyjnej na rekurencyjną: Zdefiniuj podprocedurę pomocnika z dodatkowym parametrem „wynik”. Zastosuj to, co zostanie zastosowane do wartości zwracanej przez procedurę do tego parametru. Zadzwoń do tej procedury...
Ostatnio natknąłem się na ten problem , odmianę wież hanoi . Opis problemu: Rozważ następującą odmianę dobrze znanego problemu Wieże Hanoi: Dostajemy wież i m dysków o rozmiarach 1 , 2 , 3 , … , m ułożonych na niektórych wieżach. Twoim celem jest przeniesienie wszystkich dysków do k- tej...
Czy „indukcyjne” i „rekurencyjne” oznaczają bardzo podobne? Na przykład, jeśli istnieje algorytm, który określa wektor n-dim przez określenie jego pierwszych elementów k + 1 na podstawie wyznaczonych pierwszych elementów k i jest inicjalizowany za pomocą pierwszego składnika, czy nazwałbyś go...
W programowaniu zależnym są dwa główne sposoby dekompozycji danych i wykonania rekurencji: Zależne dopasowanie wzorca : definicje funkcji podano w postaci wielu klauzul. Ujednolicenie zapewnia, że wszystkie pominięte przypadki są niemożliwe, a zewnętrzny solver zapewnia, że rekurencja jest...
Muszę utworzyć algorytm rekurencyjny, aby sprawdzić, czy drzewo binarne jest drzewem wyszukiwania binarnego, a także policzyć, ile jest pełnych gałęzi (węzeł nadrzędny z lewym i prawym węzłem podrzędnym) z założoną globalną zmienną zliczającą. To zadanie dla mojej klasy struktur danych. Do tej...
W artykule Parsing Expressions by Recursive Descent autorstwa Theodore Norvell (1999) autor zaczyna od następującej gramatyki wyrażeń arytmetycznych: E --> E "+" E | E "-" E | "-" E | E "*" E | E "/" E | E "^" E | "(" E ")" | v co jest dość złe, ponieważ jest dwuznaczne i lewostronne. Zaczyna...