4. Consider the following program specification and implementation for determin- ing the mth Fibonacci number fm for me N. (Recall that the Fibonacci sequence is defined as fo=0, fi = 1, and fm = fm-1+fm-2 for m > 2.) rec_fib(m) for m EN = (1) if m O return 0 (2) else if m 1 return 1 (3) else return rec fib(m-1) + rec fib(m - 2) {output is fm, where fm is the mth Fibonacci number} 2 CS-MATH 240: Spring 2021 (a) Trace the execution of rec fib(m) for the calls m 1 up to m = 5. It may help to draw this as a branching tree, as on page 387 on Rosen (at the beginning of subsection 5.4.3). (b) Prove the correctness of rec fib by arguing (i) partial correctness and (ii) termination