Design of a recursive algorithm for DFA implementation: computational complexity analysis

Computational complexity, in its practical application, quantifies the time and memory space required for an algorithm’s execution, thereby allowing the assessment of its efficiency and limitations with respect to input size. In this work, the design of a recursive algorithm for implementing a deterministic finite automaton (DFA) to recognise regular languages is presented. The divide-and-conquer technique was employed to select appropriate data structures and to define a recursive function for resolving the transition functions between states. The recursive algorithm was implemented in the C++ language and exhibits linear temporal and spatial computational complexity, which is intended to support different configurations for the evaluation of multiple input strings. The proposed algorithm is consistent with the theoretical definitions, and the computational complexity analysis provides support for its classification based on the input parameters. Smart citations: https://scite.ai/reports/10.61467/2007.1558.2026.v17i1.1172Dimensions.Open Alex.