"mitterekursiivsena" - 1 õppematerjal

REKURSIOON - Recursion

(1), (2) ja (3) ilmselt klapivad. (4): kas vôime tagada ülemineku (n - 1)-lt n-ile? Näide. n = 5 (vt. joonist 6): kui tôstame n - 1 ketast a-lt c kaudu b-le, saab tôsta 1 ketta a-lt c-le ja 4 ketast b-lt a kaudu c-le. Klapib. Rekursiivne lahendus on mitterekursiivsest aeglasem, kuid on tavaliselt lihtne ja lühike, tihti on rekursiivne algoritm loomulik ja loogiline (järeldub rekursiivsest definitsioonist), üritage lahendada Hanoi tornide probleemi mitterekursiivsena! Kas ônnestub? Rekursiivsed tôestused Rekursiivsed tôestused on laialt levinud tôestuste vorm. Et kasutada rekursiivset tôestust, peavad olema jällegi olemas 4 tunnusjoont (vt. eespool). Olgu tarvis leida minimaalne tôstete arv Hanoi tornide ülesande lahendamisel. On lihtne leida, et 1 ketta puhul tuleb teha 1 tôste, 2 ketta puhul 3 ja 3 ketta puhul 7 tôstet. Siit vôime püstitada hüpoteesi, et n ketta puhul on vaja vähemalt 2n - 1 tôstet