Recursion in Hardware: Applicability and Implementation Strategies

It is widely accepted that, for certain classes of algorithms, recursion provides clean, concise, elegant, and robust designs that are easy to conceive, understand, and modify with minimal design costs. Its advantages and disadvantages when compared to iteration are well known in software applications. Strategies for implementing recursion in hardware have started to be proposed only recently and they may lead to different results, not only when compared to recursion in software, but also with each other. This paper illustrates the applicability of recursive algorithms in solving computationally intensive problems, namely with the implementation of backtracking search algorithms. Then, a careful analysis of the most relevant strategies for implementing recursion in hardware is carried out, highlighting and comparing the advantages and limitations which can be found amongst them.