Pytania otagowane jako recursion

Pytania dotyczące obiektów, takich jak funkcje, algorytmy lub struktury danych, które są wyrażane za pomocą „mniejszych” wystąpień samych siebie.

4
Co to jest rekurencja ogona?
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 rekurencja ogona. Czy ktoś może wyjaśnić tę …
5
Iteracja może zastąpić rekurencję?
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ą odpowiedzią, która powiedziała, że ​​tak, to możliwe. …
6
Co jest najbardziej wydajne dla GCD?
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ć najbardziej wydajnego kodu w moim …
2
Definicje rekurencyjne nad typem indukcyjnym z zagnieżdżonymi komponentami
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 -> LTree. Naiwny sposób definiowania funkcji rekurencyjnej nad tymi drzewami …
3
Dlaczego pętle są szybsze niż rekurencja?
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 uzasadnienie?
3
Czy drzewo można przemierzać bez rekurencji, stosu lub kolejki, a jedynie garść wskazówek?
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 to pytanie, które ostatecznie zostało zaakceptowane przez …
2
Czy ten program zakończy się z każdą liczbą całkowitą?
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 . Ale mój przyjaciel nie zgodził się z …
2
Jaka właściwość wad pozwala na wyeliminowanie wad modulo ogona rekurencyjnego?
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 rekurencyjne jest zawinięte w wywołanie do cons. foo(...): # ... return …
6
Przykłady zaawansowanych algorytmów rekurencyjnych
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 interesujących algorytmów rekurencyjnych, ale nie znalazłem żadnego. Wszystkie algorytmy rekurencyjne, które mogłem wymyślić, są albo …
1
Czy to ogólny sposób na przekształcenie jakiejkolwiek procedury rekurencyjnej w rekurencję ogona?
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 pomocnika, aby rozpocząć. Wartość początkowa parametru „wynik” jest wartością punktu wyjścia procesu …
3
Czy „indukcyjne” i „rekurencyjne” mają bardzo podobne znaczenia?
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 działaniem rekurencyjnym lub indukcyjnym? Używam „rekurencyjnie”, ale dziś ktoś powiedział …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.