recursion - 1

NESTED FOR LOOP AS RECURSION

The problem is to change a nested loops of certain size (3 or 4 nested) to n size thro' recursion. Below is a typical nested for loops

    for(m1=0;m1<4;m1++)
    {
        for(m2=0;m2<4;m2++)
        {
            for(m3=0;m3<4;m3++)
            {
                for(m4=0;m4<4;m4++)
                {
                     printf("%d %d %d %d\n",m1,m2,m3,m4);
                }
            }
        }
    }

The result from the above nested loop will look like

0000

0001

0002

0003

0010

0011

0012

0013

.

.

.

3330

3331

3332

3333


In the above code there are 4 loops are nested, if we want a result of say 5 nested loop then we have to modify the code to add 5 loop. Lets say for 10 nested for loops, once again we have to modify the source code to add 10 loops which will be very difficult to implement and keep track of.

The recursive solution below can handle any number of nested for loop by simple recursion. This solution is short but the background behind recursion is bit more complicated, not memory effective & not very fast. This stackoverflow post goes bit more into details of recursion

https://stackoverflow.com/questions/2651112/is-recursion-ever-faster-than-looping


My algorithm utilizes two recursive function n_nested_for_loop1 and nested_incrementer. The steps are

1. Initiate the limite value (which is the number of nested loop) and set the initial values of i[limite]

2. Call the recursion function n_nested_for_loop1

3. Check whether the end is reached (in my opinion this step is non-intuitive and can be improved, bcoz for every time the function n_nested_for_loop1 is called this routine of checking whether the i[m] reached the end.

4. Increment the i[m] at the right level by calling nested_incrementer

5. The nested_incrementer is itself a recursive function increments the right level i[loop] 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void n_nested_for_loop1(int i[],int *n,int limit0);
void nested_incrementer(int *i,int level0,int *limit_addr);
bool check_unique(int *i,int *limit0);

int main()
{
    int limite = 3; // change the limite values to n for number of nested for loop
    int i[limite];
    i[0]=0;
    i[1]=0;
    i[2]=0;
//    i[3]=0;
//    i[4]=0;
//    i[5]=0;
//    i[6]=0;

    int n = 1;
    n_nested_for_loop1(i,&n,limite);// Recursion starts here

    return 0;
}

void n_nested_for_loop1(int i[],int *n,int limit0)
{
    // Print the numbers
    int m;
    for(m=limit0;m>0;m--)
    {
         printf("%d",i[m-1]);
    }
    printf("\n");


    bool is_end = true;
    // Check for the end (ie., all the values are reached the end
    for(m=0;m<limit0;m++)
    {
        if(i[m]<(limit0-1))
        {
            is_end = false;
            break;
        }
    }

    if(is_end!=true)
    {
        nested_incrementer(i,0,&limit0);
        n_nested_for_loop1(i,n, limit0);
    }
}

void nested_incrementer(int *i,int level0,int *limit_addr)
{
    if(level0<(*(limit_addr))) // track the level and check whether it has reached the end
    {
        if(*(i+level0)==(*(limit_addr))-1) // check whether the value reached the end
        {
            if(level0!=(*(limit_addr))-1) // Check also whether the level is not at the end (if it is then no need to bring it back to zero)
            {
                *(i+level0)=0; // bring the value to zero
                level0++; // increment the level
                nested_incrementer(i,level0,limit_addr); // recursion here now the next level will be incremented
            }
        }
        else
        {
            (*(i+level0)) = (*(i+level0))+1; // increment the number bcoz it didn't reaches the maximum
        }
    }
}