Nauka / Rekurencja

Rekurencja

Definicje rekurencyjne, liczba wywołań, drzewo wywołań, przejście na iterację, memoizacja.

Rozszerzony

Teoria, wzory i przykłady

Jak działa rekurencja

Funkcja rekurencyjna wywołuje samą siebie dla mniejszego problemu i ma warunek zakończenia (przypadek bazowy).

n!={1n=0n⋅(n−1)!n>0Fn={nn≤1Fn−1+Fn−2n>1n! = \begin{cases}1 & n=0\\ n\cdot(n-1)! & n>0\end{cases}\qquad F_n=\begin{cases}n & n\le1\\ F_{n-1}+F_{n-2} & n>1\end{cases}

Śledzenie wywołań

Rozpisuj wywołania krok po kroku, wpisując argumenty. Przykład funkcji z arkusza CKE 2026:

A(m,n)={mn=1A(2m,n2)n>1, n parzyste2⋅A(m,n−12)+mn>1, n nieparzysteA(m,n)=\begin{cases} m & n=1\\ A(2m,\tfrac n2) & n>1,\ n\ \text{parzyste}\\ 2\cdot A(m,\tfrac{n-1}2)+m & n>1,\ n\ \text{nieparzyste}\end{cases}

A(3,9)A(3,9): kolejne wywołania A(3,4)A(3,4), A(6,2)A(6,2), A(12,1)A(12,1) — 3 wywołania rekurencyjne, wynik 2⋅12+3=272\cdot12+3=27.

Obserwacja: drugi argument jest za każdym razem (prawie) dzielony przez 2 — liczba wywołań ma rząd log⁡2n\log_2 n. Dla n=2kn=2^k wywołań jest kk; dla n=2k−1n=2^k-1 (same nieparzyste kroki) wywołań jest k−1k-1.

Wzór: ta funkcja oblicza po prostu iloczyn, A(m,n)=m⋅nA(m,n)=m\cdot n (to mnożenie „rosyjskich chłopów”: dla parzystego nn podwajamy mm i dzielimy nn przez 2, dla nieparzystego dodajemy mm). Sprawdź: A(2m,n2)=2m⋅n2=mnA(2m,\tfrac n2)=2m\cdot\tfrac n2=mn oraz 2⋅m⋅n−12+m=mn2\cdot m\cdot\tfrac{n-1}2+m=mn. W zadaniach maturalnych wzór najłatwiej zauważyć, rozpisując kilka małych przykładów.

Rekurencja a iteracja

Każdą rekurencję ogonową można zamienić na pętlę. Rekurencję wielokrotną (Fibonacci) warto przyspieszyć memoizacją (zapamiętywaniem wyników) — z wykładniczej O(2n)O(2^n) do liniowej O(n)O(n).

def fib(n, pamiec={}):
    if n <= 1:
        return n
    if n not in pamiec:
        pamiec[n] = fib(n - 1) + fib(n - 2)
    return pamiec[n]

Wieże Hanoi

T(n)=2T(n−1)+1 ⇒ T(n)=2n−1T(n)=2T(n-1)+1\ \Rightarrow\ T(n)=2^n-1 ruchów.

Typowe błędy

  • Brak warunku zakończenia ⇒ nieskończona rekurencja.
  • Pomylenie „liczby wywołań rekurencyjnych” z „wartością funkcji”.

Średnie zadania

Średnie3 pkt

Rekurencja. Dana jest zdefiniowana rekurencyjnie funkcja A(m,n)A(m,n), gdzie mm i nn są dodatnimi liczbami całkowitymi:

A(m,n)={mn=1A(2m,n2)n>1 i n parzyste2⋅A(m,n−12)+mn>1 i n nieparzysteA(m,n)=\begin{cases} m & n=1\\ A\left(2m,\tfrac n2\right) & n>1\ \text{i}\ n\ \text{parzyste}\\ 2\cdot A\left(m,\tfrac{n-1}2\right)+m & n>1\ \text{i}\ n\ \text{nieparzyste}\end{cases}

Obliczenie A(3,9)A(3,9) wprost z definicji wymaga trzech wywołań rekurencyjnych: A(3,4)A(3,4), A(6,2)A(6,2), A(12,1)A(12,1), bo A(3,9)=2⋅A(3,4)+3=2⋅A(6,2)+3=2⋅A(12,1)+3=2⋅12+3=27A(3,9)=2\cdot A(3,4)+3=2\cdot A(6,2)+3=2\cdot A(12,1)+3=2\cdot12+3=27.

Podaj liczbę wywołań rekurencyjnych funkcji AA oraz wypisz wywołania rekurencyjne (w ostatnim wierszu podaj tylko liczbę wywołań) dla:

mmnn
3399 (przykład: 3 wywołania)
252^5252^5
10101515
112100+12^{100}+1
Średnie1 pkt

Dla funkcji A(m,n)A(m,n) z zadania 1.1 podaj wartości:

mmnnA(m,n)A(m,n)
11777777?
2⋅1062\cdot10^6256⋅106256\cdot10^6?

(Wynik możesz zapisać z użyciem mnożenia i potęgowania.)

Średnie3 pkt

Funkcja rekurencyjna. Dana jest funkcja przestaw, której parametrem jest nieujemna liczba całkowita:

przestaw(n):
    r ← n mod 100
    a ← r div 10
    b ← r mod 10
    n ← n div 100
    jeżeli n > 0
        w ← a + 10*b + 100*przestaw(n)
    w przeciwnym razie
        jeżeli a > 0
            w ← a + 10*b
        w przeciwnym razie
            w ← b
    wynikiem jest w

(mod — reszta z dzielenia, div — dzielenie całkowite.) Uzupełnij tabelę: wynik przestaw(n) oraz liczba wywołań funkcji przestaw łącznie z pierwszym wywołaniem.

nnwynikliczba wywołań
3164981346893
43657688??
154005710??
998877665544321??
Średnie2 pkt

Niech nn będzie liczbą kk-cyfrową, gdzie k>0k>0. Liczba wywołań funkcji przestaw (z zadania 1.1) w zależności od kk jest równa — oceń prawdziwość zapisów:

Trudne zadania

Gotowy na sprawdzian z działu?
Wygeneruj krótki test z tego działu w generatorze.
Test działowy