Searching and backtracking

Searching for solutions to problems, especially when there is no direct algorithm and you must resort to trial and error, is particularly appropriate for recursion. Many of these algorithms fall into a scheme such as the following:

  • Out of many choices available, pick one.
  • If no options are available, you've failed.
  • If you could pick one, apply the same algorithm, but find a solution to the rest.
  • If you succeed, you are done.
  • Otherwise, try another choice.

With small variations, you can also apply similar logic to find a good—or possibly, optimum—solution to a given problem. Each time you find a possible solution, you match it with previous ones that you might have found and decide which to keep. This may go on ...

Get Mastering JavaScript Functional Programming - Second Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.