Algorytm in situ
Algorytm in situ (łac. in situ – w miejscu) to rodzaj algorytmu, który wymaga stałej ilości pamięci komputera, niezależnej od wielkości danych wejściowych. Wszystkie obliczenia niezbędne do uzyskania wyniku są realizowane w pamięci, do której dane zostały załadowane.
Algorytmy tego typu były cenione nie tylko w erze, gdy komputery dysponowały ograniczoną pamięcią operacyjną, ale również w dzisiejszych czasach, szczególnie w kontekście przetwarzania dużych zbiorów danych, jak na przykład w obliczeniach numerycznych.
Rekurencja
Wiele algorytmów rekurencyjnych, w których liczba wywołań rekurencyjnych zależy od danych, nie potrafi działać w miejscu. Jest to spowodowane tym, że historia wywołań procedur (tzw. „drzewo rekurencji”) musi być przechowywana na stosie. Przykładem takiego algorytmu jest sortowanie szybkie.
Jednakże istnieją wyjątki, w których algorytmy, mimo że realizują wielokrotne wywołania rekurencyjne, można przekształcić matematycznie do formy, w której wszystkie te wywołania stają się ogonowe. W takim przypadku kompilator ma możliwość uniknięcia przechowywania pełnej historii wywołań na stosie. Styl programowania, który często wykorzystuje rekurencję ogonową, jest szczególnie przydatny i powszechnie stosowany w programowaniu funkcyjnym.
