Greedy algorithms and backtracking

What do we mean by greedy algorithms? What is backtracking? By being greedy, the algorithm matches the longest possible part. Backtracking algorithms, upon failure, keep exploring other possibilities. Such algorithms begin afresh from where they had originally started, hence they backtrack (go back to the starting point).

We all follow the process of backtracking in real life. For example, to get to an address, we go to a well-known landmark, then try the first lane, for example. If there is no success, we backtrack to the landmark again and try another lane (we may ask a passerby for help). We keep doing this until we get to the address or give up the search altogether.

A well-known example of greedy and backtracking algorithms from the programming world is how a regex match happens. We use a simple regex using greedy qualifiers such as * and +:

Here is a quick Scala REPL session to see the greediness in action:

scala> val regex = "^(.*)(.+)$".r 
regex...