Recursion

Recursion. n. masc. see recursion.

Folklore

Petro is developing a new development environment for the language Ж±. He is currently working on a module to detect potential infinite recursion.

Ж± is a procedural language in which all variables are binary, meaning each variable can have either the value "$0$" or "$1$". Each procedure in Ж± can take several arguments. The language supports the following operators:

• Increment operator "x++" – if $x$ is $0$, it becomes $1$;

• Decrement operator "x–" – if $x$ is $1$, it becomes $0$;

• Conditional operator "if (x) S1 else S2" where $S1$ and $S2$ are arbitrary operators; execute $S1$ if $x$ is $1$, or $S2$ if $x$ is $0$;

• Procedure call "f (x, y)";

• Compound operator "{S1 S2 ...}" where $S1$, $S2$, etc., are arbitrary operators; execute $S1$, $S2$, etc., in this order.

A procedure is defined as: "<procedure name> (<argument list>) S" where S is an arbitrary operator.

All arguments are passed by value (that is, changes within the procedure do not modify the values of the corresponding variables in the calling procedure).

For example, the program in the first example contains a procedure "inc" which takes a three-bit value via three arguments x2, x1, and x0, and eventually calls the procedure "done" with three arguments representing the value incremented by one.

Given the program, determine whether it is possible to call some procedure with arguments such that the result is infinite recursion.