Recursive algorithm

A recursive algorithm is in essence an algorithm which calls itself over and over again, eventually terminating when a end condition is met.

In 'C', this example of of recursive factorial function (algorithm):

---

int Factorial(n) { if (n == 1)

       return(n)
   else
       return(n*Factorial(n-1));

}

---

If you examine this short code block, you can see how it functions. For example, if the function Factorial with n=3, it runs like this:

1)Factorial function called with n=3

2)Else branch is taken

3)Return value of Factorial, this time with argument of n=2

4)In new function call, Else branch is chosen again

5)Return value of Factorial with arg n=1

6)New functional call of Factorial terminates on If statement, and returns value of 1

7)Next function return yields 2 * 1

8)Last function return yields 3 * 2 * 1, and terminates with a value of 6.

The computer running this sequence uses what is known as a stack to hold these function calls with their associated values until each is resolved in reverse order. These wait in line to be resolved one at a time.

Factorial(1)\n Factorial(2)\n Factorial(3)

Recursive algorithms are used for many purposes. They can be used to clear an overload of a holograms interactive matrix, or used to retrieve missing data from a log. (ENT: "Affliction"; VOY: "Nothing Human", "Warhead", "Renaissance Man")

Most Cardassian access codes are based on a recursive encryption algorithm. (DS9: "In Purgatory's Shadow")

See also

• Subspace infrared algorithm

External Links

• Recursion at Wikipedia