Combination of recursion and generator

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.

Recommended Posts

Combination of recursion and generator
Combination of anyenv and direnv
Referencing and changing the upper bound of Python recursion
Problems of liars and honesty
Mechanism of pyenv and virtualenv
Pre-processing and post-processing of pytest
Explanation and implementation of SocialFoceModel
Differentiation of sort and generalization of sort
Coexistence of pyenv and autojump
Use and integration of "Shodan"
Problems of liars and honesty
Occurrence and resolution of tensorflow.python.framework.errors_impl.FailedPreconditionError
Very convenient combination of CLI image viewer Überzug and Ranger
Comparison of Apex and Lamvery
Source installation and installation of Python
Introduction and tips of mlflow.Tracking
Capture GeneratorExit and detect the end of iteration from the generator side
[Translation] scikit-learn 0.18 User Guide 4.1. Pipeline and Feature Union: Combination of estimators
Environment construction of python and opencv
Basic knowledge of Linux and basic commands
Order of arguments of RegularGridInterpolator and interp2d
The story of Python and the story of NaN
Explanation and implementation of PRML Chapter 4
Introduction and Implementation of JoCoR-Loss (CVPR2020)
Benefits and examples of using RabbitMq
Explanation and implementation of ESIM algorithm
Installation of SciPy and matplotlib (Python)
Significance of machine learning and mini-batch learning
Introduction and implementation of activation function
Memorandum of saving and loading model
Misunderstandings and interpretations of Luigi's dependencies
Explanation and implementation of simple perceptron
Calculation of homebrew class and existing class
This and that of python properties
Design of experiments and combinatorial optimization
Installation and easy usage of pytest
Recursion challenge to Tower of Hanoi
Clash of Clans and image analysis (3)
Features of symbolic and hard links
Coexistence of Python2 and 3 with CircleCI (1.0)
[Excel] Addition of character strings (combination)
Summary of Python indexes and slices
Aggregation and visualization of accumulated numbers
Reputation of Python books and reference books
The golden combination of embulk and BigQuery shines even more with Digdag