Recursive Function Versus Non-recursive Function

◀ One Function Versus Multiple Functions▶ Function Template Amazon First of all let’s see the differences between a recursive function and a non-recursive one.

• A recursive function in general has an extremely high time complexity while a non-recursive one does not.
• A recursive function generally has smaller code size whereas a non-recursive one is larger.
• In some situations, only a recursive function can perform a specific task, but in other situations, both a recursive function and a non-recursive one can do it.

Here is a recursive version of calculating the Fibonacci number:

/* compute n’th Fibonacci number by using recursion */
int fibonacci(int n){
	if(n<=2)
		return 1;
	else
		return fibonacci(n-1) + fibonacci(n-2);
}

An experienced programmer should have no problem understanding the logic behind the code. As we can see, in order to compute a Fibonacci number, Fn, the function needs to call Fn-1 and Fn-2. Fn-1 recursively calls Fn-2 and Fn-3, and Fn-2 calls Fn-3 and Fn-4.

In a nutshell, each call recursively computes two values needed to get the result until control hits the base case, which happens when n<=2.

You can write a simple main() that accepts an integer n as input and outputs the n’th Fibonacci by calling this recursive function and see for yourself how slowly it computes as n gets bigger. It gets horrendously slow once n gets past 40 on my machine.

Here is a non-recursive version that calculates the Fibonacci number:

/* compute n’th Fibonacci number by using a loop */
int fibonacci(int n){
	if(n<=2)
		return 1;
	int i, last, nextToLast, result;
	last = 1;
	nextToLast = 1;
	result = 1;
	for(i=3; i<=n; i++){
		result = last + nextToLast;
		nextToLast = last;
		last = result;
	}
	return result;
}

The logic here is to keep the values already computed in variables last and nextToLast in every iteration of the for loop so that every Fibonacci number is computed exactly once. In this case, every single value is computed only once no matter how big n is.

Try to replace the recursive version with this version and see how fast you get the result when n is very big. By analyzing these examples, we should have no problem seeing that recursion usually has small code size, but sometimes the price it pays in the execution time is far too dear.

In general, whenever both a recursive function and a non-recursive function are feasible, I usually go for the non-recursive version.
Now let’s shift our attention to situations where recursion is absolutely necessary. One of the most well-known examples is the clone function for a binary search tree. Say at some point in the program you want to make two separate copies of the same tree, called theTree, how do you do that?

Many green programmers simply declare a new pointer to tree and make it point to theTree just as follows:

BinarySearchTree *cloneTree = theTree;

Then they happily think that they have made an identical copy successfully and proceed to perform operations on cloneTree. The truth is that cloneTree simply points to what theTree points to; changing either cloneTree or theTree changes the only tree that exists.

Therefore, to have two completely identical and independent trees, you need to use a function that recursively copies the right and left subtrees of the original tree to the new tree. The function may look something like this:

BinarySearchTree* BinarySearchTree::clone(BinaryNode *t){		
  if(t==NULL)
    return NULL;
  else
    return BinaryNode(t->element, clone(t->left), clone(t->right));
}

The first argument to BinaryNode is the data the node contains; the second argument is a pointer to BinarySearchTree which is the root of the left subtree; the third argument is a pointer to BinarySearchTree which is the root of the right subtree.

Basically, this function returns a node which is identical to the root of the original tree by recursively constructing the left and the right subtrees until they hit the leaf nodes. As we can see, this operation is not achievable by using a non-recursive function because you do not know what the tree looks like in advance. In this type of situation, we can rely only on recursion.

There are plenty of other examples to illustrate how powerful recursion is. As you become more experienced you will see how important and powerful it is!
◀ One Function Versus Multiple Functions▶ Function Template