Recursion Part Two

As just said in the previous blog, here we will address how recursion can affect memory and we will introduce the type of recursion called tail recursion.

Before we can address memory, we need to talk about another type of recursion that we can call basic and is called indirect recursion.

Indirect recursion: F() invokes the function G() which in turn invokes the function H() and so on until the function F() is invoked again.

For example: The following program displays the alphabet using mutual or indirect recursion.

#include <stdio.h>

void FunctionA(char Character);
void FunctionB(char Character);

int main(void)
{
        FunctionA('Z');

        return (0);
}

void FunctionA(char Character)
{
        if (Character > 'A')
              
               FunctionB(Character);

        printf("%c ", Character);
}    

void FunctionB(char Character)
{
                 
        FunctionA(--Character);   # This equal a Character - 1
}

Click here to see it graphically

Recursion vs iteration.

Both iteration and recursion are based on a control structure.

• Iteration uses a repeating structure.
• Recursion uses a selection structure, iteration and recursion involve both iteration.
• Both iteration and recursion apply a completion test (break condition).
• the iteration ends when the loop condition is not met.
• recursion ends when break condition is reached.

Memory. (this explanation of memory is more focused on language C)

When a function is called in a C program, a block of storage is allocate on the stack. To keep track of information associated with the call. Each call is referred to as an activation the block of storage placed on the stack is called an activation records or alternatively a stack frame.

An activation record consist of five regions.

1. Incoming parameters: Are the parameters passed it's the activation.
2. Space for a return value.
3. Temporary storage used in evaluating expressions.
4. Saved state information for when the activation terminates.
5. Outgoing parameters: Are the parameters passed to function called within the activation.

Note: The outgoing parameters of one activation record become the incoming parameters of the next one placed on the stack. The activation record for a function call remains on the stack until the call terminates.

Image taken from the book: Mastering Algorithms with C

• Code area: Contains the machine instructions that are executing as the program run.
• Static data area: Contains data that persists throughout the life of the program such as global variables and static local variable.
• heap: dynamically allocate storage, such as memory allocated by malloc, memset etc.
• stack: Contain information about function calls.

Tail recursive.

A recursive call is tail recursive when it is the last statement that will be executed within the body of a function and its return value is not a part of an expression. Tail-recursive functions are characterized as having nothing to do during the unwinding phase. This characteristic is important because most modern compilers automatically generate code to take advantage of it.

When a compiler detects a call that is tail recursive, it overwrites the current activation record instead of pushing a new one onto the stack. The compiler can dothis because the recursive call is the last statement to be executed in the current activation; thus, there is nothing left to do in the activation when the call returns. Consequently, there is no reason to keep the current activation around.

As a challenge, you can try to do the exercise of creating a program that will find you the factorial of a number with tail recursion, instead I will do an exercise that tells me the number of nodes in a double linked list structure.

#Recall that size_t is equal to unsigned int.
#Node is tha data structure.
#Element_List->next Pointer to next node of the data structure.


size_t Counter_Number_Of_Nodes(Node *Element_List,size_t Counter)
{
              
      if (!Element_List)
  
           return (Counter);
      else

           return ( Counter_Number_Of_Nodes(Element_List->next, ++Counter))

}

We have applied tail recursion, we can conclude this for several details to take into account. (click here to see it graphically).

Note: The code that will redirect you does not use the same function that appears in the previous image, but uses tail recursion.Also, the function of inserting a node with a specific data, and that of counting the nodes use tail recursion, this is to give the reader several ways of how to think while studying and observing said algorithm

• The last sentence of the function is the call to itself, a mandatory requirement to be able to be tail recursed
• No value depends on subsequent activation records: that is, if the count nodes function is called a second time, the original function, which is the first time it was called, does not depend on any value returned by the second, therefore the compiler detects this feature of the function and in instead of putting another activation record, update it.

The previous exercise of counting nodes, could have been done in a recursive (normal) way if you allow me to call it like that, as follows.

size_t Counter_Number_Of_Nodes(dlistint_t *Element_List)
{
      size_t Counter = 1;
      
      if (!Element_List)
 
           return (0);
      else

           return (Counter + Counter_Number_Of_Nodes(Element_List->next));
}

As can be seen in the algorithm, there are large differences in recursion with and without tail.

• The first difference that can be highlighted is the following: if the function is called again a second time, where the first is the original call (the first time the function was invoked), the original function depends on what the second returns call. Therefore the compiler realizes this and cannot update the record, but it has to create a new one each time it is called and that we can relate to as a deficiency in the code.

You can make a function like we did in the previous blog so you can see that they are even different, in a very subtle way.

Tail recursive


                     { Counter                if Element == NULL (!Element)
 F(Element, Counter) {
                     { F(Element->next, ++Counter)   if Element != NULL 

Nomal recursive


            {  0                        if Element == NULL (!Element)
 F(Element) { 
            {  Counter + F(Element)     if Element != NULL (Element)

 with Counter = 1.
   

Another way to see these two differences can be found in these two images.

Returning to the exercise of calculating the factorial and assuming that they made the effort to make the version with recursion with tail, this is what would happen in the stack

Recursion (normal).

Tail Recursion.

In the third part of this blog series I will show more interesting exercises that have to do with recursion 💛