Combination of recursion and generator

• This post is a test of Qiita.

In some cases, recursion can be expressed with a simple structure by combining recursion and a generator.

Regular expression recursion

Difficult to deal with recursive parentheses in regular expressions. Regular expressions have their own syntax in PHP and Ruby, but not in Python. Parentheses can be handled fairly easily by using a recursive function.

import re
prog = re.compile(r"\((.+)\)")

def rec_search(s):
    "Recursively get parentheses and return them as a list"
    match = prog.search(s)
    r = []
    if match:
        r.append(match)
        for i in rec_search(match.group(1)):
            r.append(i)
    return r

I make a list and return it to the caller. It looks a little dirty.

Combine with a generator

import re
prog = re.compile(r"\((.+)\)")

def recsearch(s):
    "Recursively get parentheses and iterate"
    match = prog.search(s)
    if match:
        yield match
        for i in rec_search(match.group(1)):
            yield i

It's pretty simple. If you yield the value, you can discard the value, which is easy. Note that rec_search is a generator, so yield to return it to the caller. Otherwise, a function call that does nothing will occur and end.

Execution result

>>> for i in rec_search("(1 + (1 + 2))"):
	print(i)

<_sre.SRE_Match object; span=(0, 13), match='(1 + (1 + 2))'>
<_sre.SRE_Match object; span=(4, 11), match='(1 + 2)'>

Make it even simpler with yield from

Introduced in python3.3. Execute the generator function specified by yield from and wait at the caller until all the results are returned. A yield from trial version of the above function.

import re
prog = re.compile(r"\((.+)\)")

def rec_search(s):
    "Recursively get parentheses and iterate"
    match = prog.search(s)
    if match:
        yield match
        yield from rec_search(match.group(1))

It's even shorter and simpler.

Get the file name recursively

import os

def iter(dirctory):
    "Iterate all files under directory"
    d = os.listdir(dirctory)
    if d:
        for f in (os.path.join(dirctory, f) for f in d):
            if os.path.isfile(f):
                yield f
            elif os.path.isdir(f):
                yield from iter(f):

ʻOs.listdir` An example of recursive acquisition using only the function. It judges whether it is a file or a folder, and if it is a folder, it calls recursively again.

end

Recently I remembered recursion and tried various things. It's better to use parsing for regular expressions, and you can get the file name with pathlib.Path (). Glob, so it's not practical.