Simple Strategies for Developing Algorithms

Simple Strategies for Developing Algorithms

AU : Dec.-19, Marks 8

There are two commonly used strategies used in developing an algorithm

1. Iteration 2. Recursion

Basically iteration and recursion perform the same kind of task.

1. Iteration

In iteration the control statements such as for loop, do-while loop or while is used. The loop continues its execution until the terminating condition is reached.

For example - Consider an example of factorial

One can define the factorial of some number n as a product of all the integers from n to 1.

For example, if the 5 factorial has to be calculated then, it will be = 5*4*3*2*1 = 120.

Similarly 3! = 3*2*1 = 6 and the 0! = 1.The exclamation mark is used to denote the factorial. We may write the definition of factorial function as -

n! = 1 if n= = 0

Otherwise, n! = n*(n-1)*(n-2)*...*1 if n > 0

If the value of n is any of the 0,1,2,3,or 4 then the definition will be -

0! = 1

1! = 1

2! = 2*1

3! = 3*2*1

4! = 4*3*2*1

Here we are presenting an algorithm that takes the input as value of n and returns the result of n!.

Algorithm for factorial function using iterative definition :

1. prod = 1;

2. x= n;

3. while (x > 0)

4. {

5. prod = prod*x;

6. x--;

7.}

8. return(prod);

Such an algorithm is called as an iterative algorithm because it calls explicit repetition of some process (in our example the process multiplication and decrementing x by 1) until certain condition is met (for example x > 0).

2. Recursion

Definition : Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially.

Usually recursion involves a function calling itself.

Properties of Recursion

There are three important laws of recursion:

1. A recursive algorithm must have a base case.

2. A recursive algorithm must change its state and move toward the base case.

3. A recursive algorithm must call itself, recursively

For example : (Fig. 1.7.1)

Fig. 1.7.1 Recursion

Comparison between Iteration and Recursion

Iteration

1. Iteration is a process of executing certain set of instructions repeatedly, without calling the self function.

2. The iterative functions are implemented with the help of for, while, do-while programming constructs.

3. The iterative methods are more efficient because of better execution speed.

4. Memory utilization by iteration is less.

5. It is simple to implement.

6. The lines of code is more when we use iteration,

Recursion

1. Recursion is a process of executing certain set of instructions repeatedly by calling the self function repeatedly.

2. Instead of making use of for, while, do-while the repetition in code execution is obtained by calling the same function again and again over some condition.

3. The recursive methods are less efficient.

4. Memory utilization is more in recursive functions.

5. Recursive methods are complex to implement

6. Recursive methods bring  compactness in the program.

Review Question

1. Identify the simple strategies for developing an algorithm. AU : Dec.-19, Marks 8