Recursion inside for loop (Python)

Question

I don't have experience to code recursion programs. I am trying to find a recursive solution that gives all different combinations for given two strings using for loop. I would like to find a solution using for loop inside recursion. For a given string ABC,DEF. the output must be AD,AE,AF,BD,BE,BF,CD,CE,CF. Assume combination length = 2. I wrote below code, it is not working. Can any one help? what would be thought process for a recursion inside a for loop?

def mkcb(s1, s2, i, ns):

    if i <= 2:
        print(ns)
    
    for k in range(len(s1)):
        mkcb(s1[1:], s2, i+1, s1[k] + s2[k])
        
mkcb('ABC', 'DEF', 0, '')

There is no recursion in your code. Why dont you study some examples of recursion? — Psytho, Feb 02 '22 at 07:11
Does this answer your question? [Recursively find all combinations of list](https://stackoverflow.com/questions/65181109/recursively-find-all-combinations-of-list) — Dhana D., Feb 02 '22 at 07:16

score 0 · Answer 1 · answered Feb 02 '22 at 07:13

0

There really is no need to recursion here, this is far easier using a simple nested for-loop (pseudo-code):

for each char1 in "ABC":
  for each char2 in "DEF":
    print_on_screen(concatenation(char1, char2))
  next char2
next char1

answered Feb 02 '22 at 07:13

Dominique

16,450
15
56
112

1

Your pseudocode has *more* syntax than actual Python code doing the same thing would have. Get rid of `each`, and the last two lines, and change the output line to `print(char1 + char2)` and you'd have real Python. – Blckknght Feb 02 '22 at 07:14

Blckknght · Answer 2 · 2022-02-02T19:35:31.533

Recursion doesn't really make sense for your simple case with two strings. A pair of nested loops would be much easier.

It would make more sense to use recursion if you were trying to solve a more general problem of making combinations of an arbitrary number of strings. Then the general structure of recursion combined with iteration would make sense.

I'd do it like this, with a loop over the first string, and the recursion working on the remaining strings. A prefix keyword-only argument (defaulting to an empty string) would get passed along to tell the code what characters had already been added, and the whole prefix would be printed when there were no strings left to pick characters from:

def combinations(*strings, prefix=""):
    if not strings:                         # base case, no strings left to pick from
        print(prefix)
        return

    for char in strings[0]:                 # iterate over the first string
        combinations(*strings[1:], prefix=prefix+char) # recurse on the other strings

This would work for your current case combinations("ABC", "DEF"), but would also work for more strings:

>>> combinations("AB", "CD", "EF", "GH")
ACEG
ACEH
ACFG
ACFH
ADEG
ADEH
ADFG
ADFH
BCEG
BCEH
BCFG
BCFH
BDEG
BDEH
BDFG
BDFH

If you didn't want to print the strings directly in the function, but rather return them to the caller, I'd write a recursive generator instead, which wouldn't need the prefix stuff:

def combinations_gen(*strings):
    if not strings:
        yield ""
        return

    for char in strings[0]:
        for rest in combinations_gen(*strings[1:]):
            yield char + rest

You'd use this by iterating over its return value:

for val in combinations_gen("ABC", "DEF"):
    print(val)

Hi your below code is not working. it doesn't display any value. — Ramu, Feb 02 '22 at 09:23
def combinations(*strings, prefix=""): if not strings: # base case, no strings left to pick from print(prefix) return for char in strings[0]: # iterate over the first string combinations(strings[1:], prefix=prefix+char) # recurse on the other strings — Ramu, Feb 02 '22 at 09:24
Oh, you're right, I had a typo in that first code block. You need to do an unpacking in the recursive call: `combinations(*strings[1:], prefix=prefix+char)`. After testing my own code I fixed that error in the generator version but not in the regular version. — Blckknght, Feb 02 '22 at 19:37

Recursion inside for loop (Python)

2 Answers2