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.

Customers are waiting in a line at a counter. The man at the counter wants to know how many customers are waiting in the line.

Instead of counting the length himself, he asks customer A for the length of the line with him at the head, customer A asks customer B for the length of the line with customer B at the head, and so on. When the query reaches the last customer in the line, E, since there is no one behind him, he replies 1 to D who asked him. D replies 1 + 1 = 2 to C, C replies 1 + 2 = 3 to B, B replies 1 + 3 = 4 to A, and A replies 1 + 4 = 5 to the man in the counter

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.

The outline of recursive problem-solving technique.
solver (input)
if the input is small enough
construct solution
else
find subproblems of reduced input solutions to subproblems = solver for each subproblem construct a solution to the problem from solutions to the subproblems
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 loop at least one base case.