Programowanie dynamiczne – technika projektowania algorytmów polegająca na rozwiązywaniu podproblemów i zapamiętywaniu ich wyników. W technice tej, podobnie jak w metodzie dziel i zwyciężaj, problem dzielony jest na mniejsze podproblemy. Wyniki rozwiązywania podproblemów są jednak zapisywane w tabeli, dzięki czemu w przypadku natrafienia na ten sam podproblem nie trzeba go ponownie rozwiązywać.

Wykorzystując programowanie dynamiczne można zastosować metodę zstępującą z zapamiętywaniem lub metodę wstępującą.

• Metoda zstępująca z zapamiętywaniem polega na rekurencyjnym wywoływaniu funkcji z zapamiętywaniem wyników. Metoda ta jest podobna do metody dziel i zwyciężaj – różni się od niej tym, że jeśli rozwiązanie danego problemu jest już w tabeli z wynikami, to należy je po prostu stamtąd odczytać.
• Metoda wstępująca polega na rozwiązywaniu wszystkich możliwych podproblemów, zaczynając od tych o najmniejszym rozmiarze. Wówczas w momencie rozwiązywania podproblemu na pewno są już dostępne rozwiązania jego podproblemów. W tym podejściu nie zużywa się pamięci na rekurencyjne wywołania funkcji. Może się jednak okazać, że część podproblemów została rozwiązana nadmiarowo (nie były one potrzebne do rozwiązania głównego problemu).

Ten artykuł opisuje algorytm zachłanny rozwiązujący problem wydawania reszty. Algorytm ten polega na wybieraniu zawsze największej dostępnej monety, tzn. takiej, która nie jest większa od kwoty pozostałej do wydania.

Algorytm nie zawsze znajduje rozwiązanie optymalne. Przykładowo, dla zbioru nominałów {1, 3, 4} i kwoty 6 algorytm użyje najpierw monety o nominale 4 (pozostaje do wydania kwota 2), potem monety o nominale 1 (pozostaje kwota 1) i jeszcze raz monety o nominale 1. Łącznie algorytm użyje więc trzech monet, podczas gdy rozwiązanie optymalne wymaga użycia tylko dwóch (dwie monety o nominale 3).

Rekurencja (inaczej rekursja) – odwołanie się funkcji lub definicji do samej siebie. Mówiąc inaczej, podejście rekurencyjne polega na tym, że rozwiązanie problemu wyraża się za pomocą rozwiązania tego samego problemu dla mniejszych danych wejściowych. Stosowanie rekurencji jest charakterystyczne dla algorytmów projektowanych metodą dziel i zwyciężaj.

Typowym problemem, dla którego można zastosować rekurencję, jest obliczanie silni. Przypomnijmy, że silnia z n jest zdefiniowana jako n!=1×2×…×n. Funkcja ta może być równoważnie zapisana jako:

n!=(n−1)!×n, dla n>0,
n!=1, dla n=0.

W powyższym przykładzie górny wiersz jest ogólnym równaniem rekurencji, zaś dolny wiersz jest wartością brzegową. W języku C++ powyższa funkcja byłaby zapisana w poniższy sposób.

int silnia(int n)
{
    if (n > 0)
    {
        return n * silnia(n-1);
    }
    else
    {
        return 1;
    }
};

Przekształcenie postaci rekurencyjnej funkcji do postaci zwartej (tzn. takiej, która nie zawiera odwołania do samej siebie) jest określane jako rozwiązanie rekurencji. Metody rozwiązywania rekurencji są dostępne między innymi w książkach podanych w bibliografii.

Algorytmy stosujące rekurencję są zazwyczaj proste w implementacji. Jednocześnie wiążą się one z pewnymi problemami. Przy podejściu rekurencyjnym ta sama funkcja jest wywoływana wielokrotnie, co zużywa pamięć operacyjną (w skrajnych przypadkach może to spowodować przepełnienie stosu).