dimanche 28 février 2016

Indirect Recursion - A Natural Phenomenon

Indirect recursion could be noticed in seeds and trees: a seed ends up to be a tree, and the latter produces many seeds, which themselves become trees and so forth.





An interesting case was beautifully described in the Qur'an, chapter 2, verse 261, a plain description that is easy  to represent:

"The example of those who spend their wealth in the way of Allah is like a seed [of grain] which grows seven spikes; in each spike is a hundred grains. And Allah multiplies [His reward] for whom He wills. And Allah is all-Encompassing and Knowing". (Source).

Regardless of the religious aspects, one can notice the exponential growth of seeds, which is appreciated in agriculture, but seriously deprecated in Computer Science.


If we represent this phenomenon (seeds and spikes) as a Java algorithm:


void seed(x) {
    System.out.println("Seed " + x);
    for (i = 0; i < 7; i ++) {
        spike(i);
    }
}

void spike(y) {
    System.out.println("Spike " + y);
    for (j = 0; j < 100; j ++) {
        seed(j);
    }
}

Let's refer to seed as f(x) and spike as g(x):




Clearly, calling f(x) will make 700 indirect "calls" of itself, in an indirect fashion.

Good deeds with exponential seeds is surely a nice reward, but such exponential sub-routine calls will only have a negative impact on performances.


One should be careful with recursion, direct or indirect.