The concept of Recursion
Recursion, what is it and why use it?
? Recursion is a programming technique using a function that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first.
All of this happens in the stack.
Stack example:
Why use it?
? Recursion makes many tasks easy especially?for solving problems that can be broken down into smaller, repetitive problems.
Here are some examples for Recursion use cases
? Quicksort Algorithm
? Calculating Fibonacci Sequence
? Calculating Power
? Calculating Factorial
Speaking of Calculating Power, what would it look like to calculate (x) raised to the power of (y) in recursion?
Take this for an example
float _pow_recursion(float x, float y)
{
if (y == 0)
return (1);
if (y < 0)
return (_pow_recursion(x, y + 1) / x);
return (_pow_recursion(x, y - 1) * x);
}
To explain this, it is easiest to show it in a little drawn diagram
Let (x) = 2 and (y) = 13
This is how it would look like recursively
As we build the stack with the function calls, Upon reaching the condition y == 0
All of the returns of previous functions ripple and get multiplied, then we get our result, in this case: 8192
Hence?_pow_recursion(2, 13) = 8192