$19\mathrm{.}14$ Lab $11$: A general method of removing recursion

Lab Exercise

The focus of today$$s lab is to practice removing recursion. We$$ve encountered this technique before, such as when implementing iterators for binary tree objects. By the end of this exercise, you$$ll understand how to replace recursive logic with iterative approaches while preserving functionality.

Start by reviewing the downloadable programs lab$11$a$.$ccp and lab$11$b$.$cpp which feature recursion. They are solving the same problem but b adds animation element.

Then begin looking at the lab and focus on the one function where you have to use a stack rather than recursion.

Given code

#include #include $/*$ Three towers numbered $123$ Contain a stack of disk on $1.$ Moving one at a time move disk from tower to tower. Never allow a large disk on top ofg a small disk. Move the disk from tower $1$ to tower three. $*/$ void move $($int from, int to$)$; void print$($std::vector &vec$)$; void solve$\_$tower$\_$without$\_$recursion$($int from, int to$,$ int count$)\{$ std::vector stack; $//$init the stack $--$ push from, to$,$ and count while $(!$stack.empty$())\{$ print$($stack$)$; $//$do not delete $($grading engine requires$)//$pop from, to$,$ and count in reverse order of pushes $/*$ TODO: your code here $*///$handle count $=1($move$)/*$ TODO: your code here $*///$handle count $>1//$reverse the order $//$the tail call goes on the stack first $($so we do it last$)//$instead of a recursive call just push args onto a stack instead $/*$ TODO: your code here $*///$instead of move in the middle move gets pushed onto the stack too $//$we will identify it because the count will be $1/*$ TODO: your code here $*///$reverse the order $//$first recursive call goes on the stack last $($so we do it first$)//$instead of a recursive call just push args onto a stack instead $/*$ TODO: your code here $*/\}\}$ void print$($std::vector &vec$)\{$ for $($std::vector::iterator it $=$ vec.begin$()$; it $!=$ vec.end$()$; it$+=3)\{$ std::cout it itit; $\}$ std::cout $$ std::endl; $\}//$ a slight change is made here to more closely echo the non recursive version void solve$\_$tower$($int from, int to$,$ int count$)\{$ if $($count $==1)\{$ move$($from$,$ to$)$; return; $\}$ int third$\_$tower $=6-($from$+$to$)$; solve$\_$tower$($from$,$ third$\_$tower, count$-1)$; move$($from$,$ to$)$; solve$\_$tower$($third$\_$tower, to$,$ count$-1)$; $\}$ int main$($int argc, char $*$ argv$[])\{$ solve$\_$tower$\_$without$\_$recursion$(1,3,3)$; return $0$; $\}$ #define disk$1"======"$ #define disk$2"=========="$ #define disk$3"=============="$ #define nodisk $"||"$ void move $($int from, int to$)\{$ std::cout $$ "Move disk from $"$ from to $"$ to $$ std::endl; $//$switch to zero base from$--$; to$--$; static std::string stack$[3][3]=\{\{$disk$1,$nodisk,nodisk$\},\{$disk$2,$nodisk,nodisk$\},\{$disk$3,$nodisk,nodisk$\}\}$; int topfrom $=0$; while $($stack$[$topfrom$][$from$]==$nodisk$)++$topfrom; int topto $=2$; while $($stack$[$topto$][$to$]!=$nodisk$)--$topto; std::swap$($stack$[$topfrom$][$from$],$stack$[$topto$][$to$])$; std::cout $$ std::endl$$ std::endl$$ std::endl$$ std::endl; std::cout $$ std::endl$$ std::endl$$ std::endl$$ std::endl; std::cout $$ std::endl$$ std::endl$$ std::endl$$ std::endl; std::cout $$ std::endl$$ std::endl$$ std::endl$$ std::endl; std::cout $$ std::endl$$ std::endl$$ std::endl$$ std::endl; std::cout $$ nodisk $$ nodisk $$ nodisk $$ std::endl; std::cout $$ nodisk $$ nodisk $$ nodisk $$ std::endl; for $($int k $=0$;k$<mn>3</mn>$;k$++)$ std::cout $$ stack$[$k$][0]$ stack$[$k$][1]$ stack$[$k$][2]$ std::endl; std::cout std::endl$$ std::endl; $\}$