The loop invariant is true before the loop body and after the loop body, each time.

\(\text { Fact }(\mathrm{n})=\left\{\begin{array}{l} 1 \text { if } \mathrm{n}=0 \\ \mathrm{n} * \text { fact }(\mathrm{n}-1) \text { otherwise } \end{array}\right.\)
Recursive Algorithm:
Fact (n)
-- inputs: n
outputs: Fact=n!
if(n-0)- --base case
otherwise
1
else
n fact (n-1)--recursive step

A loop invariant is a condition [among program variables] that is necessarily true immediately before and immediately after, each iteration of a loop. A loop invariant is some condition that holds for every iteration of the loop.

No, the loop condition do not affect the loop invariant. Because the loop invariant is true at four points.
(i) at the start of loop
(ii) at the start of each iteration
(iii) at the end of each iteration
(iv) at the end of the loop

An expression involving variables, which remains unchanged by an assignment to one of these variables is called as an invariant of the assignment.

Recursion:
Recursion is another algorithm design technique, closely related to iteration, but more powerful. Using recursion, we solve a problem with a given input, by solving the same problem with" a part of the input, and constructing a solution to the original problem from the solution to the partial input.

(i) Establish the loop invariant at the start of the loop.
(ii) The loop body should so update the variables as to progress toward the end and maintain the loop invariant, at the same time.
(iii) When the loop ends, the termination condition and the loop invariant should establish the input-output relation

a loop variant, then it is true at four important points in the algorithm
(i) at the start of the loop (just before the loop).
(ii) at the start of each iteration (before loop body)
(iii) at the end of each iteration (after loop body).
(iv) at the end of the loop (just after the loop).

On the other hand let n be the number of games played and r be the number of players remaining in the tournament.
After every game, r will be reduced by 1.
r → no. of players remaining
n → no. of games played
If r=2 then n=1
As n increases, r decreases
n,r: n+1,r-1
n+r=(n+1)+(r-1)
= n + 1 + r - 1
= n + r
Therefore n + r is invariant.
n+r=1234 (No. of players initially)
The winner of the tournament is the player that is left after all other players have been knocked out.
After all the games, only one player (winner) is left out.
i. c. n = 1
Put n = 1 in (1)
n+r=1234 ....(1)
1+r=1234
r = 1234-1-1233
No. of games played = 1233

Let u - No. of tumblers right side up
v - No. of tumblers up side down
Initial stage: u = 0, v=7 (All tumblers upside down)
Final stage output: u=7, v=0 (All tumblers right side up)
Possible Iterations:
(i) Turning both up side down tumblers to right side up
u=u+ 2,   v=y-2   [u is even]
(ii) Turning both right side up tumblers to upside down.
u=u-2,  v=v+2  [u is even]
(iii) Turning one right side up tumblers to upside down and other tumbler from upside down to right side up.
u=u+1-1=u, v=y+1-1=v [u is even]
Initially u = 0 and continuous to be even in all the three cases. Therefore u is always even.
Invariant: u is even (i. e. No. of right side up tumblers are always even)
But in the final stage (Goal), u = 7 and v=0 i. e. u is odd.
Therefore it is not possible to reach a situation where all the tumblers are right side up.

The recursive definition can be expressed as a recursive solver for computing power(a, n).
power (a, n)
-- inputs: n is an integer, n \(\ge\) 0
-- outputs : an
if n = 0 -- base case
1
else --recursion step
a x power (a, n-1)
The recursive process with solvers for calculating power(2, 5).·

The recursive process resulting from power(2, 5)
power (2,5)
= 2 x power (2,4)
= 2 x 2 x power(2,3)
= 2 x 2 x 2 x power(2, 2)
= 2 x 2 x 2 x 2 x power (2,1)
= 2 x 2 x 2 x 2 x 2 x power (2,0)
= 2 x 2 x 2 x 2 x 2 x 1
= 2 x 2 x 2 x 2 x 2
= 2 x 2 x 2 x 4·
= 2 x 2 x 8
= 2 x 16
= 32

To solve a problem recursively, the solver reduces the problem to sub-problems, and calls another instance of the solver, known as sub-solver, to solve the sub-problem. The input ,size to a sub-problem is smaller than the input size to the original problem. When the solver calls a sub-solver, it is known as recursive call. The magic of recursion allows the solver to assume that the sub-solver (recursive call) outputs the solution to the sub-problem. Then, from the, solution to the sub-problem, the solver constructs the solution to the given problem.
As the sub-solvers go on reducing the problem into sub-problems of smaller sizes, eventually the sub-problem becomes small enough to be solved directly, without recursion. Therefore, a recursive solver has two cases:
1. Base case: The problem size is small enough to be solved directly. Output the solution. here must be at least one base case.
2. R-ecursion step: The problem size is not small enough. Deconstruct the problem into a sub-problem, strictly smaller in size than the given problem. Call a sub-solver to solve the sub problem. Assume that the sub-solver outputs the solution to the sub problem. Construct the solution to the given problem.
This outline of recursive problem solving technique is shown below.
solver (input)
if input is small enough
construct solution
else
find sub_Problems of reduced
input
solutions to sub problems =
solver for each sub .Problem
construct solution to the
problem from
solutions to the sub_problems
Whenever we solve a problem using recursion, we have to ensure these two cases: In the recursion step, the size of the input to the recursive call is strictly smaller than the size of the given input, and there is at least one base case.

To solve a problem recursively, the solver reduces the problem to sub-problems, and calls another instance of the solver, known as sub-solver, to solve the sub-problem. The input size to a sub-problem is smaller than the input size to the original problem. When the solver calls a sub-solver, it is known as recursive call. The magic of recursion allows the solver to assume that the sub-solver (recursive call) outputs the solution to the sub-problem. Then, from the solution to the sub-problem, the solver constructs the solution to the given problem.
As the sub-solvers go on reducing the problem into sub-problems of smaller sizes, eventually the subproblem becomes small enough to be solved directly, without recursion. Therefore, a recursive. solver has two cases:
1. Base case: The problem size is small enough to be solved directly. Output the solution. There must be at least one base case.
2. Recursion step: The problem size is not small enough. Deconstruct the problem into a subproblem, strictly smaller in size than the given problem. Call a. sub-solver to solve the subproblem.
solver (input)
if input is small enough
construct solution
else
find sub_problems of reduced
input
solutions to sub_problems = solver for each sub_problem
construct a solution to the problem from
solutions to the sub_problems
Whenever we solve a problem using recursion, we have to ensure these two cases: In the recursion step, the size of the input to the recursive call is strictly smaller than the size of the given input, and there is at least one base case.

power (5,2) = 5 × 5  = 25
power (x, n) raise x to the power n
Algorithm :
power (x, n) 
If n = 0 -- base case
1
else -- rrecursion step
if n is odd
x * power (x, n - 1)
else 
p = power (x, n/2)
p * p
To find a ¹⁰ :