What differences between reentrant function and recursive function?

Answer 1

A reentrant function is called by the program during execution and can be interrupted and recalled later. A recursive function can call itself during execution and repeats itself without interruption.

Answer 2

A non-recursive function is simply an ordinary function. A recursive function only differs from an ordinary function in that it calls itself at some point.

Recursive functions are often used to implement naturally recursive algorithms. For instance, the following example calculates the factorial of n (where n! = 1 * 2 * 3 * ... * n):

unsigned f (unsigned n) {

if (n<2)

return 1;

else

return f (n-1) * n; // recursive call

}

This function can also be written more tersely using the ternary condition operator:

unsigned f (unsigned n) { return n<2 ? 1 : f (n-1) * n; // recursive call

}

Whichever you use is usually a matter of taste; there should be no advantage of one over the other.

To see how this works, let's imagine we invoked f (5):

f (5): 5 is not less than 2 so we return f (5-1) * 5 -- which returns f (4) * 5

f (4): 4 is not less than 2 so we return f (4-1) * 4 -- which returns f (3) * 4

f (3): 3 is not less than 2 so we return f (3-1) * 3 -- which returns f (2) * 3

f (2): 2 is not less than 2 so we return f (2-1) * 2 -- which returns f (1) * 2

f (1): 1 is less than 2 so we return 1

When we reach the f (1) instance we reach the end point of recursion because 1 is less than 2 (the terminating condition). The return value, 1, can then be returned to the previous instance of the function, f (2), which can subsequently calculate its return value, 1 * 2 = 2. In turn, f (3) can return 2 * 3 = 6 to f (4) which can return 6 * 4 = 24 to f (5) which can (finally) return 24 * 5 = 120 to the original caller. That is, f (5) == 120.

Although the factorial algorithm is a naturally recursive algorithm, not all naturally recursive algorithms benefit from a recursive function. We have to keep in mind that every recursion creates a new stack page upon the call stack because we need to keep track of the previous instance of the function, and setting up those stack pages has a cost in terms of performance and memory consumption. We also have to keep in mind that the call stack is fixed-length and the deeper the recursions the more stack space we consume.

The factorial function can actually be implemented more efficiently using a non-recursive function:

unsigned f (unsigned n) {

unsigned result = 1;

while (n > 1) {

result *= n;

n--;

}

return result;

}

We know this is more efficient because the recursive function requires O(n) stack space whereas the non-recursive function requires O(1) space. Although the time complexity is the same for both, O(n), the non-recursive solution is composed of trivial operations and should perform at least as well as the recursive solution.

Most recursive algorithms can benefit in some way from non-recursive solutions, thus the utility of a recursive function is often only of benefit in terms of readability. For example, the in-place quicksort algorithm is easily expressed recursively as follows:

template

void quicksort (iter begin, iter end) {

if (distance (begin, end) < 2) return;

iter pivot {partition (begin, end)};

quicksort (begin, pivot);

quicksort (pivot+1, end);

}

Much of the complexity is hidden in the (non-recursive) partition () function which does most of the actual work, splitting the half-closed sequence [begin:end) into two sequences around a pivot value selected from the sequence, with all values less than the pivot value placed in the lower portion of the sequence [begin:pivot) and all values greater than or equal to the pivot value placed in the upper portion of the sequence [pivot+1:end). In other words, the pivot value is in the correct place within the overall sequence, but the values on either side may still be unsorted. These shorter sequences are simply smaller versions of the same problem, thus we can recursively apply the same algorithm to each sequence in turn.

The end point of recursion is reached whenever a sequence has fewer than 2 elements because an empty sequence or a sequence of 1 element can always be regarded as being already sorted.

Expressing this same algorithm non-recursively is a bit more involved but ultimately hinders readability:

template

void quicksort (iter begin, iter end) {

std::stack> stack {};

stack.push ({begin, end});

while (stack.empty() == false) {

begin = stack.top().first();

end = stack.top().second();

stack.pop();

if (distance (begin, end)<2) continue;

iter pivot {partition (begin, end)};

stack.push ({begin, pivot});

stack.push ({pivot+1, end});

}

}

Whether this is more efficient than the recursive solution is debatable. The recursive solution makes use of the call stack which is both readily available and extremely fast to use; it is an integral part of "the system" and no user-defined stack can ever compete with it in terms of performance. Worse, the memory used by a user-defined stack is in addition to the memory already allocated to the call stack, so we actually end up using more memory overall.

In general, if a naturally recursive algorithm needs to maintain state before a recursion in order to make use of that state after returning from a recursion, then use a recursive function. However, if state does not need to be maintained or can at least be maintained with equal or better efficiency, then we should use an iterative function. However, these are just general guidelines; if in doubt, performance test both methods.

Answer 3

A recursive function can only call itself, as it is not open to other connections. A reentrant function can connect to several data sets simultaneously.

Answer 4

See if the fuction calls itself, if yes, it's recursive otherwise it's not a recursive function.