## среда, 10 февраля 2016 г.

### A word for recursion

Personally, I think that parents must teach recursion to their children as early as they give them counting rods for the first time. The first lesson about counting must be that every number is the previous number plus one
``````int getNthNumber(int n) {
int nthNumber = getNthNumber(n-1) + 1;
return nthNumber;
}``````
Of course, they need to define that the first number is zero
``````int getNthNumber(int n) {
if (n == 1) // first number is zero by definition
return 0;
int nthNumber = getNthNumber(n-1) + 1;
return nthNumber;
}``````
And there is a second lesson about recursion, which is that the first number have to have the index of zero, too
``````int getNthNumber(int n) {
if (n == 0) // first number is zero by definition
return 0;
int nthNumber = getNthNumber(n-1) + 1;
return nthNumber;
}``````
Now, given such a great and powerful tool, they can do some great and powerful maths. For example, they can start with "simply" adding `m` to `n`. Yes, they have to define what "adding" is, and it will be "finding m-th number after n"
``````int add(int n, int m) {
if (m == 0)
return getNthNumber(n);
return sum;
}
``````
With this power they can do anything! They can calculate an N-th item in an arithmetic progression! Of course, first defining it as a sequence of numbers such that the difference between the consecutive members is constant
``````int getNthItemOfProgression(int n, int first, int step) {
if (n == 0)
return getNthNumber(first); // first number is first number by definition
int previousItem = getNthItemOfProgression(n-1, first, step);
return nthItem;
}
``````
And why stop here? They can calculate any number for Table of Pythagoras!
``````int getPythagoras(int x, int y) {
return getNthItemOfProgression(x, 0, y);
}
``````
They can even do factorials!
``````int getFactorial(int n) {
if (n <= 1)
return getNthNumber(n);
int nthFactorial = getPythagoreanNumber(getFactorial(n-1), n);
return nthFactorial;
}
``````
And yes, every child have a right to know what is going on there, when they make a recursive call to a function
``````int getNthNumber(int n) {
// starting from the ground...
int recursionDepth = 0;
// they go deeply into the darkness of recursive calls...
while (n > 0) {
n--;
recursionDepth++;
}
int result = 0; // (first number is zero by definition)
// and then slowly make their way back to the light...
while (recursionDepth-- > 0) {
result = result + 1; // where each number equals previous number plus one
}
return result;
}
``````
Well, this is getting creepy. I think that third lesson about recursion should be that there is a multiplication already exists.