Due Date: Wednesday, March 1, 2023.

Draw the recursion tree for the function merge sort seen in C243 applied to the array
____________________________________
| 17 | 8 | 3 | 11 | 18 | 2 | 5 | 1 |

Here is a small C++ program implementing and testing the merge sort:
merge_sort.cc
merge_sort.h
merge_main.cc

Write a small C++ program that defines a recursive function GCD based on the model of the Lisp function discussed in the lecture.

In the main function, write a loop (while or do) that repeats the following actions: ask the user to enter two numbers, compute their GCD and output it, until the user enters 0 for one of the numbers.

You can use a single source file for this, or two of them. If you use only one, then assuming that it is called gcdTest.cc, you can compile it with the command

g++ gcdTest.cc -o gcd

Then you can execute it with the command gcd or ./gcd if the first one doesn't work.

For each of the following functions, state whether or not they are tail recursive. Justify your answer.

a.

(defun select-i (L i)
  (cond 
   ((not L) nil)
   ((= i 0) (car L))
   (t (select-i (cdr L) (- i 1)))))

b.

(defun length (L)
  (cond 
   ((not L) 0)
   (t (+ 1 (length (cdr L))))))

c. The function merge_sort from Exercise 1.

Turn in all the C++ code you wrote in one or several files, inluding header files if any, and exercise 1 and 3 in a text, image, or pdf format. Upload them to Canvas, Assignments, Homework 7.