Chotkos's Blog

Programowanie i informatyka

Rekurencja

„Aby zrozumieć rekurencję, trzeba najpierw zrozumieć rekurencję”

Słowa, które napisałem wyżej, mogą się wydać bezsensowne, ale na tym właśnie polega rekurencja. Zazwyczaj występuje w funkcjach, w których musimy robić coś wgłąb np. jakiegoś grafu, jest to eleganckie i nowoczesne rozwiązanie, chociaż dla niektórych trudne do zrozumienia.

Najprościej rzecz ujmując rekurencja jest wtedy, kiedy funkcja f(x) uruchamia funkcję f(x). Najlepiej zobrazuje to przykład.

funkcja(X)

{

  • powiększ a o 1
  • wypisz a
  • czy a>5 ?
  1. jeśli nie to uruchom funkcja(X)
  2. jeśli tak, to wypisz „nareszcie a=”  a.
  • napisz „costam”

}

kiedy już to przetłumaczycie na jakiś język programowania otrzymacie w konsoli:

1
2
3
4
5
nareszcie a=5
costam
costam
costam
costam
costam

Mogło was zastanowić dlaczego mamy tutaj 5x napisane „costam” i jest to na końcu a nie na początku. Pamiętaj że funkcja po zakończeniu serii rekurencji zacznie zamykać te funkcje które zaczęła wcześniej – myślę, że lepiej zobrazuje to rysunek:

wykres

kolory z wykresu odpowiadają kolorom w kodzie, czerwona kreska pionowa oznacza rekurencyjne uruchomienie funkcji. Kolorem niebieskim zaznaczyłem, gdzie kończy się dana funkcja. Wykres należy śledzić od dolnej czarnej kreski na której ustawiłem tą „piramidę”.

Warto poćwiczyć rekurencję na jakichś zadaniach np. na mainie, u mnie powinno się coś takiego niedługo pojawić w sprawdzarce – jak tylko wpadnę na dobry pomysł 😉

Reklamy

Styczeń 24, 2010 - Posted by | Algorytmy, Programowanie |

Brak komentarzy.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s

%d blogerów lubi to: