recursion the power of recursion evidently lies in the possibility of defining an infinite set of objects by finite statement in the same manneran infinite number of computations can be described by finite recursive programeven if this program contains no explicit repetitions -"algorithms data structures programs, wirth recursion is an approach to problem solving where the solution depends partially on solutions to smaller instances of related problems it is often appropriate when the input is expressed using recursive rulessuch as computer grammar more generallysearchingenumerationdivideand-conquerand decomposing complex problem into set of similar smaller instances are all scenarios where recursion may be suitable recursive function consists of base cases and calls to the same function with different arguments two key ingredients to successful use of recursion are identifying the base caseswhich are to be solved directlyand ensuring progressthat is the recursion converges to the solution both backtracking and branch-and-bound are naturally formulated using recursion recursion boot camp the euclidean algorithm for calculating the greatest common divisor (gcdof two numbers is classic example of recursion the central idea is that if xthe gcd of and is the gcd of and for examplegcd( gcd(( by extensionthis implies that the gcd of and is the gcd of and mod xi gcd( gcd(( mod gcd( mod def gcd(xy)return if = else gcd(yx ysince with each recursive step one of the arguments is at least halvedit means that the time complexity is (log max(xy)put another waythe time complexity is ( )where is the number of bits needed to represent the inputs the space complexity is also ( )which is the maximum depth of the function call stack (the program is easily converted to one which loopsthereby reducing the space complexity to ( now we describe problem that can be elegantly solved using recursive divide-and-conquer algorithm triomino is formed by joining three unit-sized squares in an -shape mutilated chessboard (henceforth mboardis made up of unit-sized squares arranged in an squareminus the top-left squareas depicted in figure (aon the next page suppose you are asked to design an algorithm that computes placement of triominoes that covers the