Is it possible to replace occurrences of a character sequence recursively without iterating over the same sequence again?

By performing a sed as in the following scenarios I can get the mentioned output.

$ echo XX | sed -e 's/XX/XoX/g'
$ echo XXX | sed -e 's/XX/XoX/g'
$ echo XXXX | sed -e 's/XX/XoX/g'

However, I'm expecting the output to follow the following behavior.



Expected output:


Is it possible to achieve the expected behavior with sed alone?

4 Answers 4


You can do:

> echo XXXX | sed -e ':loop' -e 's/XX/XoX/g' -e 't loop'


  • -e ':loop' : Create a "loop" label
  • -e 't loop' : Jump to the "loop" label if previous substitution was successful

In this particular case look-ahead or look-behind would be useful. I think GNU sed doesn't support these. With perl:

perl -ne 's/X(?=X)/Xo/g; print;'

You could also use lookbehind and lookahead like:



(?<=X) is a positive lookbehind, a zero-length assertion that make sure we have an X before the current position
(?=X) is a positive lookahead, a zero-length assertion that make sure we have an X after the current position

Using in a perl one-liner:

perl -pe 's/(?<=X)(?=X)/o/g' inputfile


-p causes Perl to assume a loop around the program with an implicit print of the current line


The looping answer is the general way to do what you are asking.

However in the case of your data, assuming you are using GNU you can simply do:

sed 's/\B/o/g'

The \b and \B options are regex extensions:

  • \b matches word boundaries, i.e. the transition from a "word" character to "non-word" character, or vice-versa
  • \B matches the opposite of \b. i.e. the gaps "inside" words. This allows us to insert characters inside of a word but not outside, as required.

Try it online.

This assumes that the input characters are in fact all "word" characters.

Alternatively if you don't have GNU sed, or if the input characters are not all "word" characters, you can still achieve your goal without looping:

sed 's/./&o/g;s/o$//'

This simply places an o after every character and then removes the final o from the string.

Try it online.

  • 1
    This assumes that input strings consist of some number of X and nothing else. Both solutions fail if there are other characters present...
    – AnoE
    Oct 16, 2018 at 10:50
  • @AnoE In the second sample, that is fixed with a simple replacement of X by .. Please see edit. Oct 16, 2018 at 19:09
  • Not equivalent to the case the OP gave. He gave the exact REs he needs (change occurrences of XX in a string). Your versions only give the same result as his for the exact same input strings he gave; not for generic input strings.
    – AnoE
    Oct 16, 2018 at 20:18

I checked if there is any sort of a flag to make this happen.
Even if that behavior was there it is going to be highly resource consuming.

However, in this particular use case, it is possible to have the expression just twice and achieve the required functionality. i.e. with 2 repeating sed expressions.

echo XX | sed -e 's/XX/XoX/g' -e 's/XX/XoX/g'     # outputs XoX
echo XXX | sed -e 's/XX/XoX/g' -e 's/XX/XoX/g'    # outputs XoXoX
echo XXXX | sed -e 's/XX/XoX/g' -e 's/XX/XoX/g'   # outputs XoXoXoX

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.