1 Treści multimedialne - kodowanie, przetwarzanie, prezentacja Odtwarzanie treści multimedialnychAndrzej Majkowski informatyka +

2 TYTUŁ: Rekurencja i jej zastosowanie AUTORZY: Joanna Paćkowska, Ewelina Malińska

3 Definicja rekurencji Rekurencja, zwana także rekursją (ang. recursion, z łac. recurrere, przybiec z powrotem) to w logice, programowaniu i w matematyce odwoływanie się np. funkcji lub definicji do samej siebie. Rekurencja jest podstawową techniką wykorzystywaną w funkcyjnych językach programowania np. w języku C++

4 Przykładem rekurencji może być: ciąg Fibonacciego, Przykłady rekurencji Przykładem rekurencji może być: ciąg Fibonacciego, dywan Sierpińskiego, płatek Kocha

5 Ciąg Fibonacciego Przykładem algorytmu rekurencyjnego jest obliczanie elementów ciągu Fibonacciego. Fibonacci (Leonardo z Pizy) – był włoskim matematykiem, twierdził, że „matematyka jest wszędzie – w całym otaczającym nas świecie...” Leonardo Fibonacci ur. ok r r.

6 Ciąg Fibonacciego - definicjaCiąg Fibonacciego – ciąg liczb naturalnych określony rekurencyjnie w sposób następujący: Pierwszy wyraz jest równy 0, drugi jest równy 1, każdy następny jest sumą dwóch poprzednich. Formalnie:

7 Ciąg Fibonacciego - Liczba Φ(fi)Dzieląc wyraz przez poprzedni, otrzymuje liczbę równą Φ(fi) – znaną z tzw. Złotego podziału 233/144 => 1,618 Złoty podział odcinka jest to wewnętrzny podział tego odcinka na dwie nierówne części tak, aby stosunek odcinka a do jego większej części x był równy stosunkowi części x do części mniejszej (a-x), tj. aby a/x = x/(a-x) a/x = Φ = 1, x/a = Φ = 0,618

8 Ciąg Fibonacciego – Złoty PodziałDzięki liczbom oraz dzięki złotemu podziałowi Fibonacci skonstruował też spiralę

9 Ciąg Fibonacciego w przyrodzieFibonacci nawet nie zdawał sobie sprawy, że wzmianka o ciągu który umieścił na marginesie księgi „Liber Abaci ” opisuje tak wiele zjawisk w przyrodzie min. układ łusek szyszki; łusek ananasa; ziaren na tarczy słonecznika; muszli łodzika (morskiego mięczaka) gałęzi na łodydze.

10 Ciąg Fibonacciego w przyrodzieGdyby przyjrzeć się z bliska łuskom szyszki, ananasa, ziarnom na tarczy słonecznika czy kwiatom kalafiora – można zauważyć, że układają się spiralnie, a ich przyrost również podlega regułom słynnego ciągu – wystarczy policzyć liczbę prawo- i lewoskrętnych spiral – pestki słonecznika czy różyczki kalafiora ułożone są wzdłuż logarytmicznych krzywych, które grupami biegną w różnych kierunkach, na przykład 34 lewoskrętne i 55 prawoskrętnych. A 34 i 55 to nic innego, jak liczby Fibonacciego.

11 Ciąg Fibonacciego w przyrodzie

12 Ciąg Fibonacciego w przyrodzie

13 Rekurencja w przyrodzieW przyrodzie spotykamy obiekty, które są podobne same do siebie - jeśli popatrzymy na cząstkę kalafiora, to wygląda ona jak cały kalafior. Rysunki powstające w podobny sposób nazywamy fraktalami. Jak je rysować? Najczęściej wykorzystujemy do tego rekurencję.

14 Dywan Sierpińskiego Dywan Sierpińskiego to fraktal otrzymany z kwadratu za pomocą podzielenia go na dziewięć (3 x 3) mniejszych kwadratów, usunięcia środkowego kwadratu i ponownego rekurencyjnego zastosowania tej samej procedury do każdego z pozostałych ośmiu kwadratów.

15 Dywan Sierpińskiego po 6 krokach

16 Płatek Kocha Płatek Kocha powstaje z odcinka, poprzez podzielenie go na 3 części i zastąpienie środkowej ząbkiem (o ramieniu długości równej 1/3 odcinka) takim, że wraz z usuwaną częścią tworzy trójkąt równoboczny. Krok ten jest powtarzany w nieskończoność dla każdego fragmentu odcinka.

17