Publications

Abstract

Recursive algorithms belong to the class of algorithms with high resource consumption, since with a large number of self-calls of recursive functions, the stack area is quickly filled [1]. In addition, organizing the storage and closing of the next layer of the recursive stack are additional operations that require time. The complexity of recursive algorithms is also affected by the number of parameters passed by the function [9]. Consider one of the methods for analyzing the complexity of a recursive algorithm, which is built on the basis of counting the vertices of a recursive tree [9]. To estimate the complexity of recursive algorithms [2], a complete recursion tree is constructed like Figure 1. It is a graph, the vertices of which are the sets of actual parameters for all calls to the function, starting from the first call to it, and the edges are the pairs of such sets corresponding to mutual calls. In this case, the nodes of the recursion tree correspond to the actual calls of the recursive functions. It should be noted that the same sets of parameters can correspond to different nodes of the tree. The root of the complete recursive call tree is the top of the complete recursion tree corresponding to the initial call to the function.