Silnia i potęgowanie rekurencyjne

1. Silnia (factorial)

Silnia liczby n (oznaczana n!) to iloczyn wszystkich liczb całkowitych od 1 do n.

Definicja matematyczna:

0! = 1  (przypadek bazowy)
n! = n × (n-1) × (n-2) × ... × 2 × 1  dla n ≥ 1

Rekurencyjnie:

0! = 1
n! = n × (n-1)!  dla n ≥ 1

Przykłady:

0! = 1
1! = 1
2! = 2 × 1 = 2
3! = 3 × 2 × 1 = 6
4! = 4 × 3 × 2 × 1 = 24
5! = 5 × 4 × 3 × 2 × 1 = 120
10! = 3,628,800
20! = 2,432,902,008,176,640,000

2. Silnia – implementacja rekurencyjna

2.1. Podstawowa rekurencja

Wynik:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120

2.2. Wizualizacja wywołań

Wynik:

→ factorial(4)
  → factorial(3)
    → factorial(2)
      → factorial(1)
        → factorial(0)
        ← zwracam 1
      ← zwracam 1
    ← zwracam 2
  ← zwracam 6
← zwracam 24

2.3. Złożoność

  • Czasowa: O(n) – n wywołań
  • Pamięciowa: O(n) – stos wywołań

3. Silnia – implementacja iteracyjna

Złożoność:

  • Czasowa: O(n)
  • Pamięciowa: O(1) ← Lepsze niż rekurencja!

4. Silnia – rekurencja ogonowa

Uwaga: Python nie optymalizuje tail recursion, więc to nie daje korzyści!

Konwersja na iterację:

5. Porównanie wydajności – silnia

Przykładowe wyniki:

--- 100! ---
Rekurencja     : 0.000052s (cyfr: 158)
Iteracja       : 0.000018s (cyfr: 158)
Ogonowa        : 0.000046s (cyfr: 158)

--- 500! ---
Rekurencja     : 0.000421s (cyfr: 1135)
Iteracja       : 0.000124s (cyfr: 1135)
Ogonowa        : 0.000398s (cyfr: 1135)

Wniosek: Iteracja najszybsza!

6. Zastosowania silni

6.1. Permutacje (n!)

6.2. Kombinacje (n wybierz k)

6.3. Szereg Taylora (e^x)

7. Potęgowanie (a^n)

Definicja matematyczna:

a^0 = 1  (przypadek bazowy)
a^n = a × a^(n-1)  dla n ≥ 1

8. Potęgowanie – rekurencja naiwna

Złożoność:

  • Czasowa: O(n)
  • Pamięciowa: O(n)

9. Potęgowanie – iteracja

Złożoność:

  • Czasowa: O(n)
  • Pamięciowa: O(1)

10. Szybkie potęgowanie – O(log n)!

Idea:

a^8 = (a^4)^2 = ((a^2)^2)^2

Zamiast 8 mnożeń – tylko 3!

Algorytm:

a^n = 1                    jeśli n = 0
a^n = a^(n/2) × a^(n/2)    jeśli n parzyste
a^n = a × a^(n-1)          jeśli n nieparzyste

10.1. Rekurencyjna implementacja

10.2. Iteracyjna implementacja

Wizualizacja dla szybkie_potegowanie_iter(2, 10):

Krok 1: n=10 (parzyste), wynik=1, podstawa=2
        n=5, wynik=1, podstawa=4

Krok 2: n=5 (nieparzyste), wynik=1, podstawa=4
        wynik=1*4=4
        n=2, wynik=4, podstawa=16

Krok 3: n=2 (parzyste), wynik=4, podstawa=16
        n=1, wynik=4, podstawa=256

Krok 4: n=1 (nieparzyste), wynik=4, podstawa=256
        wynik=4*256=1024
        n=0, wynik=1024

Koniec: 1024

Złożoność:

  • Czasowa: O(log n) ← ZNACZNIE LEPIEJ!
  • Pamięciowa: O(1) dla iteracji, O(log n) dla rekurencji

11. Porównanie metod potęgowania

Przykładowe wyniki:

--- 2^1000 ---
Naiwna rek     : RecursionError
Iteracja       : 0.000124s (cyfr: 302)
Szybka rek     : 0.000018s (cyfr: 302)
Szybka iter    : 0.000012s (cyfr: 302) ← NAJSZYBSZA!

12. Potęgowanie modularne (a^n mod m)

Przydatne w kryptografii (RSA):

Zastosowanie: RSA, testy pierwszości, haszowanie

13. Porównanie: silnia vs potęgowanie

Aspekt Silnia (n!) Potęgowanie (a^n)
Wzrost Bardzo szybki Zależy od a
Naiwna rekurencja O(n) O(n)
Iteracja O(n) O(n)
Szybki algorytm Brak O(log n)
Typowe zastosowanie Kombinatoryka Kryptografia, algebra

Przykład wzrostu:

Wynik:

n= 1: 1! =       1, 2^1 =     2
n= 2: 2! =       2, 2^2 =     4
n= 3: 3! =       6, 2^3 =     8
n= 4: 4! =      24, 2^4 =    16
n= 5: 5! =     120, 2^5 =    32
n= 6: 6! =     720, 2^6 =    64
n= 7: 7! =   5,040, 2^7 =   128
n= 8: 8! =  40,320, 2^8 =   256
n= 9: 9! = 362,880, 2^9 =   512
n=10: 10! = 3,628,800, 2^10 = 1,024

Silnia rośnie dużo szybciej!

14. Ćwiczenia

Zadanie 1: Podwójna silnia

n!! = n × (n-2) × (n-4) × ... × 1

Rozwiązanie rekurencyjne

Zadanie 2: Potęga ujemna

Zaimplementuj a^n dla n < 0 (wynik to 1/a^|n|)

15. Podsumowanie

Silnia (n!):

  • Rekurencja: O(n) czas, O(n) pamięć
  • Iteracja: O(n) czas, O(1) pamięć ← Lepsze
  • Rośnie BARDZO szybko (10! = 3.6M)
  • Zastosowania: kombinatoryka, szeregi

Potęgowanie (a^n):

  • Naiwne: O(n) czas
  • Szybkie: O(log n) czas ← Ogromna różnica!
  • Iteracja lepsza niż rekurencja (w Pythonie)
  • Zastosowania: kryptografia, algebramathematyka

Kluczowe wnioski:

  1. Iteracja > Rekurencja (w Pythonie)
  2. Szybkie potęgowanie – O(log n) zamiast O(n)
  3. Python nie optymalizuje tail recursion
  4. Silnia rośnie szybciej niż potęga

Porównanie czasów dla 2^1000:

  • Naiwna rekurencja: RecursionError
  • Iteracja naiwna: ~0.0001s
  • Szybka iteracja: ~0.00001s ← 10x szybciej!

Co dalej warto poznać:

  • Programowanie dynamiczne
  • Kombinatoryka i permutacje
  • Kryptografia (RSA, Diffie-Hellman)
  • Testy pierwszości (Fermat, Miller-Rabin)
Wróć do spisu lekcji