Recursive Algorithms

The main idea of recursion is solve a problem, solve a subproblems that are a smaller instances of the same problem, and then use the solution to that smaller instance to solve the original problem.

How Recursion Works in Memory ?

when we start the execution of program, memory is allocated for computations. The program can be divided it into segments like variables, loops, constants, functions. The memory semantics are different for each segment. Our compiler utilizes the different regions of memory to execute the program, the regions are:

1. Stack
2. Static data area
3. Code area
4. Heap

Stack region is similar to the Stack data structure; it follows the LIFO, last in fast out principle. The stack stores the information about function call for the duration of its execution. Whenever we call a function, our compiler allocates some storage in the stack in a region called activation record or simply a stack frame. In simple terms Stack is an array where each block is a stack frame that stores some information about the function. The top frame is called a Stack pointer which will be updated to refer the most recent activation call.

The stack frame can be further divided into five separate regions to store different information about an activation call.

1. Incoming parameters
2. Return value
3. Temporary storage
4. Saved state information
5. Outgoing parameters

Incoming parameters are the parameters provided in the activation call. Outgoing parameters are the parameters that are passed onto the next call to function(next activation call). Temporary storage stores the data used during the execution. Saved state information is the saved information for reference when the activation terminates. The return value is simply the return of a function.

Code area contains the instructions which your program executes as it advances.

Static data area stores the data that is declared by the program for the duration of its life cycle. Global variables, constants (Read-only) reside here along with the variables which can be modified during runtime.

Heap or dynamic memory is the memory allocated at the runtime. When we cannot pre-allocate storage for our program, we may generally request, reserve, and free the memory as per our need. Malloc, calloc, realloc for memory allocation, and free to deallocate are used in C but most other programming languages do it by default by using something called ARC (Automatic reference control if ARC is 0 for some object then the memory gets freed).

Memory Allocation in Recursion

when a function is called, its memory is allocated on a stack. . Each program has a reserved region of memory referred to as its stack. When a function executes, it adds its state data to the top of the stack. When the function exits, this data is removed from the stack.

What is recursion used for?

Recursion is best used for problems where a large task can be broken down into a repetitive “sub-task”. Because a recursive routine calls itself to perform those sub-tasks, eventually the routine will come across a sub-task that it can handle without calling itself. This is known as a base case — and it is needed to prevent the routine from calling itself over and over again without stopping. So, one can say that the base case stops the recursion.

Base cases and Recursion

In the base case, the routine does not call itself. But, when a routine does have to call itself in order to complete its sub-task, then that is known as the recursive case. So, there are 2 types of cases when using a recursive algorithm: base cases and recursive cases. This is very important to remember when using recursion, and when you are trying to solve a problem you should ask yourself: “What is my base case and what is my recursive case?”.

Recursion can be divided in two parts, basic recursion and tail recursion

Basic Recursion

Basic recursion is when the program wind all calls to the top on the stack, after the this calls and after unwind it example in graphics below.

See how it work in simple algorithm that compute the add from( a0, a1, a2…. an) for all integers n > 0.

sum(5)
5 + sum(4)
5 + (4 + sum(3))
5 + (4 + (3 + sum(2)))
5 + (4 + (3 + (2 + sum(1))))
1
2 + 1; // unwinding start
3 + 3;
4 + 6;
5 + 10;
15

Tail Recursion

Tail recursion is a specific type of recursion. In particular, a recursive function to use tail recursion if the call to itself occurs as the last action of the function.

look how it work with the above algorithm.

sum(5)
5 + sum(4)
5 + (4 + sum(3))
5 + (4 + (3 + sum(2)))
5 + (4 + (3 + (2 + sum(1))))
5 + (4 + (3 + (2 + 1)))
15

Example computing power of a number:

Above is the math definition to pow recursive function. the function accepts two numbers. x and y and calculates x ^ y.

First give our recursive _pow_recursion(x,y) function a meaningful name.
The function must accept two numbers, that is, base and exponent, and calculate their power. So, take two parameters for the base and the exponent, let's say _pow_recursion(float base, int exponent);.
Finally, the function should return base ^ exponent, that is, a value of type float.
The final function declaration for computing power is -
float _pow_recursion(double x, int y);.

• If exponent is 0, then power is 1. This is the base condition of our recursive function.
• If exponent is negative, then power is 1 / (x ^ -y). Which uses recursive call to _pow_recursionfunction for computing the value of (x ^ -1) i.e. 1 / _pow_recursion(base, -expo).
• If exponent is positive, then calculate power normally using x ^ y. Computing x ^ y also makes a recursive call i.e. base * _pow_recursion(base, expo - 1)

now look two way to solve this problem using recursion.

Using Basic Recursion

time complexity O(n)

Using Divide and Conquer.

Time complexity O(logN)