The power of recursion!

Function invocation

When we call a function, an execution context gets placed on the execution stack. Let’s break this down some more.

A stack is a data structure that operates on a “Last In, First Out” basis.

An item is “pushed” onto a stack to add to it, and an item is “popped” off the stack to remove it.

The name “stack” for this type of structure comes from the analogy to a set of physical items stacked on top of each other. Using a stack is a method of ordering certain operations for execution.

An execution context forms upon a function invocation. This context places itself on an execution stack, an order of operations. The item that is always first in this stack is the global execution context. Next up are any function created contexts.

These execution contexts have properties, an Activation Object, and a “self” binding. The “self” binding is a reference back to this execution context. The Activation Object includes: parameters passed, declared variables, and function declarations.

By the way, we use “self” since we're using the Python programming language. On other programming languages like JavaScript you usually use a “this” binding.

With recursion, we are waiting for return values coming from other execution contexts. These other contexts are higher up the stack. When the last item on the stack finishes execution, that context generates a return value. This return value gets passed down as a return value from the recursive case to the next item. That execution context is then popped off the stack.

Recursion

According to geeksforgeeks, recursion is the process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function.

A recursive function is a function that calls itself until a “base condition” is true, and execution stops.

While false, we will keep placing execution contexts on top of the stack.

We may run into a “stack overflow” if we run out of memory to hold items in a stack.

In general, a recursive function has at least two parts: a base condition and at least one recursive case.

Let’s look at 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);
}

The power (or exponent) of a number says how many times to use the number in a multiplication. Here we are trying to find 2 to the power of 3.

The _pow_recursion() function is defined by having 2 inputs. x is a number and y is how many times we want the number xmultiplied by x . At the end of the day, we want to get 8 as a result. since 2 x 2 x 2 is equal to 8.

Next, the recursive case states:

“If the y parameter is not 0, then we will pass value of calling this function again:

• with y + 1 / x if y is a negative number
• with y — 1 * x if y is a positive number

So if we call _pow_recursion(1, 0) , the function returns 1 and never hits the recursive case.

We can see what is happening if we insert a debugger statement into the code and use a development too to see the stack.

1. The execution stack places _pow_recursion(2, 3) with x = 2 and y = 3 — 1 then multiplied by x which is 2. The base case is false, so we enter a recursive condition.
2. The execution stack places _pow_recursion(2, 2) a second time with x = 2 and y = 2 — 1 then multiplied by x which is 2. The base case is false, so we enter a recursive condition.
3. The execution stack places _pow_recursion(2, 1) a third time with x = 2 and y = 1 — 1 then multiplied by x which is 2. The base case is false, so we enter a recursive condition.
4. The execution stack places _pow_recursion(2, 0) a fourth time with x = 2 and y is now 0 . The base case is true, so we return 1.

At this point, we have decreased the argument y by one on each function call till we reach a condition to return 1.

5. From here the last execution contexts completes, y == 0 , The stack gets popped and the function returns 1.

6. The stack gets popped, and the return value is 2. (1 x 2).

7. The stack gets popped, and the return value is 4. (2 x 2).

8. Finally, the last item from the stack gets popped and the return value is 8. (4 x 2). There’s nothing left in the stack. That means 8 serves as the final value.

Conclusion:

There are plenty of ways to use recursion, examples of these are binary search trees, graphs, and heaps. It also works on sorting algorithms like quicksort and heapsort.

I hope you now get a good understanding of how recursion works. Thank you for your time in reading this guide!

Resources:

Recursion is not hard: a step-by-step walkthrough of this useful programming technique

Power

Recursion - GeeksforGeeks