Kaip paprasciau perprasti rekursines funkcijas?

Sveiki, studijuoju programavima, viskas lyg ir sekas neblogai. Bet peilis man yra rekursija. Kai programuoju programa, tai viska isivaizduoju gan nesunkiai, bet kai reikia rekursines funkcijas parasyti, arba bent susekti ka jos grazina gale, tai smegenine susisuka visai. Gal turite kokiu patarimu ar pamoku kaip reikia lengviau perprasti rekursines funkcijas ?

Tai kad čia tiesiog funkcija funkcijoje ir tiek. Nelabai suprantu kur čia galva turi susisukti :)

Na, bet jei reikia: http://www.techmat.vgtu.lt/konspektai/C++MK_PDF/5%20sk.pdf (5.7 punktas)

O šiaip yra toks išradimas vadinamas Google. Įvedi ten "rekursinės funkcijos" ir nustebsi pamatęs, kad šis išradimas tau pateikia norimus rezultatus.

Tai gal debugerio nenaudoji, kad nesupranti ką gražina ir mėgini įsivaizduot? :) Aišku jei ta funkcija lapo dydžio, tai čia jau iš esmės Tavo projektavimo klaida :)

Labas,

rekursinės f-jos kūnas dažniausiai būna toks:

1. pačios rekursijos pabaigos sąlyga, kad nesigautų amžinas ciklas.

2. jei sąlyga nėra tenkinama, savęs pačios iškvietimas su naujais parametrais.

O skaičiuoji tai paprastai rašydamas į stulpelį kiekvienos iteracijos rezultatus ir galiausiai susumuoji.

Sveiki, studijuoju programavima, viskas lyg ir sekas neblogai. Bet peilis man yra rekursija. Kai programuoju programa, tai viska isivaizduoju gan nesunkiai, bet kai reikia rekursines funkcijas parasyti, arba bent susekti ka jos grazina gale, tai smegenine susisuka visai. Gal turite kokiu patarimu ar pamoku kaip reikia lengviau perprasti rekursines funkcijas ?

Tai kad čia tiesiog funkcija funkcijoje ir tiek. Nelabai suprantu kur čia galva turi susisukti :)

 

Na, bet jei reikia: http://www.techmat.vgtu.lt/konspektai/C++MK_PDF/5%20sk.pdf (5.7 punktas)

 

O šiaip yra toks išradimas vadinamas Google. Įvedi ten "rekursinės funkcijos" ir nustebsi pamatęs, kad šis išradimas tau pateikia norimus rezultatus.

Per testus reikia nuo lapo seksti funkcija ir parasyta ka galiausiai grazina, vakar teko su situo veraintu susidurti, tai galu gale teko speti:

int recursion(int m,int n) {
   if (n == 0) {
       return n+1;
   } else if (m > 0 && n = 1) {
       recursion (m-1, n);
   } else {
       recursion(m, recursion(m, n-1));
   }
}

Toki koda reikejo backtrackinti su pradinem reiksmes m = 3, n = 2. Nemanau, kad cia jau paprasta toki susekti vien su popierium ir piestuku. :)

Per testus reikia nuo lapo seksti funkcija ir parasyta ka galiausiai grazina, vakar teko su situo veraintu susidurti, tai galu gale teko speti:

 

int recursion(int m,int n) {
   if (n == 0) {
       return n+1;
   } else if (m > 0 && n = 1) {
       recursion (m-1, n);
   } else {
       recursion(m, recursion(m, n-1));
   }
}

Toki koda reikejo backtrackinti su pradinem reiksmes m = 3, n = 2. Nemanau, kad cia jau paprasta toki susekti vien su popierium ir piestuku. :)

Tai čia išvis kodas ne visai teisingas, nes prie recursion() kvietimų nėra return. T.y., jei n == 0, grąžins 1, kitokiu atveju negrąžins nieko apskritai...

Tai čia išvis kodas ne visai teisingas, nes prie recursion() kvietimų nėra return. T.y., jei n == 0, grąžins 1, kitokiu atveju negrąžins nieko apskritai...

Galbut ne taip pamenu visa uzduoti is galvos. Parasysiu koks tiksliai kodas yra kai gausiu atsakyma.

Rašymo daug, bet kitaip kažin ar pavyktų. Aš pvz. paėmiau 10, 10

int recursion(int m, int n) {

if (n == 0) {

return n+1;

} else if (m > 0 && n == 1) {

recursion (m-1, n);

} else {

recursion(m, recursion(m, n-1));

}

}

pvz. m = 10, n = 10

r(10, 10)

10 == 0 ? false

10 > 0 && 10 == 1 ? false

r(10, r(10, 9))

r(10,9)

9 == 0 ? false

10 > 0 && 9 == 1 ? false

r(10, r(10, 8))

...

r(10, r(10, 1))

1 == 0 ? false

10 > 0 && 1 == 1 ? false

r(10, r(10, 0))

r(10, r(10, 0))

0 == 0 ? true

return 1

r(10, 1)

...

Užsipipi rašyt, bet galiausiai mano krištolinis rutulys sako, kad rezultatas bus 1 :D

Rašymo daug, bet kitaip kažin ar pavyktų. Aš pvz. paėmiau 10, 10

 

int recursion(int m, int n) {

if (n == 0) {

return n+1;

} else if (m > 0 && n == 1) {

recursion (m-1, n);

} else {

recursion(m, recursion(m, n-1));

}

}

 

pvz. m = 10, n = 10

 

r(10, 10)

10 == 0 ? false

10 > 0 && 10 == 1 ? false

r(10, r(10, 9))

 

r(10,9)

9 == 0 ? false

10 > 0 && 9 == 1 ? false

r(10, r(10, 8))

 

...

 

r(10, r(10, 1))

1 == 0 ? false

10 > 0 && 1 == 1 ? false

r(10, r(10, 0))

 

r(10, r(10, 0))

0 == 0 ? true

return 1

 

r(10, 1)

...

 

Užsipipi rašyt, bet galiausiai mano krištolinis rutulys sako, kad rezultatas bus 1 :D

Deja, bet tokio varianto nebuvo tarp galimu :D

Kaip ir minėjo Silkė, šitame kode rekursija kartosis tol, kol bus pasiekta sąlyga: if (n == 0) return n+1; Tai atsakymas be skaičiavimų aiškus, kad 1. Aukščiau tik parodžiau, kad įmanoma užsirašyti kaip vyksta kodas įsistatant į kintamuosius realias reiškmes. Sėkmės!

Originali uzduotis:

public static ackermann(int m, int n) {
   if(m == 0)
       return n+1;
   else if(m > 0 && n == 0)
       return ackermann(m-1,1);
   else
       return ackermann(m-1, ackermann(m, n-1));

What is the result of a call ackermann(3,2)?

Answer: 29