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: