TraceRecursio 2.1.0

This library provides a decorator that traces the execution of recursive functions, representing their behavior through a graph.

TraceRecursio

TraceRecursio is a Python library that provides a decorator to trace the execution of recursive functions. The library generates a visual representation of the recursion process through a directed graph, allowing you to observe how the function operates step-by-step, tracking the parameters, return values, and the order of function calls.

Features

• Trace decorator: Easily apply the @Trace decorator to any recursive function to start tracing its execution.
• Graphical Representation: The library generates an interactive graph where each node represents a function call and edges show the call relationships.
• Detailed call information: For each recursive call, the parameters, return values, and call order are tracked and displayed.
• HTML output: The graph is exported as an interactive HTML file for easy visualization.

Installation

You can install TraceRecursio via PyPI:

pip install TraceRecursio

Quickstart

Here is a minimal example to demonstrate the library’s functionality:

from TraceRecursio import Trace

# Applying the Trace decorator to a recursive function
@Trace
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

# Call the function
factorial(5)

# Generate and visualize the graph
Trace.get_graph('factorial')

Running this code will generate a factorial.html file that contains the interactive graph of the recursive calls.

Use Cases

Example: Fibonacci Sequence

In this example, we apply @Trace to a recursive function that calculates the nth number in the Fibonacci sequence. The decorator tracks each step of the recursion:

from TraceRecursio import Trace

@Trace
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

fibonacci(5)

# Generate the graph visualization
Trace.get_graph('fibonacci')

Default Graph Representation

By default, the get_graph method generates a standard directed graph that shows the recursion steps:

Hierarchical Graph Representation

You can also visualize the recursion as a hierarchical graph, which organizes the nodes more clearly based on their relationships. To enable this, you need to modify the settings by enabling hierarchical view, setting sortMethod to directed, and adjusting the shakeTowards parameter to roots. This will result in a more tree-like graph, where the root of the recursion (initial function call) is at the top, and subsequent calls branch downward:

The hierarchical graph and other layout configurations can be enabled via the interactive control panel that appears in the graph view. Here’s an image of the control panel where you can find the options for:

• Enabling Hierarchical Layout
• Setting Sort Method to "directed"
• Adjusting Shake Towards to "roots"

How It Works

The @Trace decorator monitors the execution of recursive functions. The key method is get_graph. This method accepts a string as an argument, which should be the name of the decorated function. This method generates and saves the HTML file of the recursion graph in the root directory where the code is executed, displaying:

• Nodes: Represent each function call.
• Edges: Show the relationship between parent and child function calls.
• Detailed information: Each node contains the arguments, return value, and call order for the corresponding function call.

Detailed Explanation of the Graph Output

Using the Fibonacci example, let’s break down the recursive calls and how they are represented in the graph. The recursion process for fibonacci(5) is as follows:

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = fibonacci(1) + fibonacci(0) = 1 + 0 = 1
fibonacci(3) = fibonacci(2) + fibonacci(1) = 1 + 1 = 2
fibonacci(4) = fibonacci(3) + fibonacci(2) = 2 + 1 = 3
fibonacci(5) = fibonacci(4) + fibonacci(3) = 3 + 2

Now, comparing this with the graph generated by TraceRecursio, each node in the graph corresponds to one of these function calls:

• The nodes with args set to (0,) represent the call to fibonacci(0), which immediately returns 0.
• Similarly, the nodes with args set to (1,) represent the call to fibonacci(1), which immediately returns 1.
• The nodes with args set to (2,) represent the call to fibonacci(2). They have two incoming edges from fibonacci(1) and fibonacci(0), indicating that fibonacci(2) is computed by summing the results of these two calls. In fact, their return is set to 2, which is the sum of the return values from the two child nodes.
• This pattern continues for fibonacci(3), fibonacci(4), and fibonacci(5), with each node aggregating results from the two preceding calls, as dictated by the recursive Fibonacci algorithm.

In the graph, you can see exactly how the recursion unfolds, with the edges showing the flow of data between recursive calls. Here's an image highlighting these nodes in the graph:

Each node not only shows the recursive call but also contains details about the arguments passed to the function, the return value, and the order in which the calls were made, making it easy to follow the execution flow step-by-step.

Additional Features

Track class

The Track class includes the instances method, which provides a dictionary with the following structure:

• Key: The name of the decorated function.

• Value: The decorated function itself, which contains the following useful attributes for further exploration:

  • edges: A dictionary where the key is the node ID, and the value is a list of connected nodes.
  • frames_order: A dictionary with the node ID as the key and an ordinal number representing the order in which that node was generated.
  • parameters: A dictionary where the key is the node ID and the value is the list of parameters passed to the function during that call.
  • returns: A dictionary where the key is the node ID and the value is the result returned from that function call.
  • G: The graph generated using NetworkX.

Contributing

We welcome contributions! Please feel free to submit a pull request or open an issue.

License

This project is licensed under the MIT License.