# XTRAN Example — Recursive vs. Iterative Factorial Computation

A **recursive** algorithm is one that **invokes itself**
(recurses). A common example is the **factorial function**, in which
the factorial of a number ** n** (expressed mathematically
as

**) is defined as**

*n!***1**if

**is 1, else**

*n***. (The special case for the value 1 is called the recursion's**

*n*times the factorial of*n*- 1**terminating condition**; without such a condition, a recursive algorithm will recurse until it runs out of memory and crashes.)

A recursive algorithm in which the **self-invocation** is the **last
action** in the algorithm is said to be **tail-recursive**. It has
been **proven** that any **tail-recursive algorithm** can be implemented
using **iteration** instead of the recursion. This is usually **more
efficient**, because it **eliminates** the **function call overhead**
and **memory usage** that are inherent in the recursion.

The following example uses an XTRAN rules file
comprising **86** non-comment lines of "meta-code"
(XTRAN's rules language) to compare execution times of
recursive vs. iterative computation of factorials. The rules took less
than **¾ hour** to write and about **¼ hour** to
debug. (That's right, only **1 hour total**!)

The rules repeatedly prompt for a **number to do** and the **number of
computations** (to get a meaningful time result). They then **compute
the factorial** both **recursively** and **iteratively** the specified
**number of times**, and **show the results**.

How can such **powerful** and **generalized computation**
be **automated** in **only 1 hour** and **only 86 code lines**
of XTRAN **rules**? Because there is
so much **capability already available** as part of
XTRAN**'s rules language**. These rules take
advantage of the **following functionality**:

**Text formatting****Regular expression matching****Creating new meta-functions written**in**meta-code**, which we call**user meta-functions****Recursive user meta-functions****Meta-variable**and**meta-function pointers**

The **input to** and **output from** XTRAN
are **untouched**.

### Process Flowchart

Here is a flowchart for this process, in which the elements are color coded:

**BLUE**for XTRAN versions (runnable programs)**ORANGE**for XTRAN rules (text files)

## Interactive results (*this* indicates user
input):

Number whose n! you want, 1-10 [done]:5<ENTER>Number of computations:5<ENTER>Result: 120 Recursive: 0 seconds for 5 computations Iterative: 0 seconds for 5 computations Number whose n! you want, 1-10 [done]:15<ENTER><BELL>?Number must be between 1 and 10! Number whose n! you want, 1-10 [done]:10<ENTER>Number of computations:1000<ENTER>Result: 3628800 Recursive: 2 seconds for 1000 computations Iterative: 2 seconds for 1000 computations Number whose n! you want, 1-10 [done]:10<ENTER>Number of computations:2000<ENTER>Result: 3628800 Recursive: 4 seconds for 2000 computations Iterative: 3 seconds for 2000 computations Number whose n! you want, 1-10 [done]:xyz<ENTER><BELL>?You must enter an integer, or just <ENTER> when done! Number whose n! you want, 1-10 [done]:10<ENTER>Number of computations:5000<ENTER>Result: 3628800 Recursive: 12 seconds for 5000 computations Iterative: 7 seconds for 5000 computations Number whose n! you want, 1-10 [done]:<ENTER>