What is Recursion about?

Recursive drawing example

“A method of defining a sequence of objects, such as an expression, function, or set, where some number of initial objects are given and each successive object is defined in terms of the preceding objects. The Fibonacci sequence is defined by recursion.”

Lets see this example

A function written in C

As you can see the function _pow_recursion() its calling itself in 2 ocassions, but what does this funcition do? its just a neat recursive way of x at the power of y

X at the power of Y

A recursive function call itslf a infinite number of times or until they met certain condition given by the user, like in the example above it stops when y is equal to 0 (y increases its own value when y is negative and y decreases its own value when y is positive)

Giving values to x and y

Lets see 1 example with y as a positve number and another with y as a negative number

You can tell by yourself that ²³ = 8 and 2^-3 = 1/²³ = 0.125

for y = 3 the computer does something like this

2³ = 2x2²
2² = 2x2¹
2¹ = 2x1
2^0 = 1

for y = -3 the computer does something like this

2^-3 = 1/(2x2^-²)
2^-2 = 1/(2x2^-¹)
2^-1 = 1/(2x1)
2^0 = 1

The computer separates each call of the function and put them in an stack until they exit the loop and then solves it from the bottom to the top