0.4 Recursion  (Page 2/2)

One common example (using the Pascal programming language, in this case) is the function used to calculate the factorial of an integer :

function Factorial(x: integer): integer;

begin

if x<= 1 then

Factorial := 1

else

Factorial := x * Factorial(x-1);

end

Here is the same function coded without recursion. Notice that this iterative solution requires two temporary variables; in general, recursive formulations of algorithms are often considered "cleaner" or "more elegant" than iterative formulations.

function Factorial(x: integer): integer;

var i, temp: integer;

begin

temp := 1;

for i := 1 to x do

temp := temp * i

Factorial := temp

end

Another comparison that even more clearly demonstrates the relative "elegance" of recursive functions is the Euclidean algorithm , used to compute the greatest common divisor of two integers. Below is the algorithm with recursion, coded in C :

int gcd(int x, int y)

{

if (y == 0)

return x;

else

return gcd(y, x % y);

}

Below is the same algorithm using an iterative approach:

int gcd(int x, int y)

{

while (y != 0) {

int r = x % y;

x = y;

y = r;

}

return x;

}

The iterative algorithm requires a temporary variable, and even given knowledge of the Euclidean algorithm it is more difficult to understand the process by simple inspection, although they are very similar in their steps.

Recursion versus iteration

In the "factorial" example the iterative implementation is likely to be slightly faster in practice than the recursive one. This is almost definite for the Euclidean Algorithm implementation. This result is typical, because iterative functions do not pay the "function-call overhead" as many times as recursive functions, and that overhead is relatively high in many languages. (Note that an even faster implementation for the factorial function on small integers is to use a lookup table .)

There are other types of problems whose solutions are inherently recursive, because they need to keep track of prior state. One example is tree traversal ; others include the Ackermann function and divide-and-conquer algorithms such as Quicksort . All of these algorithms can be implemented iteratively with the help of a stack , but the need for the stack arguably nullifies the advantages of the iterative solution.

Another possible reason for choosing an iterative rather than a recursive algorithm is that in today's programming languages, the stack space available to a thread is often much less than the space available in the heap, and recursive algorithms tend to require more stack space than iterative algorithms.

4.3. recursive functions

(From Wikipedia, the free encyclopedia)

Functions whose domains can be recursively defined can be given recursive definitions patterned after the recursive definition of their domain.

The canonical example of a recursively defined function is the following definition of the factorial function f(n):

Given this definition, also called a recurrence relation , we work out f(3) as follows:

f(3) = 3 * f(3 − 1)

= 3 * f(2)

= 3 * 2 * f(2 − 1)

= 3 * 2 * f(1)

= 3 * 2 * 1 * f(1 − 1)

= 3 * 2 * 1 * f(0)

= 3 * 2 * 1 * 1

= 6

4.4. tail - recursive functions

(From Wikipedia, the free encyclopedia)

Tail-recursive functions are functions ending in a recursive call. For example, the following C function to locate a value in a linked list is tail-recursive, because the last thing it does is call itself:

struct node {

int data;

struct node *next;

};

struct node *find_value(struct node *head, int value)

{

if (head == NULL)

return NULL;

if (head->data == value)

return head;

return find_value(head->next, value);

}

The Euclidean Algorithm function, following a similar structure, is also tail-recursive. On the other hand, the Factorial function used as an example in the previous section is not tail-recursive, because after it receives the result of the recursive call, it must multiply that result by x before returning to its caller. That kind of function is sometimes called augmenting recursive.

The Factorial function can be turned into a tail-recursive function:

function Factorial(acc: integer, x: integer): integer;

begin

if x<= 1 then

Factorial := acc

else

Factorial := Factorial(x * acc, x - 1);

end

Function should then be called by Factorial(1, x).

Notice that a single function may be both tail-recursive and augmenting recursive, such as this function to count the odd integers in a linked list:

int count_odds(struct node *head)

{

if (head == NULL)

return 0;

if (head->data % 2 == 1)

return count_odds(head->next) + 1; /* augmenting recursion */

return count_odds(head->next); /* tail recursion */

}

The significance of tail recursion is that when making a tail-recursive call, the caller's return position need not be saved on the call stack ; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, on compilers which support tail-recursion optimization, tail recursion saves both space and time.