Recursive or iterative, which algorithm is better

discrete-mathematical-algorithm-data-structures

https://leanpub.com/discretemathematicalalgorithmanddatastructures

The advantage of using recursion is its shortness, cleanliness, and moreover, it is closer to our discrete mathematical definitions. If you think and model your code keeping the mathematical conceptions in your mind, then recursion is close to your definition.
It is more evident when we use recursion in finding the Fibonacci series. Mathematically, the Fibonacci is defined as the following:

Fibonacci of 1 or 2 is 1
Fibonacci of F (for F > 2) is Fibonacci of (F - 1) + Fibonacci of (F – 2)

If we want to find the Fibonacci series using recursion, it is not only the simplest version, but also mathematically similar.
Watch the next line of code snippet.

package fun.sanjibsinha.recursive;

public class AlgoFibTwo {

static int getFibonacci(int f) {
if ((f == 1) || (f == 2)){
return 1;
} else {
return (getFibonacci(f - 1) + getFibonacci(f - 2));
}
}

public static void main(String[] args) {

int newNumber = 6, result;
result = getFibonacci(newNumber);
System.out.printf("Fibonacci series of " + newNumber + " = " + result);
System.out.printf("");
System.out.printf("");
}

}

//output of the above code

Fibonacci series of 6 = 8

We can do the same thing using iterative way, but it does not reflect the mathematical conception as the recursion does. The next code snippet shows us the same thing.

package fun.sanjibsinha.recursive;

public class AlgoFibOne {

static int getFibinacci(int f) {
int k1, k2, k3;
k1 = k2 = k3 = 1;
for (int j = 3; j <= f; j++) {
k3 = k1 + k2;
k1 = k2;
k2 = k3;
}
return k3;
}

public static void main(String[] args) {

int newNumber = 6, result;
result = getFibinacci(newNumber);
System.out.printf("Fibonacci series of " + newNumber + " = " + result);
System.out.printf("");
System.out.printf("");
}
}

//output of the above code
Fibonacci series of 6 = 8

Ability to simulate the mathematical models cannot always give the moral support to the recursions. Because there are many other factors while we program, we need to keep them in our mind.
Maintaining that the recursive versions are slower than the iterative versions, we may still want to adopt it for some reasons. When the code is heavy in iterative versions, it is much simpler to adopt the recursions, it also easier to debug and maintain. Whatever our reasons to adopt the recursions, slowing down the program may cost at the end.
We cannot save the memory space, we cannot speed up the execution; yet, in some cases, recursions are essential.

As we progress, we will find that later.

What is Algorithm?

discrete-mathematical-algorithm-data-structures

https://leanpub.com/discretemathematicalalgorithmanddatastructures

Algorithm is expressed as a set of steps. By describing the actions at each step we instruct the computer do something. Usually we can use any natural language to describe the actions to perform at each step.

Consider this simple description.

• 1. Enter one integer
  2. Enter another integer
  3. Compare both integers and return the maximum value
  4. Compare both integers and return the minimum value

In C++ programming language, on one hand, we can create generic functions to find the maximum or minimum value; and, on the other, we can take help from the ‘algorithm’ template library to find the same values.

Every high level language comes with its own algorithm library. They do so for one reason. Any system of counting or calculation by means of a device like computer involves following a steps or directions. Computer scientists use the word ‘algorithm’ to describe such as ‘set of directions’.

In some cases, these directions could be simple as described above. In most cases, it is much more complex. For complex cases, we need the help of ‘algorithm’ library. Otherwise, we have to do the low-level plumbing, which is much more time consuming and that takes us away from building other important parts of any application.

Historically, the derivation of this word has some interesting facts. At the beginning of ninth century an Arabian mathematician wrote a book called ‘Kitab al jabr w’al muqabala’ (Rules of Restoration and Reduction). The word ‘algebra’ comes from the title of the book. This textbook introduced the use of Hindu numerals and included a systematic discussion of fundamental operations on integers.

The word ‘algorithm’ comes from the name of the mathematician, Abu Ja’far Mohammed ibn Musa al-Khowarizmi.

One of the most famous and well known algorithms is of course Euclid’s Algorithm. It is a process for calculating the greatest common divisor (GCD) of two integers.
We can illustrate this algorithm in the following way.

• 1. Take two integers x and y
  2. Divide y by x and get the remainder as r
  3. Now replace the value of x with the value of r and replace the value of y with the value of x
  4. Again divide y by x
  5. This process will continue until we get r = 0
  6. Once we get r = 0, stop the calculation, x is the GCD

Notice that the algorithm is expressed as a set of steps. Each step describes some action to take. The important thing is to describe the actions to be performed clearly and unambiguously.

Let us summarize this introductory part on algorithm in one sentence.
Data go inside the computer as inputs, algorithm takes charge, processing the data and after that the data as outputs come out.

By the way, people often mistake the word ‘data’ as singular; but, it is actually a plural form of the Latin word ‘datum’. Since we have used this word too often in our discourse, and will use in future, therefore, for the curious readers I opened up the Oxford dictionary and searched for the word: datum.

Oxford dictionary defines datum as “A thing given or granted; a thing known or assumed as a fact, and made the basis of reasoning or calculation; a fixed starting-point for a series of measurements etc.” It has also made it clear that the plural form of ‘datum’ is ‘data’.

For instance, in Java we have Collection class and in C++ we have containers that manage this data structure part. We are going to find out how they are related in the next post.