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

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.

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.

Iteration:
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. Loop invariant is the key to construct and to reason about iterative algorithms.

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

Let P(m, n) = m + 3n. Then
P(m, n) [m, n := m + 3, n -1]
= m + 3n [m, n := m + 3, n -1]
= (m + 3) + 3(n -1)
= m + 3 + 3n - 3
= m + 3n
= P(m, n)
Since (m + 3n) [m, n : = m + 3, n - 1] = m + 3n, m + 3n an invariant of the assignment m, n := m + 3, n-1.

Let P (p, c) = p - c. Then
P (p, c) [p, c := p + 1, c + 1]
= p - c [p, c := p + 1, c + 1]
= (p + 1)-(c + 1)
= p-c
= p(P, c)
Since (p - c) [p, c := p + 1, c + 1] = p - c, p - c is an invariant of the assignment p, c := p + 1, c + 1.

Recursion is another algorithm design technique, closely related to iteration. 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) 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.
(ii) However, there is also a property of the variables which remains unchanged by the execution of the loop body.
(iii) This unchanging property is called the loop invariant. Loop invariant is the key to construct and to reason about iterative algorithms.

The loop invariant is true in four crucial points in a loop. Using the loop invariant, we can construct the loop and reason about the properties of the variables at these points.
Example:
Design an iterative algorithm to compute aⁿ , Let us name the algorithm power(a, n).
For example,
power(10, 4) = 10000
power (5 , 3) = 125
power (2 , 5) = 32
Algorithm power (a, n) computes aⁿ by multiplying a cumulatively n times.

The specification and the loop invariant are shown as comments.
power (a, n)
-- inputs: n is a positive integer
-- outputs: p = aⁿ
p, i := 1 ,0
while i \(\neq \) n
-- loop invariant: p = a ⁱ
p, i:=p x a, i+ 1
The step by step execution of power (2, 5) is shown in Table. Each row shows the values of the two variables p and i at the end of an iteration, and how they are calculated. We see that p = a' is true at the start of the loop, and remains true in each row. Therefore, it is a loop invariant.

When the loop ends, p = a' is still true, but i = 5. Therefore, p = a5. In general, when the loop ends, p = an. Thus, we have verified that power(a, n) satisfies its specification.

In a loop, if L is an invariant of the loop body B, then L is known as a loop invariant.
while C
--L
B
-- L
The loop invariant is true before the loop body and after the .loop body, each time. Since L is true at the start of the first iteration, L is true at the start of the loop also (just before the loop). 'Since L is true at the end of the last iteration, L is true when the loop ends also (just after the loop). Thus,.if L is a loop variant, then it is true at four important points in the algorithm, as annotated in the algorithm.
1.  At the start of the loop (just before the loop)
2. at the start of each iteration (before loop body)
3. at the end of each iteration (after loop body)
4. at the end of the loop (just after the loop)
1. -- L, start of loop
while
C
2. -- L, start of iteration
B
3. -- L, end of the iteration
4. -- L, end of the loop