- 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.

/* 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,

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

You can write a simple

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

Try to replace the recursive version with this version and see how fast you get the result when

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

Many green programmers simply declare a new pointer to

BinarySearchTree *cloneTree = theTree;Then they happily think that they have made an identical copy successfully and proceed to perform operations on

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

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