Thursday, August 20, 2020

Global variables in Python

 https://www.programiz.com/python-programming/global-keyword

Recursive problems: Example solutions

Problem 1:

'n' number of people are standing in a queue. People standing on even positions are selected. Of the selected people a queue is formed and again out of these only people on even position are selected. This continues until we are left with one person. Find out the position of that person in the original queue.

Solution:

#Python code

#declare a Global variable to store the last base case value of the recursion in it.

h = []

# The recursive function definition

def rec(l):

    global h

    m = []

    #see the list after each recursive call

    print(l)

    #see the size of the new list after each recursive call

    print(len(l))

    

    #base case

    if len(l) == 1:

        h = l

         

        

    if len(l)>1:

        #Getting the even indexed elements of the list

        for i in range(0,len(l)):

            if (i+1) %2 == 0:

                m = m + [l [i]]

# The above three lines can be replaced by following single line

# m = l[1::2] , this puts all the even indexed elements of list l in m. This also significantly improve #performance. Similarly, we can get odd indexed element with m = l[::2]

        rec(m)

    

    return h

# end of the recursive function

    

n=19

k = list(range(1,n+1))

#Call the recursive function

a = rec(k)

#Convert the only element in the list returned by the recursive function into a string

s = str(a[0])

print("Answer is " + s)


-------------------------------------------------------------------------

Output:



Problem 2

Print a sequence of numbers starting with a positive number N, recursively, such that  A[i+1] = A[i] - 5, as long as  A[i]>0. Once A[i] becomes negative, then  A[i+1]=A[i] + 5,  repeat it until A[i]=N.

Solution:

#Python code

def rec(n):


    print(n,end=" " )


    if n>0:

        n = n - 5

        rec(n)

        n = n + 5

        print(n,end=" ")


# end of recursive function definition

  

n = int(input("Enter the value of n :"))

rec(n)

--------------------------------------------------------------------------
Sample output:


Saturday, August 1, 2020

Program Execution (control flow) in a double recursive call


If a function calls itself twice recursively, its tracing tree (program execution/control flow) will be a binary tree




//Understanding double recursion part 1
#include<stdio.h>
//Global variable
int level = 0;
/*
split a list in two equal halves recursively,
and print the level of the binary tree for each node(function call) value pair.

This is the same function used in the DIVIDE & CONQUER technique (splitting
a list from mid recursive ) of  Merge Sort.
*/
void split(int low, int high)
{
    level++; //increment the level each step downwards journey of program execution
    int mid;
    //printf("low = %d High = %d Level = %d\n",low,high,level);
    printf("%d %d Level = %d\n",low,high,level);
    if(low<high)
    {
        mid = (low + high)/2;
        split(low,mid);               //split the left half recursively
        split(mid + 1,high);       //split the right half recursively
    }
    level--; //decrement level as retrace each step upwards the tree, of program execution.
}
int main(void)
{
    printf("For input 1 and 8\n"); // A list of 8 elements, index starting from 1
    split(1,8);
    printf("For input 1 and 16\n"); // A list of 16 elements, index starting from 1
    split(1,16);
    return 0;
}

Output:




/*
Understanding double recursion part 2
Making both the recursive calls in the
SAME line (return statement) also produces
the same result.
The only difference now is that you need to pass
the level as the third argument to the function.
*/
#include<stdio.h>
//Global variable
int level = 0;
/*
split a list in two equal halves recursively,
and print the level of the binary tree for each node(function call) value pair.
*/
int split(int low, int high, int height)
{
    height++; //increment the level each step down
    int mid;
    printf("%d %d Level = %d\n",low,high,height);
    //base condition
    if(low == high)
    {
        return 1;
    }
    if(low<high)
    {
        mid = (low + high)/2;
        return split(low,mid,height) + split(mid + 1,high,height);// The recursive calls in the SAME line
    }
    height--; //decrement level as retrace each step upward
}
int main(void)
{
    printf("For input 1 and 8\n");
    printf("%d \n",split(1,8,level));
    printf("For input 1 and 16\n");
    printf("%d \n",split(1,16,level));
    return 0;
}

Ouput:


Sacred Thought

28 April 2024 Today I am going to explain verse 31 - 38 chapter two for you all. There is no opportunity better than a righteous war (सत्य औ...