Quiz o rekurencji

Co to jest rekurencja?

• Proces, w którym funkcja wykonuje tylko jedno wywołanie

• Proces, w którym funkcja wykonuje wywołania równoległe

• Proces, w którym funkcja wywołuje samą siebie

• Proces, w którym funkcja wykonuje wywołania iteracyjne

Jakie są typy rekurencji?

• Bezpośrednia, pośrednia, liniowa, ogonowa

• Ogonowa, nieliniowa, zagnieżdżona, nieskończona

• Liniowa, drzewiasta, zagnieżdżona, nieliniowa

• Bezpośrednia, wielokrotna, zagnieżdżona, ze zwrotem

Jakie są zalety rekurencji bezpośredniej?

• Optymalizuje rekurencyjne wywołania funkcji

• Prostota implementacji; łatwa do zrozumienia

• Może prowadzić do nadmiernego zużycia stosu wywołań dla dużych danych wejściowych

• Umożliwia rozwiązanie złożonych problemów poprzez podział na mniejsze funkcje

Jakie są wady rekurencji wielokrotnej?

• Nieefektywna dla dużych danych wejściowych, może szybko wyczerpać stos wywołań

• Może prowadzić do eksplozji liczby wywołań rekurencyjnych i nadmiernego zużycia pamięci

• Pozwala na rozwiązanie złożonych problemów, które naturalnie dzielą się na wiele podproblemów

• Umożliwia eleganckie rozwiązanie problemów rozgałęziających się na wiele ścieżek

Jakie jest równanie złożoności czasowej dla rekurencji ogonowej?

• O(1)

• O(n^2)

• O(n log n)

• O(n)

Jaką złożoność czasową ma funkcja rekurencyjna T(n) = T(n-1) + 1?

• O(n)

• O(n^2)

• O(n log n)

• O(n^3)

Jaka jest złożoność czasowa funkcji rekurencyjnej T(n) = 2T(n-1) + 1?

• O(2^n)

• O(n^2)

• O(n)

• O(n log n)

Jaką złożoność czasową ma funkcja rekurencyjna T(n) = T(n-1) + n?

• O(2^n)

• O(n log n)

• O(n)

• O(n^2)

Co oznacza parametr a w rekurencji dzielonej?

• Rozmiar każdego z podproblemów

• Stopień wielomianu

• Liczba podproblemów na każdym poziomie rekurencji

• Dodatkowy koszt związany z podziałem problemu

Jaka jest złożoność czasowa funkcji rekurencyjnej T(n) = 2T(n/2) + n log n?

• O(n log n)

• O(n)

• O(n^2)

• O(2^n)