"kursiivselt" - 1 õppematerjal

REKURSIOON - Recursion

alumise ketta teisaldamiseks a-lt c-le ja lôpuks veel 2 n - 1 tôstet n pealmise ketta teisaldamiseks b-lt c-le, kokku 2n - 1 + 1 + 2n - 1 = 2 * 2n - 1 = 2n+1 - 1 tôstet, mida oligi tarvis tôestada. Kui rekursiivne programm on tavaliselt aeglasem sama ülesande mitterekursiivsest lahendusest, siis rekursiivne tôestus on tavaliselt lühem ja lihtsam sama teoreemi mitterekursiivsest tôestusest (proovige näiteks toodud teoreemi tôestada mittere- kursiivselt!) Millal saabub maailma lôpp Oletagem, et mungad sooritavad 1 tôste sekundis. Siis kulub neil aega 2 64 sekundit (-1 pole sealjuures enam oluline). See on umbes 300 miljardit aastat. Arvestades, et maakera vanust hinnatakse 5 miljardile aastale ja elu vanust Maal umbes 1,5 miljardile aastale, on see soliidne periood. Sellest tuleb järeldada, et môni rekursiivne programm vôib töötada sôltuvalt ülesande mahust kolossaalselt kaua. Juba 20 ketta puhul kulub lahenduseks 6 päeva