{"id":8436,"date":"2023-04-10T13:49:50","date_gmt":"2023-04-10T11:49:50","guid":{"rendered":"https:\/\/blue.pri.ee\/ttu\/?p=8436"},"modified":"2026-06-03T14:14:03","modified_gmt":"2026-06-03T12:14:03","slug":"pr2en11-stack-and-recursion-2","status":"publish","type":"post","link":"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en11-stack-and-recursion-2\/","title":{"rendered":"PR2EN11: Stack and recursion"},"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\/labs\/pr2en11-stack-and-recursion-2\/#Lab_materials\" >Lab materials<\/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\/labs\/pr2en11-stack-and-recursion-2\/#Lab_tasks\" >Lab tasks<\/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\/labs\/pr2en11-stack-and-recursion-2\/#Task_1_W11-1_Set_of_recursion_tasks\" >Task 1 [W11-1]: Set of recursion tasks<\/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\/labs\/pr2en11-stack-and-recursion-2\/#Requirements\" >Requirements<\/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\/labs\/pr2en11-stack-and-recursion-2\/#Part_1_Sum\" >Part 1: Sum<\/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\/labs\/pr2en11-stack-and-recursion-2\/#Part_2_Power\" >Part 2: Power<\/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\/labs\/pr2en11-stack-and-recursion-2\/#Part_3_Fibonacci_sequence\" >Part 3: Fibonacci sequence<\/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\/labs\/pr2en11-stack-and-recursion-2\/#Task_2_W11-2_Stack\" >Task 2 [W11-2]: Stack<\/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\/labs\/pr2en11-stack-and-recursion-2\/#Requirements-2\" >Requirements<\/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\/labs\/pr2en11-stack-and-recursion-2\/#Debugging_function_for_the_stack\" >Debugging function for the stack<\/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\/labs\/pr2en11-stack-and-recursion-2\/#Testing\" >Testing<\/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\/labs\/pr2en11-stack-and-recursion-2\/#Extra_task_1_W11-3_Practical_use_case_for_recursion\" >Extra task 1 [W11-3]: Practical use case for recursion<\/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\/labs\/pr2en11-stack-and-recursion-2\/#Extra_task_2_W11-4_Improving_and_extending_the_stack\" >Extra task 2 [W11-4]: Improving and extending the stack<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-14\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en11-stack-and-recursion-2\/#Requirements-3\" >Requirements<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-15\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en11-stack-and-recursion-2\/#Testing-2\" >Testing<\/a><\/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\/labs\/pr2en11-stack-and-recursion-2\/#After_this_class_you_should\" >After this class, you should<\/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\/labs\/pr2en11-stack-and-recursion-2\/#Additional_materials\" >Additional materials<\/a><\/li><\/ul><\/nav><\/div>\n<h3><span class=\"ez-toc-section\" id=\"Lab_materials\"><\/span>Lab materials<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>Slides: <a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/slaidid-en\/11_recursion.pdf\"><strong>Recursion<\/strong><\/a><\/li>\n<li>Slides: <a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/slaidid-en\/11_stack.pdf\"><strong>Stack<\/strong><\/a><\/li>\n<li>Examples done together in the lab\n<ul>\n<li>Recursive factorial <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>Tail-recursive factorial <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>Stack: <a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/stack_base.c\"><strong>https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/stack_base.c<\/strong><\/a><\/li>\n<\/ul>\n<\/li>\n<li>Alternative example of a stack that uses the SP as a pointer:\u00a0 <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=\"Lab_tasks\"><\/span>Lab tasks<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>In this lab there are two base tasks, one completely independent extra task for recursion and one extra task as an extension to the stack task.<\/p>\n<h4><span class=\"ez-toc-section\" id=\"Task_1_W11-1_Set_of_recursion_tasks\"><\/span>Task 1 [W11-1]: Set of recursion tasks<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>As the first task, you need to create\u00a0<strong>three<\/strong> recursive programs (parts 1, 2 and 3). <strong>The task can only be presented once all three are done!<\/strong><\/p>\n<p>NB! The recursions are extremely simple, avoid looking for solutions on the internet!<\/p>\n<p>In the beginning of the lesson, we&#8217;ll create an example of a factorial task solved recursively!<\/p>\n<h5><span class=\"ez-toc-section\" id=\"Requirements\"><\/span>Requirements<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<ul>\n<li>You can make the solution as one file with three recursions or as three separate programs. Example output is provided separately for each program.<\/li>\n<li>In all cases, the programs must support positive integers as input. Negative input either has a defined base case or will cause an error.<\/li>\n<li>Input can be prompted inside of the application or read as a command line argument<\/li>\n<li>Iterative solutions are not permitted! All three parts must be solved recursively<\/li>\n<li>Only present your task once all three parts are completed<\/li>\n<\/ul>\n<h5><span class=\"ez-toc-section\" id=\"Part_1_Sum\"><\/span>Part 1: Sum<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Create an application that finds the sum of all positive integers until the entered integer. Negative argument for the recursive function returns the sum as 0.<\/p>\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/sum 0\r\nsum(0) = 0\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/sum 1\r\nsum(1) = 1\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/sum 2\r\nsum(2) = 3\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/sum 3\r\nsum(3) = 6\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/sum -1\r\nsum(-1) = 0<\/pre>\n<h5><span class=\"ez-toc-section\" id=\"Part_2_Power\"><\/span>Part 2: Power<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Create an application that allows you to take x to the power of y (x<sup>y<\/sup>). Using the math library and built in power function is not allowed.<\/p>\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/pow 2 8\r\n2^8 = 256\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/pow 5 3\r\n5^3 = 125\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/pow 5 0\r\n5^0 = 1<\/pre>\n<p>NB! Even though you only need to create the solution for positive integers, you can also try to expand to negative values.<\/p>\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/pow -5 2\r\n-5^2 = 25\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/pow -5 3\r\n-5^3 = -125\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/pow 2 -1\r\n2^-1 = 0.5000\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/pow 2 -2\r\n2^-2 = 0.2500\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/pow 2 -3\r\n2^-3 = 0.1250<\/pre>\n<h5><span class=\"ez-toc-section\" id=\"Part_3_Fibonacci_sequence\"><\/span>Part 3: Fibonacci sequence<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Create an application that finds the n-th Fibonacci number. The Fibonacci numbers are calculated as the sum of two previous Fibonacci numbers\u00a0 <strong>fib<sub>x<\/sub> = fib<sub>x &#8211; 1<\/sub> + fib<sub>x &#8211; 2<\/sub><\/strong>. Compared to the previous recursions, Fibonacci sequence requires two base cases.<\/p>\n<p>Fibonacci numbers are\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\/wk10_recursion_stack$ .\/fib -1\r\nError! Input must be 0 or greater!\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/fib 0\r\nfib(0) = 0\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/fib 1\r\nfib(1) = 1\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/fib 6\r\nfib(6) = 8\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/fib 7\r\nfib(7) = 13\r\nristo@risto-tux:~\/Nextcloud\/prog2\/wk10_recursion_stack$ .\/fib 45\r\nfib(45) = 1134903170<\/pre>\n<p>Did you notice how long it took to find the last value? This is expected in the lab and you don&#8217;t need to fix anything, however you should understand why this happened! If not, think or ask!<\/p>\n<p><strong>All 3 parts are done, now present your lab!<\/strong><\/p>\n<p>You can time the execution of your program using the\u00a0 <span class=\"lang:c highlight:0 decode:true crayon-inline\">time<\/span>\u00a0 program. I&#8217;ve put the comparison of two different solutions for Fibonacci below. The second one uses tail-recursion. You can read about it on your own if necessary!<\/p>\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/prog2\/wk10_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\/wk10_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=\"Task_2_W11-2_Stack\"><\/span>Task 2 [W11-2]: Stack<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>In this task, we will create a menu program to demonstrate some of the stack functions. The lab task is demonstrative only and is intended to support the dynamic memory allocation studied before &#8211; due to the added complexity of this, the benefits of speed are unfortunately diminished.<\/p>\n<p>In the beginning of the lesson, we will create a partial solution with the Push() function.<\/p>\n<h5><span class=\"ez-toc-section\" id=\"Requirements-2\"><\/span>Requirements<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<ul>\n<li>Create a menu structure &#8211; the user must be able to select the desired operation<\/li>\n<li>Create Pop() and Peek() functions\n<ul>\n<li>Pop() removes the topmost element from the stack and returns the value.<\/li>\n<li>Peek() returns the topmost element from the stack, but does not remove it.<\/li>\n<\/ul>\n<\/li>\n<li>The functions you create are <strong>not allowed<\/strong> to display the values!\u00a0 Values must be printed in the menu.<\/li>\n<li>NB! In the base variant, you are allowed to reserve a special value to be returned in the case of stack underflow, so that the illegal value wouldn&#8217;t be displayed. This is not allowed in the extra task version of this task.<\/li>\n<li>Depending on the function, implement either underflow or overflow detection!<\/li>\n<li>Pay attention to the situation when all the elements are removed from the stack &#8211; do not use realloc for 0 bytes, use the free() function!<\/li>\n<\/ul>\n<h5><span class=\"ez-toc-section\" id=\"Debugging_function_for_the_stack\"><\/span>Debugging function for the stack<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>In order to get a bit better understanding of the stack contents, we&#8217;ll provide a debugging function. In reality, this kind of function goes against the limitations of the stack and may also not even be possible due to the implementation specifics!<\/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=\"Testing\"><\/span>Testing<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>During testing, pay extra attention to<\/p>\n<ul>\n<li>stack overflow<\/li>\n<li>stack underflow<\/li>\n<li>freeing the data after last element is popped.<\/li>\n<li>memory leak when the program exits when there are still values in the stack<\/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>Click me to see the output<\/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\/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; 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=\"Extra_task_1_W11-3_Practical_use_case_for_recursion\"><\/span>Extra task 1 [W11-3]: Practical use case for recursion<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>This extra task is given to you as a description of an algorithm. <strong>This is a completely independent task, that is not related to the original lab task solution!<\/strong><\/p>\n<p>NB! The variables in the description are given more to the likes of mathematicians (single letters). Use descriptive variable names when creating your program as is more suited for programming.<\/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>Once the task is complete, prepare the answer to the following questions. Once ready, present your task!<\/p>\n<ul>\n<li>Time complexity &#8211; compare the given algorithm and conventional linear search. How many comparisons do you need to find the result from an array that has\n<ul>\n<li>16 members<\/li>\n<li>256 members<\/li>\n<li>100 000 members<\/li>\n<\/ul>\n<\/li>\n<li>Give an esimate toe the complexity &#8211; e.g. constant, logarithmic, linear, exponential (<strong><a href=\"https:\/\/www.bigocheatsheet.com\">https:\/\/www.bigocheatsheet.com<\/a><\/strong>)<\/li>\n<li>If the array wouldn&#8217;t be sorted, would the algorithm still work?<\/li>\n<\/ul>\n<h4><span class=\"ez-toc-section\" id=\"Extra_task_2_W11-4_Improving_and_extending_the_stack\"><\/span>Extra task 2 [W11-4]: Improving and extending the stack<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>In this task, we will add a two extra functions and make it a bit more universal than the original solution.<\/p>\n<h4><span class=\"ez-toc-section\" id=\"Requirements-3\"><\/span>Requirements<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<ul>\n<li>Add the following functions to your stack\n<ul>\n<li>Duplicate() &#8211; takes the top element and creates a copy of it on the stack<\/li>\n<li>Swap() &#8211; swaps the two topmost elements around<\/li>\n<\/ul>\n<\/li>\n<li>These functions are only allowed to use the original Push(), Pop() and Peek() functions internally to access the stack!<\/li>\n<li>Change your Pop() and Peek()\u00a0 functions in a way that the following would apply\n<ul>\n<li>Stack must allow any integers (no reserved values)<\/li>\n<li>In the case of an underflow during popping from the stack, you can only provide a warning message, but not display the value!<\/li>\n<\/ul>\n<\/li>\n<li>Note: You&#8217;ll likely need to adjust your Push() function as well to accommodate the additional functions<\/li>\n<\/ul>\n<h4><span class=\"ez-toc-section\" id=\"Testing-2\"><\/span>Testing<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>These would be the important edge cases to test for in addition to the normal operation<\/p>\n<ul>\n<li>Pop(), when the stack is empty (do not display any value)<\/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; 2\r\nERROR: Stack underflow!<\/pre>\n<ul>\n<li>Duplicate(), when the stack is empty<\/li>\n<li>Duplicate(), when the stack is full<\/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; 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(), when the stack is empty<\/li>\n<li>Swap(), when the stack only has one member<\/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=\"After_this_class_you_should\"><\/span>After this class, you should<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>Know what a recursion is, including recursive functions and data structures<\/li>\n<li>Know how to write simple recursions<\/li>\n<li>Know about the existence of a tail recursion<\/li>\n<li>Know about the good and bad that recursions bring to the table<\/li>\n<li>Know use cases for recursions<\/li>\n<li>Know what an abstract data structure means<\/li>\n<li>Know what is a stack and what are its properties<\/li>\n<li>Know the use cases for stacks<\/li>\n<li>Know how to create a stack and its mandatory functions<\/li>\n<\/ul>\n<h3><span class=\"ez-toc-section\" id=\"Additional_materials\"><\/span>Additional materials<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>Lab materials Slides: Recursion Slides: Stack Examples done together in the lab Recursive factorial https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/factorial.c Tail-recursive factorial https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/factorial_tail.c Stack: https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/stack_base.c Alternative example of a stack that uses the SP as a pointer:\u00a0 https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/demokood\/stack_sp_as_pointer.c Lab tasks In this lab there are two base tasks, one completely independent extra task for recursion and one extra task as &hellip; <a href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en11-stack-and-recursion-2\/\" class=\"more-link\">Loe edasi <span class=\"screen-reader-text\">PR2EN11: Stack and recursion<\/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":[75,105],"tags":[],"class_list":["post-8436","post","type-post","status-publish","format-standard","hentry","category-labs","category-pr2_en"],"_links":{"self":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8436","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=8436"}],"version-history":[{"count":10,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8436\/revisions"}],"predecessor-version":[{"id":11449,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8436\/revisions\/11449"}],"wp:attachment":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/media?parent=8436"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/categories?post=8436"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/tags?post=8436"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}