Czy „indukcyjne” i „rekurencyjne” mają bardzo podobne znaczenia?

Czy „indukcyjne” i „rekurencyjne” oznaczają bardzo podobne?

Na przykład, jeśli istnieje algorytm, który określa wektor n-dim przez określenie jego pierwszych elementów k + 1 na podstawie wyznaczonych pierwszych elementów k i jest inicjalizowany za pomocą pierwszego składnika, czy nazwałbyś go działaniem rekurencyjnym lub indukcyjnym? Używam „rekurencyjnie”, ale dziś ktoś powiedział to „indukcyjnie”.

Nie , ale nie z powodów, które podali inni ludzie. Różnica między rekurencją a indukcją nie polega na tym, że rekurencja jest „odgórna”, a indukcja „oddolna”. Indukcja jest izomorficzna w stosunku do czegoś, co nazywa się „prymitywną rekurencją”, ale generalnie rekurencja jest zdecydowanie silniejsza niż indukcja .

Różnica między odgórnym a oddolnym jest trywialna - każdy prymitywny program rekurencyjny „z góry na dół” może zostać mechanicznie przekształcony w coś „z dołu do góry”. W rzeczywistości każdy dowód indukcyjny może zostać przekształcony w program rekurencyjny. W ramach rachunku konstrukcji indukcyjnych, jeśli chcesz udowodnić, że każda liczba naturalna jest nieparzysta, napisałbyś ją jako funkcję, która konstruuje dowód, że n jest niepoprawny, poprzez wywołanie rekurencyjne w celu skonstruowania dowodu, że n- 1 jest obfity.

Kluczowym czynnikiem indukcji jest to, że rzeczy są definiowane w kategoriach mniejszych rzeczy i „oddają się” po skończonej liczbie kroków. Liczby naturalne są indukcyjne, ponieważ każdy naturalny jest albo 0, albo następcą mniejszego naturalnego. Listy są indukcyjne, ponieważ każda lista jest pusta lub może zostać podzielona („rozwinięta”) na element i mniejszą listę.

Czasami programy rekurencyjne nie są pisane w kategoriach mniejszych rzeczy. Weźmy na przykład tę funkcję Collatz:

fun collatz(n) 
   if n <= 1
      return 0;
   else if n % 2 == 0
     return 1 + collatz(n / 2)
   else
     return 1 + collatz(3 * n + 1)
end

Ta funkcja nie jest odgórna ani oddolna, a zatem nie indukuje liczb naturalnych.

Może być nakaz traktowania tego indukcyjnie, ale w większości przypadków po prostu nie ma mowy. Doskonałym przykładem są funkcje nad nieskończonymi strumieniami. W rzeczywistości strumienie są prototypowym przykładem typu „koindukcyjnego”.

„Praktyczne podstawy dla języków programowania” Boba Harpera, dostępny bezpłatnie online, zawiera miłe wprowadzenie do typów indukcyjnych, koindukcyjnych i rekurencyjnych.

Dla mnie to głównie kwestia punktu widzenia. Jeśli definiuję obiekty na podstawie mniejszego, robię to indukcyjnie, więc jest to oddolne. Jeśli rozwiążę problem, dzieląc go na mniejsze części, które są rozwiązywane w ten sam sposób, nazywam to rekurencją, czyli odgórnym.

(edytuj) PS. Zobacz podobne pytanie w naszym siostrzanym dziale matematyki, Definicja rekurencyjna vs. indukcyjna . Cytuję z odpowiedzi Carla Mummerta:

Mój najlepszy opis jest taki, że „definicja indukcyjna” jest bardziej powszechna, gdy definiujemy zestaw obiektów „z niczego”, natomiast „definicja rekurencyjna” jest bardziej powszechna, gdy definiujemy funkcję w już istniejącym zbiorze obiektów.

Ale co ważniejsze:

nie warto tracić snu

Nie, to nie to samo. I masz rację (zakładam, że algorytm, który opisujesz): jest rekurencyjny.

Powodem jest definicja obu słów, które można przeczytać w słowniku lub Wikipedii.

Indukcja (zakładając „indukcję matematyczną”) polega konkretnie na udowodnieniu, że wszystkie przypadki argumentów są prawdziwe.

Rekurencja dotyczy w szczególności procesu, który może być w jakiś sposób powtarzany w ramach tego samego procesu.

RE: odpowiedzi innych osób:

Po zapoznaniu się z odpowiedziami innych ludzi rozumiem, dlaczego istnieje zamieszanie: podczas definiowania struktur danych, funkcji i języków niektórzy teoretycy wydają się używać „indukcyjnego” i „rekurencyjnego” w mylący sposób (patrz komentarze do tego pytania). Nie sądzę, aby odpowiedź Koppela (nawet przy obecnych najwyższych głosach) naprawdę odzwierciedla to zamieszanie. Ponieważ mówimy o algorytmie, nie powiedziałbym, że istnieją „algorytmy indukcyjne”; Myślę, że to niepotrzebna kategoryzacja.