Finding Fibonacci numbers using regex

Question

I found the following code example on this blog post :

final String FIBONACCI = 
   "(?x) .? | ( \\2?+ (\\1|^.) )* ..";

for (int n = 0; n < 10000; n++) {
   String s = new String(new char[n]);
   if (s.matches(FIBONACCI)) {
      System.out.printf("%s ", n);
   }
}

output: 0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 ...

How does (?x) .? | ( \\2?+ (\\1|^.) )* .. match Fibonacci numbers?

It would be great if you post the internet source of this code. — Luiggi Mendoza, Sep 04 '13 at 21:12
The example come from here: http://www.polygenelubricants.com/2010/09/finding-fibonacci-numbers-using-regex.html — dcaswell, Sep 04 '13 at 21:23
@progenhard It _matches_ fibonacci numbers, it does not _generate_ the fibonacci sequence. — tredontho, Sep 04 '13 at 21:37
thanks Danny but I want more detail.This explanation is not enough for me I didn't understand:( — Melih Altıntaş, Sep 04 '13 at 21:38
It looks like the answer was written by the same person who wrote the blog where you found this code. Perhaps you could comment on the answer asking for clarification (though, it looks like he's been inactive for a few months). — DannyMo, Sep 04 '13 at 21:51
What's unclear about it? Very clever but it's pretty straight forward to read and understand. — Qtax, Sep 04 '13 at 23:14
I found it very difficult to understand, but I don't usually use extended regular expressions. — jmh, Sep 04 '13 at 23:49

score 16 · Accepted Answer · edited May 23 '17 at 10:30

(?x) .? | ( \\2?+ (\\1|^.) )* ..

There are a lot of things going on here which may confuse. I will go through each of these things in order to explain why the algorithm works.

The match is being done on a string with the length of the regex, not the actual number. The only real data in the string is its length.
\\The double backslashes are just because in Java string literals backslashes have to be backslashed so that it is clear you aren't escaping something else. I won't show them in any future code in this answer.
(?x): This enables extended regex mode. In this mode whitespace that is not backslashed or within a character class is ignored, allowing the regular expression to be broken into more readable parts with embedded comments. [sarand.com].
.?: This will match 0 or 1 character strings. This match is only used for the f(0), f(1) and f(2) cases, otherwise it will be discarded.
|: This means that if the first attempt to match 1 or two characters didn't work, then try to match everything on the right of it.
(: This opens the first group (referenced by \1 later on).
(\2?+ The + makes the ? a possessive quantifier. In this case the result is that the ? means use the \2 backreference if it is defined and the + means don't go back and try not using it if the regex doesn't work with it.
(\1|^.): This will match either everything that has been matched so far or a single character. This of course means that the first "everything matched so far" is a single character. Since this is the second regex, it is also the new \2
)*: This will repeat the algorithm. Every time it repeats it will define new values for \1 and \2. These values will be equal to F(n-1) and F(n-2) for the current iteration which will be F(n). Each iteration will be added to the previous, meaning you have a sum of F(n) 0 to n. Try running the algorithm through your head for some smaller numbers to get the idea.
..: One dot is required to match the f(1) that is not included in the sum, the second is because the Second Identity of Fibonacci Numbers states that the sum of a sequence of fibonacci numbers is a fibonnaci number minus one. (1)
Walking through the replacements you can see how this will continue to add Fibonacci numbers until filling the string. The first iteration matches the ^., so 1. The second iteration matches the previous partial match with the \2 as well as the entire previous match with the \1. That makes two for the second iteration. Third iteration takes that second part of the match from the second iteration (1) as well as the entire second iteration (2). This makes three for the third iteration. Add the iterations together and you have a sum of fib numbers.

Please see Why does Java regex engine throw StringIndexOutOfBoundsException on a + repetition? for more information on why this recurrence actually works.

score 0 · Answer 2 · answered May 15 '20 at 08:19

I know it's already explained in a lot of detail in the other answer (including a better explanation of the regex used in general), but I recently came across this regex without explanation, so I've added some comments myself for it. I figured I'd also share it here for others to see.

The first thing to note is that the regex uses unary for the integers. So String s = new String(new char[n]); in the Java code will convert an integer n into a String of that many ('\0') characters. Which character this string contains isn't important, it's the length that matters for unary. (An alternative in Java 11+ could for example have been String s = "x".repeat(n);, and it would still work as intended.)

As for the regex itself:

"(?x) .? | ( \\2?+ (\\1|^.) )* .." # Since this is a Java-String, where the `\` are escaped
                                   # as `\\` and `String#matches` also implicitly adds a 
                                   # leading/trailing `^...$` to regex-match the entire
^(?x) .? | ( \2?+  (\1 |^.) )* ..$ # String, the actual regex will be this:
                                   # The `(?x)` is used to enable comments and whitespaces,
                                   # so let's ignore those for now:
^.?|(\2?+(\1|^.))*..$
    (           )*                 # First capture group repeated 0 or more times.
                                   # On each iteration it matches one Fibonacci number.
            |^.                    # In the first iteration, we simply match 1 as base case.
                                   # Afterwards, the ^ can no longer match, so the
                                   # alternative is used.
     \2?+                          # If possible, match group 2. This ends up being the
                                   # Fibonacci number before the last. The reason we need
                                   # to make his optional is that this group isn't defined
                                   # yet in the second iteration. The reason we have the `+`
                                   # is to prevent backtracking: if group 2 exists, we
                                   # *have* to include it in the match, otherwise we would
                                   # allow smaller increments.  
         (\1|  )                   # Finally, match the previous Fibonacci number and store
                                   # it in group 2 so that it becomes the second-to-last
                                   # Fibonacci number in the next iteration.

                                   # This in total ends up adding Fibonacci numbers starting
                                   # at 1 (i.e. 1,2,3,5,8,... will add up to 3,6,11,19,...
                  ..               # They are all two less than the Fibonacci numbers, so
                                   # we add 2 at the end.

                                   # Now it's only missing the 0 and 1 of the Fibonacci
 .?|                               # numbers, so we'll account for those separately

Finding Fibonacci numbers using regex

2 Answers2