Recursion

What is Recursion?

Recursion is a function calling itself. This means that it repeatedly executing a block of code, so it is similar to iteration. Indeed, exam questions will often ask you to examine a recursive function and re-write it using iteration.

This is the basic idea:

public void DoSomething()
{
    DoSomething()
}

In the recursive function above we have an issue, it will never end! A recursive function must have an exit condition. We call this the base case or terminating condition.

Why use Recursion?

Recursion is considered to be neater and more concise than iteration with fewer lines of code. However, the downside is that a recursive might be more challenging to understand.

Examples of Recursion - Binary Search

The code below implements a binary search function using recursion.

It takes as parameters: the array, the search value, the beginning and end of the list.

If the search value is found mid is returned.

If the mid point in the array is too high the function calls itself passing the first half of the array (up to mid -1)

If the mid point in the array is too low, the function calls itself passing the last half of the array (from mid + 1)

Recursion - Advantages and Disadvantages

• Recursion is self-referential. That is, it calls itself
• Recursion uses more memory than iteration. This is because recursion declares new separate copies of variables which are put onto the stack each time the function is called. Whereas iteration re-uses the variables.
• These variables remain on the stack until the recursive function meets the terminating condition and begins to unwind. If the function is called enough times (or too much memory is allocated inside the function) a recursive function can run out of memory and cause a stack overflow error. Iteration can not run out of memory.
• Recursion does, however, often express a problem in fewer lines of code than iteration, which can look more elegant and compact. This is easier to read than iteration. This is particularly true for divide and conquer algorithms e.g. Binary Search, Merge Sort, Quick Sort, Binary Tree traversal.

Want to know more?

There are more examples on Isaac ComputerScience.