Searching

Searching over a set (o similar structure) can be done in an iterative way, but it presents several problems:

• first of all, you need to know the depth

Binary search

Efficient for finding in an ordered list.

Exhaustive search

Exploring every possible combination from a set of choices or values.

Using recursion is a good way to do that exploration.

Applications: - producing all Permutations of a set - enumerating all possible names, words, etc. - combinatorics and logic programming - Chess game (evaluate up to some depth or all possible movements in a given moment)

Pseudo-code:

Search(decisions):
   - if there are no more decisions to make: Stop.
   - else, let's handle one decision ourselves, and the rest by recursion
     for each available choice 'C' for this decision:
       - **Choose** 'C'.
       - **Search** the remaining decisions that could follow 'C'.

Often, the search space consists of many decisions, each of which has several available choices. As an example, when enumerating all 5-letters strings, each of the 5 letters is a decision, and each of these 5 decisions have 26 possible choices. So, we choose one letter (this is the decision) and handover recursively the rest of decision (chooses).

As for recursion, a base case (the ideal or easy case) has to be thought, as well as the recursive pattern (the self-familiarity) of the problem.

Exhaustive search as a tree (of calls)

https://youtu.be/HvGkzDT2ffI?t=25m22s