Recursion is when the "solution to a problem depends on solutions to smaller instances of the same problem" (wiki).
There are different types of recursion:
1. Single Recursion - only contains a single self-reference
ex. list traversal (linear search), computing the factorial function
2. Multiple Recursion - contains multiple self-references
ex. tree traversal (depth-first search), computing the Fibonacci sequence
3. Indirect Recursion - when a method invokes another method, eventually resulting in the original method being invoked again
4. Anonymous recursion - does not explicitly call a function by name
Recursion is important in artificial intelligence because it involves searching through nested structures. Anything involving tree data structures will require some recursion.
wiki source: http://en.wikipedia.org/wiki/Recursion_(computer_science)