Iteracja

Iteracja – powtarzanie określonej operacji lub zestawu operacji w sposób określony przez warunek kontrolny. Termin ten występuje w wielu dziedzinach, w szczególności w matematyce oraz w programowaniu, gdzie jest podstawowym mechanizmem realizacji powtarzalnych procesów.

Definicja

W najogólniejszym ujęciu iteracja polega na wykonywaniu kolejnych kroków, z których każdy zależy od wyniku poprzedniego, aż do spełnienia określonego warunku zakończenia. W praktyce informatycznej najczęściej realizuje się ją przy pomocy pętli (np. for, while, do‑while) lub poprzez rekurencję.

Rodzaje iteracji

Iteracja w programowaniu

• Pętla for – najczęściej stosowana przy znanej z góry liczbie powtórzeń. Przykład w C++:

  for (int i = 0; i < n; ++i) {
      // ciało pętli
  }

• Pętla while – używana, gdy liczba iteracji zależy od warunku dynamicznego.

  while (warunek) {
      // ciało pętli
  }

• Pętla do‑while – gwarantuje przynajmniej jedną iterację.

  do {
      // ciało pętli
  } while (warunek);

• Iteracja w językach funkcyjnych – realizowana za pomocą funkcji wyższego rzędu, np. map, filter w Pythonie czy Haskellu.
• Iteracja równoległa – wykonywanie wielu iteracji jednocześnie przy użyciu wątków lub procesów, co jest istotne w kontekście złożoności obliczeniowej.

Iteracja w matematyce

W matematyce iterację stosuje się do budowania ciągów i badania ich własności. Typowe przykłady:

• Ciągi rekurencyjne – np. ciąg Fibonacciego definiowany jako aₙ = aₙ₋₁ + aₙ₋₂ z warunkami początkowymi.
• Iteracje funkcji – wielokrotne stosowanie tej samej funkcji do wyniku poprzedniego, np. x_{n+1}=f(x_n). Badanie takiego procesu prowadzi do teorii dynamicznej i chaosu.
• Metoda Newtona – iteracyjne przybliżanie pierwiastka równania f(x)=0 poprzez formułę x_{n+1}=x_n - f(x_n)/f'(x_n).
• Algorytmy przybliżone, np. metoda gradientu w optymalizacji, które polegają na iteracyjnym poprawianiu przybliżenia rozwiązania.

Iteracja a rekurencja

Choć iteracja i rekurencja realizują podobny cel – powtarzalność – różnią się pod względem realizacji technicznej. Iteracja zwykle wymaga stałej ilości pamięci (np. zmienna indeksująca), podczas gdy rekurencja wykorzystuje stos wywołań, co może prowadzić do większego zużycia pamięci (stack overflow) lecz jest bardziej naturalna przy problemach o strukturze drzewiastej.

Zastosowania praktyczne

• Przetwarzanie danych – np. iteracyjne przeglądanie rekordów w bazie danych, sortowanie (algorytmy sortowania bąbelkowe, quicksort).
• Grafika komputerowa – iteracyjne renderowanie sceny, algorytmy ray tracingu.
• Uczenie maszynowe – iteracyjne optymalizacje wag w sieciach neuronowych (algorytm gradientu prostego, metoda Adam).
• Systemy operacyjne – pętle główne (main loop) obsługujące zdarzenia.

Powiązane pojęcia

W encyklopedii można także przeczytać o:

• algorytmie
• pętli
• rekurencji
• złożoności obliczeniowej
• programowaniu
• dynamice układów
• metodzie Newtona

Przykład iteracji w języku Python

# Zliczanie sumy liczb od 1 do n
def suma(n):
    total = 0
    i = 1
    while i <= n:
        total += i
        i += 1
    return total

print(suma(10))  # wynik: 55

Historia

Pojęcie iteracji wywodzi się z klasycznej logiki i matematyki, gdzie już w starożytności rozważano powtarzalne procesy (np. algorytmy egipskie). W informatyce termin stał się powszechny wraz z rozwojem pierwszych języków programowania w latach 50. i 60. XX wieku, zwłaszcza w językach FORTRAN i LISP.

W literaturze

Klasyczne pozycje omawiające iterację to między innymi:

• Donald Knuth, The Art of Computer Programming – tom 1, rozdział poświęcony pętlom i iteracjom.
• Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein, Introduction to Algorithms – opis algorytmów iteracyjnych.
• James S. Munkres, Analysis on Manifolds – zastosowanie iteracji w analizie matematycznej.

Patrz także

Wzór rekurencyjny, cykle, algorytmy genetyczne, metody numeryczne.