Hi folks!
I haven't found one in this forum yet so here is a little tutorial about how recursivity works in most programming languages since it can be such a useful tool!
I will use C++ as an example here but this works in a lot of languages.
What is recursivity ?
A function is called recursive if it calls itself. A recursive function has often two basic cases :
- Either we are in an end case and we return a result
- Or we are not and we call the function again to calculate a sub-result
An example is better than words
A common example of recursivity is the factorial function, which is f(n) = n * (n-1) * ... * 2 * 1
It can also be fully defined like this :
- f(1) = 1
- for all n > 1, f(n) = n * f(n - 1)
For instance, if we want to calculate f(3) = 3 * f(2) = 3 * (2 * f(1)) = 3 * (2 * 1) = 6
So we can define a function like so :
Code:
int factorial(int n)
{
if (n == 1)
return 1;
else
return n * factorial(n - 1);
}
Why ?
In simple cases like the factorial function, recursivity may not be useful. However, there are more complex cases that lead to much better code when created recursively.
For instance, imagine you have a tree containing integers at its leaves. Then in order to sum all these integers, you first need to calculate the sum of all the child branches of the root to calculate the sum of the whole tree.
This is where recursivity comes in handy.
Code:
int sum(tree t)
{
int result = t.value;
for (tree child : t.children)
{
result += sum(child);
}
return result;
}
I hope it may help some beginner programmers to understand this useful concept.
Good bye!