#include

#include

$/*$ compute x$*$y with addition $*/$

uint$64\_$t recmul$($uint$64\_$t a$,$uint$64\_$t b$)\{$

if $($a$==0||$ b$==0)$

return $0$;

else if $($a$==1)$

return b;

else

return b $+$ recmul$($a$-1,$b$)$;

$\}$

$/*$ compute x to the yth power using only addition $*/$

uint$64\_$t recexp$($uint$64\_$t x$,$uint$64\_$t y$)\{$

if $($y $==0)$

return $1$;

else if $($y$==1)$

return x;

else

return recmul$($x$,$recexp$($x$,$y$-1))$;

$\}$

int main$()\{$

printf$("$recexp$(2,2)$ returned $\%$lu$.$

$",$recexp$(2,2))$;

return $0$;

$\}$

In this problem you will trace the evolution of

the state of the stack across the series of recursive calls. With each function call the return address

and the contents of some registers are stored in the stack, creating what we call a $$stack frame$$ for

that invocation of the function.

For this problem you will diagram the changes to the state of the stack by indicating the function

invoked and the parameters to that function, and the return address to which that function will

return when that invocation completes execution. An example of what this looks like for the given

code, with main invoking recexp$(2,2),$ is shown below. In these diagrams, lower addresses are at

the bottom of each stack; thus the stack grows downward in the figures. $($We don$$t care about the

return address from main.$)$

Create a similar sequence of diagrams showing the stack evolution if the call from main is recexp$(3,3).$

$($Hint$.$ Use gdb$.$ Set breakpoints in the two recursive functions, and each time you hit a breakpoint,

use the where command. Note that stack frames are listed in gdb from the top down.$)$

$2$