How to properly rewrite a recursive algorithm to form chains of text replacement actions in Python?

Question

Python

Good evening!

The system of text replacements is given:
1. |>∗< to >∗ 2. d| on |md
3. dm on md
4. d> on >
5. <>∗< on 6. e| to e
7. em to |e
8. e> to >

Also given is a string (example: <|>*<||>) for which these substitutions can be applied.
The task is to build all possible chains of actions presented in the text replacement system on a given string. As a result, you should get a list of all sequences of actions on the string, for example:
1256247678
1256274678
1256276478
1256276748
1256724678
1256726478
1256726748
1522467678
All sequences must be complete, such that after performing these actions it was impossible to make any replacements on the string.

I decided to write a python program to implement this task, and this is what happened:

s = '<|>*<||>'

arr_replacements = [
    ['|>*<', '>*<d'],
    ['d|', '|md'],
    ['dm', 'md'],
    ['d>', '>'],
    ['<>*<', '<e'],
    ['e|', 'e'],
    ['em', '|e'],
    ['e>', '>']
]

def recursive_replace(s, path):
    k = 0
    for i in range(len(arr_replacements)):
        z = arr_replacements[i]
        if (s != s.replace(z[0], z[1])):
            path += str(i + 1)
            s = s.replace(z[0], z[1])
            return recursive_replace(s, path)
        else:
            k += 1
    if k == len(arr_replacements):
        return path
        
print(recursive_replace(s, str()))

True, this program now goes through only one branch and collects only one sequence. So far I have no idea how to remake it so that it goes through all the possible options.