Is recursion used in practice to improve performance of AI systems?

Is there any methods by which artificial intelligence use recursion(s) to solve a certain issue or to keep up working and calculating?

• Can you clarify the phrase 'keep up working and calculating'? Aug 7 '16 at 7:13

1 Answer

To my knowledge, recursion does not play a strong role in the definition of modern AI techniques, although it does feature used in Lovasz's definition of 'Local Search' and Kurzweil is certainly an advocate.

Recursion can be seen as an elegant 'architectural factorization' - building complexity by combining the results of smaller, similar patterns previously encountered. Computationally, recursion can always be converted into iteration so this form of elegance is really mainly of use in helping to make designs more comprehensible.

GOFAI algorithms that were traditionally defined using recursion include depth- and breath- first search and means-ends analysis (used in Newell and Simon's General Problem Solver).

With respect to performance, while many functions can be very economically defined using recursion, the naive version of such definitions can be inefficient.

This page gives an example in which recursive version of the Fibonacci function, which has asymptotic execution time $$n^{1.6}$$, which is reduced to $$n$$ by the use of memoization.

• It's important to note that some languages like Prolog use recursion as one of the main methods of handling parse trees - this is considered powerful when it comes to handling NLP and applications like Watson make use of this property. Aug 11 '16 at 3:21