Pattern 22 (Recursion)

FLASH animation of Recursion pattern

Description

The ability of a task to invoke itself during its execution or an ancestor in terms of the overall decomposition structure with which it is associated.

Examples

An instance of the resolve-defect task is initiated for each mechanical problem that is identified in the production plant. During the execution of the resolve-defect task, if a mechanical fault is identified during investigations that is not related to the current defect, another instance of the resolve-defect is started. These subprocess can also initiate further resolve-defect tasks should they be necessary. The parent resolve-defect task cannot complete until all child resolve-defect tasks that it initiated have been satisfactorily completed.

Motivation

For some types of task, simpler and more succinct solutions can be provided through the use of recursion rather than iteration. In order to harness recurive forms of problem solving within the context of a process, a means of describing a task execution in terms of itself (i.e. the ability for a task to invoke another instance of itself whilst executing) is required.

Overview

Figure 33 illustrates the format of the recursion pattern in Petri net terms. Task A can be decomposed into the process model with input i1 and output o1. It is important to note that this process also contains the task A hence the task is described in terms of itself.

In order to implement the pattern, a process model requires the ability to denote the synchronous invocation of a task or sub-process within the same model.

Figure 33: Recursion pattern

In order to ensure that the use of recursion does not lead to infinite self-referencing decomposition, Figure 33 contains one path (illustrated by task sequence BDC) which is not self-referencing and will terminate normally. This corresponds to the terminating condition in mathematical descriptions of recursion and ensures that, where resursion is used in a process, the overall process will eventually complete normally when executed.

Context

There are no specific context conditions associated with this pattern.

Implementation

In order to implement recursion within the context of a process, some means of invoking a distinct instance of a task is required from within a given task implementation. Staffware, WebSphere MQ, COSA, iPlanet and SAP Workflow all provide the ability for a task to invoke an instance of itself whilst executing.

Figure 34: Recursion implementation

The actual mechanics of implementing recursion for a process such as that depicted in Figure 33 are shown in Figure 34. The execution of the recursive task A is denoted by the transitions startA and endA. When an instance of task A is initiated in a case c, any further execution of the case is suspended and the thread of control is passed to the decomposition that describes the recursive task (in this case, task B is enabled). A new case-id is created for the thread of control that is passed to the decomposition and a mapping function (in this example denoted by child()) is used to capture the relationship between the parent case-id and the decomposition case-id, thus ensuring that once the child case has completed, the parent case can continue from the point at which it originally suspended execution and invoked the child instance of itself.

Issues

None identified.

Solutions

N/A.

Evaluation Criteria

An offering achieves full support if it provides a construct that satisfies the description for the pattern.

Product Evaluation

To achieve a + rating (direct support) or a +/- rating (partial support) the product should satisfy the corresponding evaluation criterion of the pattern. Otherwise a - rating (no support) is assigned.