Rozważ stary, dobrze znany problem :
W matematyce największy wspólny dzielnik (gcd)… dwóch lub więcej niezerowych liczb całkowitych jest największą dodatnią liczbą całkowitą, która dzieli liczby bez reszty.
Definicja gcd jest zaskakująco prosta:
gdzie mod jest operatorem modulo (czyli resztą po dzieleniu liczb całkowitych).
W języku angielskim ta definicja mówi, że największym wspólnym dzielnikiem dowolnej liczby i zerem jest ta liczba, a największy wspólny dzielnik dwóch liczb m i n to największy wspólny dzielnik liczby n, a reszta po podzieleniu m przez n .
Jeśli chcesz wiedzieć, dlaczego to działa, zobacz artykuł w Wikipedii na temat algorytmu Euklidesa .
Obliczmy jako przykład gcd (10, 8). Każdy krok jest równy temu tuż przed nim:
- gcd (10, 8)
- gcd (10, 10 mod 8)
- gcd (8; 2)
- gcd (8, 8 mod 2)
- gcd (2; 0)
- 2
W pierwszym kroku 8 nie jest równe zeru, więc obowiązuje druga część definicji. 10 mod 8 = 2, ponieważ 8 przechodzi do 10 raz z resztą 2. W kroku 3 druga część ma zastosowanie ponownie, ale tym razem 8 mod 2 = 0, ponieważ 2 dzieli 8 bez reszty. W kroku 5 drugi argument to 0, więc odpowiedź to 2.
Czy zauważyłeś, że gcd pojawia się po lewej i prawej stronie znaku równości? Matematyk powiedziałby, że ta definicja jest rekurencyjna, ponieważ wyrażenie, które definiujesz, powtarza się w swojej definicji.
Definicje rekurencyjne wydają się być eleganckie. Na przykład rekurencyjna definicja sumy listy to
sum l =
if empty(l)
return 0
else
return head(l) + sum(tail(l))
gdzie headjest pierwszym elementem listy i tailpozostałą częścią listy. Zauważ, że sumna końcu powtarza się w definicji.
Może wolisz zamiast tego maksymalną wartość na liście:
max l =
if empty(l)
error
elsif length(l) = 1
return head(l)
else
tailmax = max(tail(l))
if head(l) > tailmax
return head(l)
else
return tailmax
Możesz zdefiniować mnożenie nieujemnych liczb całkowitych rekurencyjnie, aby przekształcić je w serię dodawania:
a * b =
if b = 0
return 0
else
return a + (a * (b - 1))
Jeśli ten fragment dotyczący przekształcania mnożenia w serię dodatków nie ma sensu, spróbuj rozwinąć kilka prostych przykładów, aby zobaczyć, jak to działa.
Sortowanie przez scalanie ma piękną rekurencyjną definicję:
sort(l) =
if empty(l) or length(l) = 1
return l
else
(left,right) = split l
return merge(sort(left), sort(right))
Definicje rekurencyjne są wszędzie, jeśli wiesz, czego szukać. Zauważ, że wszystkie te definicje mają bardzo proste przypadki podstawowe, np. Gcd (m, 0) = m. Przypadki rekurencyjne zmniejszają problem, aby przejść do łatwych odpowiedzi.
Dzięki temu zrozumieniu możesz teraz docenić inne algorytmy w artykule Wikipedii na temat rekurencji !
