\(\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

1. Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller sub problems until user gets in to a small problem that it can be solved trivially.
2. Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.

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

In iteration, the loop body is repeatedly executed as long as the loop condition is true. Each time the loop body is executed, the variables are updated.
However, there is also a property of the variables which remains unchanged by the execution of the loop body. This unchanging property is called the loop invariant.

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

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.

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 ¹⁰ :