Kuo skiriasi rekursija matematikoje nuo rekursijos programavime?


Atsakymas 1:

Nepaisant to, ką sako kiti atsakymai, taip. Programuotojai reiškia ką nors šiek tiek kitokio termino „rekursija“ nei matematikai.

Bet tiksliau, ne grynų kalbų programuotojai reiškia ką nors šiek tiek kitokio nei grynųjų kalbų programuotojai, kai vartoja terminą „rekursija“. Nors grynųjų kalbų programuotojai reiškia tą patį, ką ir matematikai.

Pagrindinė priežastis yra ta, kad programuotojai ir matematikai reiškia „funkciją“ ką nors skirtingą.

Matematikoje „funkcija“ visada yra gryna - tai tik argumentų į rezultatus atvaizdavimas ir kiekvieną kartą paklausus apie funkcijos rezultatą remiantis kai kuriais argumentais, rezultatas yra tas pats. Jei turite Fibonačio rekursiją f (n) = f (n-1) + f (n-2), galite saugiai pakartotinai naudoti f (n-2) reikšmę kaip faktorių f (n) apibrėžime ir f (n-1) apibrėžime. Tai yra tiksliai ta pati žodžio „funkcija“ reikšmė, kaip ir žodžio „funkcija“ gryna programavimo kalba - rašyti galite

f n = jei n <= 1
tada 1
kitur f (n-1) + f (n-2)

Haskelyje (taip, aš suprantu, kad nėra taip, kaip jūs turėtumėte „rašyti“ Haskell'e, bet aš labiau renkuosi pažinti ne Haskell'o vartotojus), o šis kodas bus rodomas O (n). Jis bus rodomas O (n), nes f yra tiksliai „funkcija“ matematiniu šio žodžio prasme, ty f (n) visada yra ta pati grynoji reikšmė tam tikram n reikšmei, taigi kartą f apskaičiuojamas kiekvieno f (i) rezultatas Pirmą kartą jis gali būti pakartotinai panaudotas kitur be skaičiavimo pridėtinės vertės.

Aukščiau apibrėžta Haskelio „rekursija“ yra visiškai tokia pati kaip matematikos „rekursija“ f (n) = f (n-1) + f (n-2).

Kita vertus, ne gryna kalba „funkcijos“ reikšmė yra skirtinga, nes funkcijos visuma gali sukelti šalutinį poveikį. Taigi, jei aš rašau

int f (int n) {
if (n <= 1) grįžti 1;
grįžti f (n-1) + f (n-2);
}

C ++ / Java / etc, tai yra kitokia „rekursijos“ reikšmė nei Haskell pavyzdyje. Tai yra rekursija, kuri skambins f kiekvienam n kartai kelis kartus, todėl iš viso iškviečiami O (2 ^ n) skambučiai. Taip yra todėl, kad jei „funkcija“ reiškia procedūrą, procedūrą turime paskambinti du kartus, jei ji du kartus rodoma rekursijos kūne.

Tai, ką ne grynų kalbų programuotojai reiškia „funkcija“, yra procedūra, duodanti (galbūt) tam tikrą rezultatą ir atliekanti (galbūt) tam tikrą šalutinį poveikį. Pati procedūra yra svarbi (nes ji gali turėti šalutinį poveikį), o programa, procedūrą du kartus paskambinanti tais pačiais argumentais, gali sukurti kitokią vertę, nei programa, kuri ją vadina vieną kartą. Kadangi rekursija yra tada, kai funkcija priklauso nuo savęs, tai reiškia, kad rekursija yra procedūra, kai pati paskambina ir [galbūt] naudoja rezultatą.

Tai, ką grynųjų kalbų programuotojai ir matematikai reiškia „funkcija“, yra grynos procedūros rezultatas (be šalutinių poveikių), todėl pati procedūra nėra svarbi, nes „tik“ ji reikalinga norint gauti gryną rezultatą. Taigi „rekursija“ reiškia tik rezultatus, kurie priklauso nuo vienas kito, o ne pačios funkcijos apibrėžimo „skambučius“.

Kadangi grynos kalbos yra retos, o ne grynos kalbos yra labai paplitusios, tai yra visiškai saugus apibendrinimas, siekiant supaprastinti situaciją į „programuotojai reiškia ką nors kita nei matematikai“.


Atsakymas 2:

Ne griežtas atsakymas čia:

Palyginę matematikos ir skaičiavimo (arba kaip jūs sakote, „programavimo“) palyginimą tarp „matavimo“, kurį gali nešti asilas, gali būti metrikuojamas “. Tai gimė vadinamame Curry – Howard korespondencija - Wikipedia, kurioje sakoma, kad matematika ir skaičiavimas yra beveik sinonimai. Be to, pasiekę homotopijos tipo teorijos ir Univalencijos aksiomos kopėčias, galite pradėti manyti, kad atitikimas priklauso nuo geometrijos, skaičiavimo, teorijos nustatymo ir daugumos matematikos.

TL; DR: Jie yra lygiaverčiai, net jei kalbama apie šiek tiek skirtingą paskirtį.


Atsakymas 3:

Ar programuotojai ir matematikai, kalbėdami apie „pasikartojimą“, reiškia ką nors kitokio?

Aš taip nemanau.

Turint omenyje, kad ankstyvieji kompiuterių mokslą plėtoję žmonės - Turingas, Bažnyčia, Gedelas ir kt., Buvo matematikai.

Nors Gödelis daugiausia žinomas dėl savo neišsamumo teoremų, jis atliko milžinišką darbą atkuriamųjų funkcijų teorijos srityje. Jis bandė išspręsti tą pačią problemą (iš Davido Hilberto), kurią turėjo Turingas savo garsiajame darbe, ir savo sprendimo pagrindu iš esmės naudojo bendrąsias rekursines funkcijas. Bendrosios rekursinės funkcijos yra skaičiavimo modelis, todėl yra glaudžiai susijusios su informatika ir programavimu.

Aš manau, kad sunku yra tai, kad dauguma programuotojų, ypač tie, kurie neturi informatikos žinių, nemato ryšio tarp rekursinio apibrėžimo matematikos, kaip antai:

F0=F1=1Fn=Fn1+Fn2F_0 = F_1 = 1\\
F_n = F_{n-1} + F_{n-2}

ir rekursinis funkcijos apibrėžimas kaip

def fib (n)
  jei n == 0 || n == 1
    1
  Kitas
    fib (n-1) + fib (n-2)
  galas
galas

Funkcine kalba, pvz., Haskell, aiškiau:

fib :: Nat -> Nat
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

bet taip yra iš dalies todėl, kad Haskell buvo sukurtas aiškiems santykiams.

Žinoma, sunkiau yra pamatyti ryšį, kai programavimo pavyzdys yra ilgesnis, bet jis iš esmės yra.

Tai, be abejo, iš stovyklos „Bet programavimas yra matematika!“.


Atsakymas 4:

Ar programuotojai ir matematikai, kalbėdami apie „pasikartojimą“, reiškia ką nors kitokio?

Aš taip nemanau.

Turint omenyje, kad ankstyvieji kompiuterių mokslą plėtoję žmonės - Turingas, Bažnyčia, Gedelas ir kt., Buvo matematikai.

Nors Gödelis daugiausia žinomas dėl savo neišsamumo teoremų, jis atliko milžinišką darbą atkuriamųjų funkcijų teorijos srityje. Jis bandė išspręsti tą pačią problemą (iš Davido Hilberto), kurią turėjo Turingas savo garsiajame darbe, ir savo sprendimo pagrindu iš esmės naudojo bendrąsias rekursines funkcijas. Bendrosios rekursinės funkcijos yra skaičiavimo modelis, todėl yra glaudžiai susijusios su informatika ir programavimu.

Aš manau, kad sunku yra tai, kad dauguma programuotojų, ypač tie, kurie neturi informatikos žinių, nemato ryšio tarp rekursinio apibrėžimo matematikos, kaip antai:

F0=F1=1Fn=Fn1+Fn2F_0 = F_1 = 1\\
F_n = F_{n-1} + F_{n-2}

ir rekursinis funkcijos apibrėžimas kaip

def fib (n)
  jei n == 0 || n == 1
    1
  Kitas
    fib (n-1) + fib (n-2)
  galas
galas

Funkcine kalba, pvz., Haskell, aiškiau:

fib :: Nat -> Nat
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

bet taip yra iš dalies todėl, kad Haskell buvo sukurtas aiškiems santykiams.

Žinoma, sunkiau yra pamatyti ryšį, kai programavimo pavyzdys yra ilgesnis, bet jis iš esmės yra.

Tai, be abejo, iš stovyklos „Bet programavimas yra matematika!“.