Rekurencja — jak działa, przykłady i przypadki bazowe

Rekurencja w matematyce oznacza definiowanie funkcji, ciągu lub procesu za pomocą mniejszych przypadków tej samej idei. Definicja rekurencyjna działa tylko wtedy, gdy zawiera przypadek bazowy oraz regułę, która prowadzi każdy nowy przypadek w stronę tego przypadku bazowego.

Jeśli potrzebujesz tylko najważniejszej idei, to jest ona taka: rekurencja przestaje być użyteczna w chwili, gdy reguła przechodzenia do mniejszego kroku nie prowadzi już do poprawnego punktu zatrzymania.

Co oznacza rekurencja w matematyce

Definicja rekurencyjna nie wypisuje osobno każdego przypadku. Zamiast tego podaje punkt startowy oraz regułę budowania większych przypadków z mniejszych.

To różni się od wzoru jawnego. Wzór jawny podaje odpowiedź na podstawie argumentu w jednym wyrażeniu. Definicja rekurencyjna sprowadza problem krok po kroku, aż dotrze do przypadku, który jest już znany.

Dlaczego przypadek bazowy jest konieczny

Przypadek bazowy to punkt zatrzymania. Bez niego definicja odwołuje się do coraz mniejszych przypadków i nigdy się nie kończy.

Przypadek bazowy musi też pasować do wybranej reguły. Jeśli krok rekurencyjny sprowadza z $n$ do $n-1$, to przypadek bazowy musi być osiągalny w tym schemacie dla dopuszczonych argumentów.

Przykład: rekurencyjna definicja silni

Silnia jest standardowym przykładem definicji rekurencyjnej. Dla liczb całkowitych $n \ge 0$ definiujemy silnię przez

$$0! = 1$$

oraz dla $n \ge 1$,

$$n! = n(n-1)!$$

Tutaj $0! = 1$ jest przypadkiem bazowym, a $n! = n(n-1)!$ jest krokiem rekurencyjnym.

Aby obliczyć $4!$, sprowadzamy wyrażenie dalej, aż pojawi się przypadek bazowy:

$$4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0!$$

Teraz stosujemy przypadek bazowy $0! = 1$:

$$4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$$

To jest pełny schemat rekurencji: sprowadzenie do mniejszego przypadku, dojście do przypadku bazowego, a następnie obliczenie wyniku z powrotem dla pierwotnego pytania.

Rekurencja a równanie rekurencyjne

Rekurencja jest pojęciem szerszym. Równanie rekurencyjne to rekurencyjna reguła dla ciągu, w której każdy wyraz zależy od wcześniejszych wyrazów.

Na przykład ciąg Fibonacciego jest określony równaniem rekurencyjnym, ponieważ każdy wyraz definiuje się na podstawie wcześniejszych. Silnia także jest rekurencyjna, ale zwykle przedstawia się ją jako rekurencyjną definicję funkcji, a nie jako równanie rekurencyjne dla ciągu.

Częste błędy w rekurencji

Pominięcie przypadku bazowego

Jeśli nie ma przypadku bazowego, definicja się nie kończy.

Użycie kroku, który nie prowadzi do mniejszego przypadku

Jeśli krok rekurencyjny nie prowadzi w stronę przypadku bazowego, proces może zapętlić się bez końca albo stać się nieokreślony dla niektórych argumentów.

Pominięcie warunku przy regule

W przykładzie z silnią reguła $n! = n(n-1)!$ jest stosowana dla $n \ge 1$. Ten warunek ma znaczenie. Bez niego można by próbować stosować regułę tam, gdzie definicja nie była zamierzona.

Zakładanie, że rekurencja to tylko pojęcie z programowania

Rekurencja pojawia się w matematyce na długo przed kodem. To sposób definiowania funkcji, ciągów i zbiorów przez odwołanie do mniejszych przypadków. Następnie często używa się indukcji, aby udowadniać twierdzenia o takich definicjach rekurencyjnych.

Kiedy rekurencja jest przydatna

Rekurencja jest przydatna wtedy, gdy problem naturalnie rozkłada się na mniejsze wersje samego siebie. Widać to przy silni, ciągach typu Fibonacciego, rekurencyjnie definiowanych zbiorach i wielu algorytmach.

Jest szczególnie pomocna wtedy, gdy mniejszy przypadek ma tę samą strukturę co przypadek wyjściowy. Jeśli mniejszy przypadek nie jest naprawdę problemem tego samego rodzaju, rekurencja zwykle nie jest właściwym narzędziem.

Szybki test poprawnej definicji rekurencyjnej

Zadaj sobie dwa pytania:

1. Czy mam przypadek bazowy?
2. Czy każdy krok rekurencyjny przybliża mnie do niego?

Jeśli na któreś z nich odpowiedź brzmi nie, definicję trzeba poprawić.

Spróbuj podobnego zadania

Zdefiniuj ciąg przez

$$a_1 = 2, \qquad a_n = a_{n-1} + 3 \quad \text{for } n \ge 2$$

Następnie wyznacz $a_2$, $a_3$ i $a_4$. To szybki sposób, aby poćwiczyć rozpoznawanie przypadku bazowego i kroku rekurencyjnego w nowym kontekście.