{"id":8339,"date":"2023-04-09T22:37:11","date_gmt":"2023-04-09T20:37:11","guid":{"rendered":"https:\/\/blue.pri.ee\/ttu\/?p=8339"},"modified":"2026-06-03T14:16:19","modified_gmt":"2026-06-03T12:16:19","slug":"pr2et11-pinu-ja-rekursioon","status":"publish","type":"post","link":"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/","title":{"rendered":"PR2ET11: Pinu ja rekursioon"},"content":{"rendered":"<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_85 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Praktikumi_materjal\" >Praktikumi materjal<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Praktikumi_ulesanded\" >Praktikumi \u00fclesanded<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Ulesanne_1_W11-1_Rekursiooni_ulesannete_komplekt\" >\u00dclesanne 1 [W11-1]: Rekursiooni \u00fclesannete komplekt<\/a><ul class='ez-toc-list-level-5' ><li class='ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Nouded\" >N\u00f5uded<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Programm_1_summa\" >Programm 1: summa<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Programm_2_astendamine\" >Programm 2: astendamine<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Programm_3_Fibonacci_arvud\" >Programm 3: Fibonacci arvud.<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Ulesanne_2_W11-2_pinu\" >\u00dclesanne 2 [W11-2]: pinu<\/a><ul class='ez-toc-list-level-5' ><li class='ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Nouded-2\" >N\u00f5uded<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Pinu_silumisfunktsioon\" >Pinu silumisfunktsioon<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Testimine\" >Testimine<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Lisaulesanne_1_W11-3_rekursiooni_praktiline_kasutusjuht\" >Lisa\u00fclesanne 1 [W11-3]: rekursiooni praktiline kasutusjuht<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-13\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Lisaulesanne_2_W11-4_Pinu_laiendus\" >Lisa\u00fclesanne 2 [W11-4]: Pinu laiendus<\/a><ul class='ez-toc-list-level-5' ><li class='ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-14\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Nouded-3\" >N\u00f5uded<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-15\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Testimine-2\" >Testimine<\/a><\/li><\/ul><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-16\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Parast_seda_tundi_peaksid\" >P\u00e4rast seda tundi peaksid<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-17\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/#Taiendav_materjal\" >T\u00e4iendav materjal<\/a><\/li><\/ul><\/nav><\/div>\n<h3><span class=\"ez-toc-section\" id=\"Praktikumi_materjal\"><\/span>Praktikumi materjal<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>Slaidid: <a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/slaidid-et\/11_rekursioon.pdf\"><strong>Rekursioon<\/strong><\/a><\/li>\n<li>Slaidid: <a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/slaidid-et\/11_pinu.pdf\"><strong>Pinu (magasin)<\/strong><\/a><\/li>\n<li>Tunnis l\u00e4bi tehtavad n\u00e4ited\n<ul>\n<li>Rekursiivne faktoriaal: <strong><a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/factorial.c\">https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/factorial.c<\/a><\/strong><\/li>\n<li>Sabarekursiivne faktoriaal: <strong><a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/factorial_tail.c\">https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/factorial_tail.c<\/a><\/strong><\/li>\n<li>Pinu: <strong><a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/stack_base.c\">https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/stack_base.c<\/a><\/strong><\/li>\n<\/ul>\n<\/li>\n<li>Alternatiivne n\u00e4ide: Pinu, mis kasutab pinuviita (SP) viidana: <strong><a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/stack_sp_as_pointer.c\">https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/stack_sp_as_pointer.c<\/a><\/strong><\/li>\n<\/ul>\n<h3><span class=\"ez-toc-section\" id=\"Praktikumi_ulesanded\"><\/span>Praktikumi \u00fclesanded<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>Selles praktikumis on kaks baas\u00fclesannet, \u00fcks iseseisev lisa\u00fclesanne rekursioonile ning \u00fcks lisa\u00fclesanne, mis laiendab pinu baas\u00fclesannet.<\/p>\n<p>Tunnis vajaminev teooria esitatakse kahes osas, teine pool teooriast esitatakse p\u00e4rast m\u00f5ne aja m\u00f6\u00f6dumist. Teise teooriaosa algusajast antakse teada tunni v\u00e4ltel.<\/p>\n<h4><span class=\"ez-toc-section\" id=\"Ulesanne_1_W11-1_Rekursiooni_ulesannete_komplekt\"><\/span>\u00dclesanne 1 [W11-1]: Rekursiooni \u00fclesannete komplekt<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>Esimese \u00fclesande raames tuleb sul luua <strong>kolm<\/strong> rekursiivset programmi (osa 1, 2 ja 3). <strong>\u00dclesannet saab esitada ainult siis, kui k\u00f5ik kolm on valmis!<\/strong><\/p>\n<p>NB! Tegu on \u00e4\u00e4rmiselt lihtsate \u00fclesannetega, v\u00e4ldi internetist lahenduste otsimist!<\/p>\n<p>Tunni alguses luuakse n\u00e4idislahendus faktoriaali rekursiivsest lahendamisest!<\/p>\n<h5><span class=\"ez-toc-section\" id=\"Nouded\"><\/span>N\u00f5uded<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<ul>\n<li>V\u00f5id laheduse luua \u00fche failina, kus on kolm rekursiooni korraga, v\u00f5i kolme erineva programmina. N\u00e4ited on tehtud kolme erineva rakendusena.<\/li>\n<li>K\u00f5igil juhtudel on kohustuslik toetada sisendina positiivset t\u00e4isarvu. Negatiivse sisendi korral on kas lahenduses m\u00e4rgitud eraldi vastus (baasjuht) v\u00f5i tuleb kuvada viga.<\/li>\n<li>Sisendi v\u00f5id k\u00fcsida rakenduse sees v\u00f5i lugeda k\u00e4surea argumendina.<\/li>\n<li>Iteratiivseid lahendusi kasutada ei tohi, k\u00f5ik kolm osa peavad olema lahendatud rekursiivselt.<\/li>\n<li>Esitada saab \u00fclesannet vaid siis, kui k\u00f5ik kolm osa on valmis.<\/li>\n<\/ul>\n<h5><span class=\"ez-toc-section\" id=\"Programm_1_summa\"><\/span>Programm 1: summa<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Loo rakendus, mis leiab k\u00f5igi positiivsete t\u00e4isarvude summa kuni kasutaja sisestatud arvuni. Negatiivse argumendi korral rekursiivsele summa funktsioonile on summa 0 (positiivsed arvud puuduvad, baasjuht).<\/p>\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/sum 0\r\nsum(0) = 0\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/sum 1\r\nsum(1) = 1\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/sum 2\r\nsum(2) = 3\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/sum 3\r\nsum(3) = 6\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/sum -1\r\nsum(-1) = 0<\/pre>\n<h5><span class=\"ez-toc-section\" id=\"Programm_2_astendamine\"><\/span>Programm 2: astendamine<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Loo rakendus, mis lubab astendada x<sup>y<\/sup>. math.h teegi ja sisse ehitatud astmefunktsioonide kasutamine ei ole lubatud.<\/p>\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/pow 2 8\r\n2^8 = 256\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/pow 5 3\r\n5^3 = 125\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/pow 5 0\r\n5^0 = 1<\/pre>\n<p>NB! Kuigi n\u00f5ue on vaid rakendus luua positiivsetele t\u00e4isarvudele, siis v\u00f5id proovida ka laiendada lahendust n\u00e4iteks negatiivsetele arvudele.<\/p>\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/pow -5 2\r\n-5^2 = 25\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/pow -5 3\r\n-5^3 = -125\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/pow 2 -1\r\n2^-1 = 0.5000\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/pow 2 -2\r\n2^-2 = 0.2500\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/pow 2 -3\r\n2^-3 = 0.1250<\/pre>\n<h5><span class=\"ez-toc-section\" id=\"Programm_3_Fibonacci_arvud\"><\/span>Programm 3: Fibonacci arvud.<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Loo rakendus, mis leiab soovitud Fibonacci arvu. n-indaks fibonacci arvuks on selle kahe eelneva Fibonacci arvu summa ehk siis <strong>fib<sub>x<\/sub> = fib<sub>x &#8211; 1<\/sub> + fib<sub>x &#8211; 2<\/sub><\/strong>. Erinevalt eelnevatest rekursioonidest on Fibonacci jadal kaks seet\u00f5ttu ka 2 baasjuhtu.<\/p>\n<p>Fibonacci arvud on\u00a0 0, 1, 1, 2, 3, 5, 8, 13, 21, &#8230;,<\/p>\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/fib -1\r\nError! Input must be 0 or greater!\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/fib 0\r\nfib(0) = 0\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/fib 1\r\nfib(1) = 1\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/fib 6\r\nfib(6) = 8\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/fib 7\r\nfib(7) = 13\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/fib 45\r\nfib(45) = 1134903170<\/pre>\n<p>M\u00e4rkasid kui kaua aega l\u00e4ks viimase leidmiseks? See on ootusp\u00e4rane ning parandada vaja ei ole, kuid oluline on just aru saada miks see nii kaua aega v\u00f5ttis!<\/p>\n<p><strong>K\u00f5ik kolm programmi valmis, n\u00e4ita n\u00fc\u00fcd \u00fclesanne ette!<\/strong><\/p>\n<p>Programmi ajakulu saad m\u00f5\u00f5ta kasutades <span class=\"lang:c highlight:0 decode:true crayon-inline \">time<\/span>\u00a0 programmi. Siin on v\u00f5rdluseks kaks erinevat rekursiivset lahendust samast programmist. Teisel juhul on kasutatud l\u00e4henemist, mida kutsutakse <em>tail-recursion<\/em>&#8217;iks ehk sabarekursiooniks. Selle kohta v\u00f5id vajadusel uurida omal k\u00e4el.<\/p>\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$  time .\/fib 45\r\nfib(45) = 1134903170\r\n\r\nreal    0m8,520s\r\nuser    0m8,518s\r\nsys     0m0,000s\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk11_recursion_stack$  .\/fib_tail 45\r\nfib(45) = 1134903170\r\n\r\nreal    0m0,001s\r\nuser    0m0,000s\r\nsys     0m0,001s<\/pre>\n<h4><span class=\"ez-toc-section\" id=\"Ulesanne_2_W11-2_pinu\"><\/span>\u00dclesanne 2 [W11-2]: pinu<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>Selles \u00fclesandes loome men\u00fc\u00fcprogrammi, mille sisuks on demonstreerida pinu funktsioone. Tunnis lahendatav \u00fclesanne on demonstratiivne ning toetab varasemalt \u00f5pitud d\u00fcnaamilist m\u00e4lu &#8211; selline lahendus ei too oma keerukuse t\u00f5ttu v\u00e4lja pinu eeliseid kiiruses!<\/p>\n<p>Tunni alguses luuakse osaline n\u00e4idis, kus lahendame \u00e4ra Push() funktsiooni!<\/p>\n<h5><span class=\"ez-toc-section\" id=\"Nouded-2\"><\/span>N\u00f5uded<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<ul>\n<li>Loo oma rakendusele men\u00fc\u00fc struktuur &#8211; kasutaja peab saama valida, millist operatsiooni soovib teostada<\/li>\n<li>Loo <span class=\"lang:c highlight:0 decode:true crayon-inline \">Pop()<\/span>\u00a0 ja <span class=\"lang:c highlight:0 decode:true crayon-inline \">Peek()<\/span>\u00a0 funktsioonid\n<ul>\n<li><span class=\"lang:c highlight:0 decode:true crayon-inline\">Pop()<\/span>\u00a0 eemaldab pealmise elemendi pinust ja tagastab selle v\u00e4\u00e4rtuse.<\/li>\n<li><span class=\"lang:c highlight:0 decode:true crayon-inline\">Peek()<\/span>\u00a0 tagastab pealmise elemendi, kuid ei eemalda seda<\/li>\n<\/ul>\n<\/li>\n<li>Loodavad funktsioonid elementide v\u00e4\u00e4rtusi kuvada <strong>ei tohi<\/strong>! Ekraanile kuvatakse v\u00e4\u00e4rtused p\u00e4rast men\u00fc\u00fcsse tagastamist!\n<ul>\n<li>NB! Baasversioonis on lubatud reserveerida \u00fcks v\u00e4\u00e4rtus t\u00e4histamaks pinu alat\u00e4itumist, et v\u00e4ljastuses illegaalset v\u00e4\u00e4rtust ei kuvataks. Lisa\u00fclesande esitamisel see lubatud ei ole.<\/li>\n<\/ul>\n<\/li>\n<li>Vastavalt funktsioonile veendu, et oleksid realiseeritud kas ala- v\u00f5i \u00fclet\u00e4itumise kontrollid.<\/li>\n<li>P\u00f6\u00f6ra t\u00e4helepanu olukorrale, kus pinust eemaldatakse k\u00f5ik elemendid &#8211; <span class=\"lang:c highlight:0 decode:true crayon-inline \">realloc()<\/span>\u00a0 funktsiooniga 0 baiti k\u00fcsida ei tohi, tuleb kasutada <span class=\"lang:c highlight:0 decode:true crayon-inline \">free()<\/span>\u00a0 funktsiooni!<\/li>\n<\/ul>\n<h5><span class=\"ez-toc-section\" id=\"Pinu_silumisfunktsioon\"><\/span>Pinu silumisfunktsioon<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Selleks, et saaksid paremat aimu pinu sisust, pakun sulle ka silumisfunktsiooni. Tegelikus olukorras sellist funktsiooni sageli rakendada ei saaks, kuna see v\u00f5ib olla vastuolus pinu piirangute ning ka konkreetse pinu realisatsiooniga!.<\/p>\n<pre class=\"toolbar:2 lang:c decode:true \">void debug_stack(stack st)\r\n{\r\n    printf(\"DEBUG\\n\");\r\n    printf(\"\\tStack size: %d\\n\", st.size);\r\n    printf(\"\\tData pointer: %p\\n\", st.data);\r\n    \r\n    if (st.size != 0 &amp;&amp; st.data == NULL)\r\n    {\r\n        printf(\"Sanity check failed!\\n\");\r\n        printf(\"Stack is NULL, but size is not 0\\n\");\r\n        return;\r\n    }\r\n    \r\n    if (st.size == 0 &amp;&amp; st.data != NULL)\r\n    {\r\n        printf(\"Sanity check failed!\\n\");\r\n        printf(\"Stack data is not NULL, but size is 0\\n\");\r\n        return;\r\n    }\r\n    \r\n    printf(\"\\tValues: \");\r\n    for (int i = st.size - 1; i &gt;= 0; i--)\r\n    {\r\n        printf(\"%d \", st.data[i]);\r\n    }\r\n    printf(\"\\n\\n\");\r\n}\r\n<\/pre>\n<h5><span class=\"ez-toc-section\" id=\"Testimine\"><\/span>Testimine<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Testimisel p\u00f6\u00f6ra t\u00e4helepanu j\u00e4rgnevale:<\/p>\n<ul>\n<li>pinu \u00fclet\u00e4itumine<\/li>\n<li>pinu alat\u00e4itumine<\/li>\n<li>pinu andmete vabastamine p\u00e4rast viimase elemendi kustutamist (valgrind!)<\/li>\n<li>M\u00e4lulekke ohule, kui programm suletakse hetkel, kui pinus on veel andmeid (valgrind!)<\/li>\n<\/ul>\n<div class=\"su-spoiler su-spoiler-style-fancy su-spoiler-icon-chevron su-spoiler-closed\" data-scroll-offset=\"0\" data-anchor-in-url=\"no\"><div class=\"su-spoiler-title\" tabindex=\"0\" role=\"button\"><span class=\"su-spoiler-icon\"><\/span>Ava mind v\u00e4ljundi n\u00e4gemiseks<\/div><div class=\"su-spoiler-content su-u-clearfix su-u-trim\">\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-wk:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/stack_solution \r\nMaximum stack size is limited to 3!\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 9\r\nDEBUG\r\n        Stack size: 0\r\n        Data pointer: (nil)\r\n        Values: \r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 1\r\nEnter value: 97\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 9\r\nDEBUG\r\n        Stack size: 1\r\n        Data pointer: 0x558cd0c07ac0\r\n        Values: 97 \r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 1\r\nEnter value: 34\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 1\r\nEnter value: 25\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 1\r\nEnter value: 99\r\nERROR: Stack overflow!\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 9\r\nDEBUG\r\n        Stack size: 3\r\n        Data pointer: 0x558cd0c07ac0\r\n        Values: 25 34 97 \r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 2\r\nGot 25\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 2\r\nGot 34\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 2\r\nGot 97\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 2\r\nERROR: Stack underflow!\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 9\r\nDEBUG\r\n        Stack size: 0\r\n        Data pointer: (nil)\r\n        Values: \r\n\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 0\r\n<\/pre>\n<\/div><\/div>\n<h4><span class=\"ez-toc-section\" id=\"Lisaulesanne_1_W11-3_rekursiooni_praktiline_kasutusjuht\"><\/span>Lisa\u00fclesanne 1 [W11-3]: rekursiooni praktiline kasutusjuht<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>k\u00e4esolev lisa\u00fclesanne on sulle antud ingliskeelse algoritmi kirjeldusena. <strong>Tegu on t\u00e4iesti eraldiseisva \u00fclesandega, mis ei ole seotud eelnevalt tehtud tunnit\u00f6\u00f6 lahendusega!<\/strong><\/p>\n<p>NB! Olulised muutujad on antud matemaatikutele omases kirjapildis ehk \u00fcksikute t\u00e4htedena &#8211; soovitus oma programmis kasuta pikemaid ja selgitavamaid nimesid nagu on programmeerimises omane.<\/p>\n<p>Given search key <span class=\"lang:c highlight:0 decode:true crayon-inline \">K<\/span>\u00a0 and an array <span class=\"lang:c highlight:0 decode:true crayon-inline\">A<\/span>\u00a0 of <span class=\"lang:c highlight:0 decode:true crayon-inline \">n<\/span>\u00a0 integers A<sub>0<\/sub>, A<sub>1<\/sub>, &#8230; , A<sub>n &#8211; 1<\/sub> sorted such that A<sub>0<\/sub> \u2264 A<sub>1<\/sub>\u2264 &#8230; \u2264 A<sub>n &#8211; 1<\/sub> use the following algorithm to find if <span class=\"lang:c highlight:0 decode:true crayon-inline \">K\u00a0\u2208\u00a0A<\/span><\/p>\n<ol>\n<li>Set <i>lowIndex<\/i><i> <span class=\"lang:c highlight:0 decode:true crayon-inline\">L<\/span> <\/i>\u00a0to <span class=\"lang:c highlight:0 decode:true crayon-inline \"> 0<\/span>\u00a0 and\u00a0<i>highIndex <\/i><i><span class=\"lang:c highlight:0 decode:true crayon-inline\">H<\/span> <\/i>\u00a0to <span class=\"lang:c highlight:0 decode:true crayon-inline \">n\u00a0\u2212 1<\/span> .<\/li>\n<li>Call the recursive function using 4 arguments \u2013 <span class=\"lang:c highlight:0 decode:true crayon-inline\">A, L, H, K<\/span> .\n<ul>\n<li>If <span class=\"lang:c highlight:0 decode:true crayon-inline \">L\u00a0&gt;\u00a0H<\/span> , the search terminates as unsuccessful &#8211; <i>return<\/i><i> 0<\/i><\/li>\n<li>Set <span class=\"lang:c highlight:0 decode:true crayon-inline \">m<\/span>\u00a0 (the position of the middle element) to the <span class=\"lang:c highlight:0 decode:true crayon-inline\">floor of (L + H)\u200a \/ \u200a2<\/span><\/li>\n<li>If\u00a0<i>A<\/i><sub><i>m<\/i><\/sub>\u00a0&lt;\u00a0<i>K<\/i>, set <span class=\"lang:c highlight:0 decode:true crayon-inline \">L<\/span>\u00a0 to <span class=\"lang:c highlight:0 decode:true crayon-inline \">m\u00a0+ 1<\/span> , call recursion again<\/li>\n<li>If <i>A<\/i><sub><i>m<\/i><\/sub>\u00a0&gt;\u00a0<i>K<\/i>, set <span class=\"lang:c highlight:0 decode:true crayon-inline \">H<\/span>\u00a0 to <span class=\"lang:c highlight:0 decode:true crayon-inline \">m\u00a0\u2212 1<\/span> , call recursion again<\/li>\n<li>If <i>A<\/i><sub><i>m<\/i><\/sub>\u00a0=\u00a0<i>K<\/i>, the search was successful &#8211; <i>return<\/i><i> 1<\/i><\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<p>\u00dclesanne valmis, valmista enne esitamist ette vastused j\u00e4rgmistele k\u00fcsimustele. Kui vastused olemas, anna m\u00e4rku!<\/p>\n<ul>\n<li>Ajaline keerukus &#8211; v\u00f5rdle antud algoritmi ja tavalist lineaarset otsingut. Mitu v\u00f5rdlust l\u00e4heks vaja, et v\u00f5rrelda massiivi, kus on\n<ul>\n<li>16 liiget<\/li>\n<li>256 liiget<\/li>\n<li>100 000 liiget<\/li>\n<\/ul>\n<\/li>\n<li>Anna hinnang algoritmi keerukusele\u00a0 &#8211; nt konstantne, logaritmiline, lineaarne, eksponentsiaalne (https:\/\/www.bigocheatsheet.com)<\/li>\n<li>Kui massiiv poleks sorteeritud, kas see algoritm t\u00f6\u00f6taks?<\/li>\n<\/ul>\n<h4><span class=\"ez-toc-section\" id=\"Lisaulesanne_2_W11-4_Pinu_laiendus\"><\/span>Lisa\u00fclesanne 2 [W11-4]: Pinu laiendus<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>Selles \u00fclesandes loome paar lisav\u00f5imalust oma pinule ning teeme seda veidi universaalsemaks.<\/p>\n<h5><span class=\"ez-toc-section\" id=\"Nouded-3\"><\/span>N\u00f5uded<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<ul>\n<li>Lisa oma pinule j\u00e4rgmised funktsioonid\n<ul>\n<li>Duplicate() &#8211; v\u00f5tab pinu k\u00f5ige pealmise elemendi<\/li>\n<li>Swap() &#8211; vahetab pinu kahe pealmise elemendi v\u00e4\u00e4rtused omavahel<\/li>\n<\/ul>\n<\/li>\n<li>Need funktsioonid tohivad kasutada <strong>ainult<\/strong> Push() ja Pop() funktsioonide v\u00e4ljakutseid!<\/li>\n<li>Muuda oma Pop() ja Peek() funktsioonide kujusid sedasi, et kehtiksid j\u00e4rgmised n\u00f5uded\n<ul>\n<li>Pinu peab toetama k\u00f5iki arve (ei tohi olla reserveeritud mitmet\u00e4henduslike v\u00e4\u00e4rtusi).<\/li>\n<li>Juhul kui tekib pinu alat\u00e4itumine, siis kuvatakse vaid veateade, v\u00e4\u00e4rtust ennast ei kuvata<\/li>\n<\/ul>\n<\/li>\n<li>M\u00e4rkus: Lisafunktsioonide jaoks pead suure t\u00f5en\u00e4ousega muutma ka Push() funktsiooni!<\/li>\n<\/ul>\n<h5><span class=\"ez-toc-section\" id=\"Testimine-2\"><\/span>Testimine<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Olulised kitsaskohad, mida testida (lisaks tavaolukordadele)<\/p>\n<ul>\n<li>Pop(), kui pinu on t\u00fchi (ei tohi numbrit v\u00e4ljastada)<\/li>\n<\/ul>\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true \">risto@risto-wk:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/stack_solution \r\nMaximum stack size is limited to 3!\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 2\r\nERROR: Stack underflow!<\/pre>\n<ul>\n<li>Duplicate(), kui andmeid pinus pole<\/li>\n<li>Duplicate(), kui pinu on t\u00e4is<\/li>\n<\/ul>\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-wk:~\/Nextcloud\/prog2\/wk11_recursion_stack$ .\/stack_solution \r\nMaximum stack size is limited to 3!\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 5\r\nERROR: Stack underflow!\r\nERROR: Cannot duplicate!\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 1\r\nEnter value: 25\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 5\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 5\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 5\r\nERROR: Stack overflow!\r\nERROR: Cannot duplicate!\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 9\r\nDEBUG\r\n        Stack size: 3\r\n        Data pointer: 0x561f250ebac0\r\n        Values: 25 25 25<\/pre>\n<ul>\n<li>Swap(), kui pinus andmeid pole<\/li>\n<li>Swap(), kui pinus on vaid 1 liige<\/li>\n<\/ul>\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-wk:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/stack_solution \r\nMaximum stack size is limited to 3!\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 4 \r\nERROR: Stack underflow!\r\nERROR: Cannot swap!\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 1\r\nEnter value: 2\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 4\r\nERROR: Stack underflow!\r\nERROR: Cannot swap !\r\nOriginal state restored.\r\n\r\n1 - Push        4 - Swap\r\n2 - Pop         5 - Duplicate\r\n3 - Peek        9 - DEBUG\r\n0 - exit\r\n&gt; 9\r\nDEBUG\r\n        Stack size: 1\r\n        Data pointer: 0x55e8aa1e6ac0\r\n        Values: 2 \r\n<\/pre>\n<h3><span class=\"ez-toc-section\" id=\"Parast_seda_tundi_peaksid\"><\/span>P\u00e4rast seda tundi peaksid<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>Teadma, mida t\u00e4hendab rekursioon, sh rekursiivne funktsioon ja rekursiivne andmet\u00fc\u00fcp.<\/li>\n<li>Oskama kirjutada lihtsaid rekursioone<\/li>\n<li>Teadma, et eksisteerib ka sabaga rekursioon<\/li>\n<li>Teadma rekursioonide headest omadustest ja probleemidest<\/li>\n<li>Teadma rekursioonide kasutusvaldkondi<\/li>\n<li>Teadma, mida t\u00e4hendab abstraktne andmestruktuur<\/li>\n<li>Teadma, mis on pinu ning millised on selle omadused<\/li>\n<li>Teadma pinu kasutusvaldkondi<\/li>\n<li>Oskama luua pinu ning sellele kohustuslike funktsioone<\/li>\n<\/ul>\n<h3><span class=\"ez-toc-section\" id=\"Taiendav_materjal\"><\/span>T\u00e4iendav materjal<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>Introduction to Recursion \u2013 Data Structure and Algorithm Tutorials<br \/>\n<strong><a href=\"https:\/\/www.geeksforgeeks.org\/introduction-to-recursion-data-structure-and-algorithm-tutorials\/\">https:\/\/www.geeksforgeeks.org\/introduction-to-recursion-data-structure-and-algorithm-tutorials\/<\/a><\/strong><\/li>\n<li>Merge sort (recursion)<br \/>\n<strong><a href=\"https:\/\/www.geeksforgeeks.org\/merge-sort\/\">https:\/\/www.geeksforgeeks.org\/merge-sort\/<\/a><\/strong><\/li>\n<li>Quick sort (recursion)<br \/>\n<strong><a href=\"https:\/\/www.geeksforgeeks.org\/quick-sort\/\">https:\/\/www.geeksforgeeks.org\/quick-sort\/<\/a><\/strong><\/li>\n<li>Stack data structure<br \/>\n<strong><a href=\"https:\/\/en.wikipedia.org\/wiki\/Stack_(abstract_data_type)\">https:\/\/en.wikipedia.org\/wiki\/Stack_(abstract_data_type)<\/a><\/strong><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Praktikumi materjal Slaidid: Rekursioon Slaidid: Pinu (magasin) Tunnis l\u00e4bi tehtavad n\u00e4ited Rekursiivne faktoriaal: https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/factorial.c Sabarekursiivne faktoriaal: https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/factorial_tail.c Pinu: https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/stack_base.c Alternatiivne n\u00e4ide: Pinu, mis kasutab pinuviita (SP) viidana: https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/stack_sp_as_pointer.c Praktikumi \u00fclesanded Selles praktikumis on kaks baas\u00fclesannet, \u00fcks iseseisev lisa\u00fclesanne rekursioonile ning \u00fcks lisa\u00fclesanne, mis laiendab pinu baas\u00fclesannet. Tunnis vajaminev teooria esitatakse kahes osas, teine pool teooriast &hellip; <a href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et11-pinu-ja-rekursioon\/\" class=\"more-link\">Loe edasi <span class=\"screen-reader-text\">PR2ET11: Pinu ja rekursioon<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[97,176],"tags":[],"class_list":["post-8339","post","type-post","status-publish","format-standard","hentry","category-laborid","category-pr2-et"],"_links":{"self":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8339","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/comments?post=8339"}],"version-history":[{"count":17,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8339\/revisions"}],"predecessor-version":[{"id":11450,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8339\/revisions\/11450"}],"wp:attachment":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/media?parent=8339"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/categories?post=8339"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/tags?post=8339"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}