$(5\mathrm{.}4\mathrm{.}15)$ The greatest common divisor of positive integers a and b can be defined recursively as follows: Basis Step: If a $=$ b$,$ then gcd$($ab$)=$ a$.$ Recursive Step: If a $<$ b$,$ then gcd$($ab$)=$ gcd$($ab a$),$ and if a $>$ b$,$ then gcd$($ab$)=$ gcd$($a b b$).$ Suppose that you are given two positive integers, a and b$.($a$)$ Give pseudocode for a recursive algorithm that computes the greatest common divisor of a and b$.$ For example, given a $=8$ and b $=12,$ your algorithm should return gcd$(812)=$ gcd$(84)=$ gcd$(44)=4.$ Given a $=8$ and b $=11,$ it should return gcd$(811)=$ gcd$(83)=$ gcd$(53)=$ gcd$(23)=$ gcd$(21)=$ gcd$(11)=1.($b$)$ State a lemma establishing the correctness of your algorithm. $($c$)$ Prove that your algorithm is correct. $[$Hint: When recursing, neither a nor b is guaranteed to get smaller. Rather, consider inducting over a $+$b$,$ a single integer that encapsulates the entire size of the problem.$]$