board of Figure . . Now, we have four corner-covered boards, each of size n- × n- . Figure .
: Recursive process of covering a corner-covered board of size x Chapter Page - - We have sub-problems whose size is strictly smaller than the size of the given problem. We can solve each of the sub- problems recursively. tile board of size n if n = -- base case • Iteration repeats the two steps of evaluating a condition and executing a statement, as long as the condition is true. • An expression involving variables, which remains unchanged by an assignment to one of these variables, is called an invariant of the assignment.
• An invariant for the loop body is known as a loop invariant. • A loop invariant is true. • (a) at the start of the loop (just before the loop) • (b) at the start of each iteration (before loop body) • (c) at the end of each iteration (after loop body) Points to Remember • (d) at the end of the loop (just after the loop) • When a loop ends, the loop invariant is true. In addition, the termination condition is also true.
• Recursion must have at least one base case. • Recursion step breaks the problem into sub-problems of smaller size, assumes solutions for sub-problems are given by recursive calls, and constructs solution to the given problem. • In recursion, the size of input to a sub- problem must be strictly smaller than the size of the given input. cover the squares with one triominoe else -- recursion step divide board into of size n- place a triominoe at centre of board , leaving out the sub -board tile each of size n- The resulting recursive process for covering a x corner-covered board is illus trated in Figure .