Recursion question example code

Python
1

I don’t understand this code after aaa is printed


# Python 3 program to print all

# possible strings of length k

    

# The method that prints all

# possible strings of length k.

# It is mainly a wrapper over

# recursive function printAllKLengthRec()

def printAllKLength(set, string_length):

    set_length = len(set)

     

    print("the set length is", set_length)

    printAllKLengthRec(set, "", set_length, string_length)

# The main recursive method

# to print all possible

# strings of length k

def printAllKLengthRec(set, prefix, set_length, string_length):

    

    # Base case: k is 0,

    # print prefix

    if (string_length == 0) :

        print(prefix)

        return

    # One by one add all characters

    # from set and recursively

    # call for k equals to k-1

    for i in range(set_length):

        print(f"for iteration {i} of {set_length-1} with string length:{string_length}") #extra print

        

        # Next character of input added

        newPrefix = prefix + set[i]

        print("the newprefix is ", newPrefix)

        

        # k is decreased, because

        # we have added a new character

        printAllKLengthRec(set, newPrefix, set_length, string_length - 1)

# Driver Code

if __name__ == "__main__":

    

    print("First Test")

    set1 = ['a', 'b']

    string_length = 3

    printAllKLength(set1, string_length)

        

    # print("\nSecond Test")

    # set2 = ['a', 'b', 'c', 'd']

    # k = 1

    # printAllKLength(set2, k)

# This code is contributed

# by ChitraNayal
2

Calling it “set” is really bad practice because that’s a Python keyword…

Anyway, the recursion calls itself in a for-loop going through the set of characters, while reducing the “string_lengths” by one, which is actually the remaining length to be filled (hence it’s reduced by one, for every recursion-level, because there is one letter less to fill).
Once the string_length reaches 0, no further recursion will be called. Which means on the lowest level the for-loop will finish it’s first loop and go to the next entry in the set.

3

could you give a detailed explanation how is the string length always restricted to 3 and there is addition going on when getting the new prefix and no removing of letter then how do they get ab, and from iteration 1 how does it goback to iteration 0

thanks

4

The code already goes very in-depth and also provides a ton of printing statements which go through the process quite detailed.

Maybe run the code and read them slowly.

The string-length is restricted to 3, because it starts at 3 and is reduced once per recursive call, but the recursion stops at 0 → so there are only 3 different states it can have.

5

The call stack is what l don’t understand, which the print statements don’t show, it doesn’t show the “unseen”/“magic” that happens

Thanks

6

The call-stack means when the recursions keep calling themself and because the last one to be called is the first one to finish, it’s a stack (opposite is a queue: first called is first finished).

In order to “see” when functions are called and finished, you can just edit a print-statement at the beginning and end of the function call.
Like in the following code (I deleted some comments, you can just copy the print-statements into the code):

def printAllKLengthRec(set, prefix, set_length, string_length):
    print(f"printAllKLengthRec({set}, {prefix}, {set_length}, {string_length}) is called")


    if (string_length == 0) :
        print(prefix)
        return
    for i in range(set_length):

        print(f"for iteration {i} of {set_length-1} with string length:{string_length}") #extra print

        newPrefix = prefix + set[i]

        print("the newprefix is ", newPrefix)

        printAllKLengthRec(set, newPrefix, set_length, string_length - 1)
    print(f"printAllKLengthRec({set}, {prefix}, {set_length}, {string_length}) is finished")
7

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.