What are the differences between iteration and recursion?

Answer 1

In computer programming, both iteration and recursion define a type of loop. With iteration, the loop makes use of the current instance of the function in which it appears. When we start a new iteration, the "state" of the previous iteration is carried forward to the new iteration but we cannot return to a previous state. With recursion we can return to a previous state because each recursion invokes a new instance of the function which automatically saves the state of the current instance. Whenever we return from an instance, the result of that instance can be passed back to the previous instance and be incorporated into its restored state.

To demonstrate, consider the following iterative loop (in C++):

for (unsigned i=0; i<=10; ++i)

std:cout << i << std::endl;

Here we print the numbers from 0 to 10. Each iteration of the loop is not reliant upon the previous iteration so recursion is not required. However, we can achieve the same thing using recursion:

void print (unsigned max)

{

if (max!=0) print (max-1);

std::cout << max << std::endl;

}

Here we test the value of max. If it is non-zero we invoke a new instance of the same function, recursively passing the decremented value of max. Thus if max were 10, we'd invoke print (9), which invokes print (8), then print (7) and so on, until print (0) is invoked. At this point there are 11 instances of the print function, thus the "depth of recursion" is 11 and each instance of the function has its own instance of the max variable. Since max is zero in the 11th instance, the condition fails and the next statement is executed, which prints the value 0 and returns to the previous instance where max was 1. In that instance we'd already tested if max were zero so we continue with the next statement which prints the value 1 and returns to the previous instance where max was 2. The recursions continue to "unwind", each printing their own max value until we arrive back at the first instance where max was 10 and the value 10 is printed.

This is not a good example of recursion, but it clearly demonstrates how recursion works. In essence, the recursive loop works backwards from 10 to 0, then unwinds to print from 0 to 10.

There are many examples of naturally recursive algorithms that are more efficiently implemented using iterative loops. The reason they are more efficient is because whenever we invoke a function we must save the state of the current function, which means pushing all the local variables onto the call stack. We also have to push the return address onto the call stack so that the called function can pass control back to the current function at the correct place. Finally, we have to push all the arguments to the called function onto the stack before we pass control to that function. Upon entering the called function, the arguments are popped from the stack and it can begin processing. When the function returns, the return address is popped from the stack and control passed to that address. When the caller regains control, its local variables are popped from the stack. If the called function returned a value, it is retrieved from the appropriate CPU register and assigned to the appropriate variable.

This is a lot of work, which is why C++ compilers make use of inline expansion, replacing function calls with the actual code in the function. However, not all functions can be inline expanded. Recursive functions are particularly problematic when the depth of recursion is variable but even when a particular invocation is constant, the compiler may limit the number of expansions because the efficiency gained by eliminating each function call needs to be balanced with the increased code size, which can be counter-productive if the function is non-trivial.

However, there are cases where recursion is more efficient than an iterative solution. Our example above is an example of depth-first recursion which is a naturally recursive algorithm, where we dig down to reach an exit condition and then work our way back up. For instance, to traverse the nodes of a binary tree using depth-first search, we initiate the traversal by passing the root node to the traversal function. This function performs three tasks upon the node it receives: first traverse the node's left node; then print the node's value; then traverse the node's right node. In other words, the function recursively invokes itself twice. Writing such a function iteratively is simply not possible because the depth of each recursion can vary so wildly.

This type of function uses a "divide and conquer" algorithm and in cases where the depth of recursion is unpredictable (non-constant) recursion is often the most efficient choice because the call stack serves a purpose that cannot easily be implemented with an iterative approach. However, because such functions often make use of tail recursion (where the final statement of the function is a recursion), the call stack becomes redundant because the current instance of the function would simply return immediately after that recursion. In these cases, a good compiler can modify the function such that the tail recursion becomes an iteration of the same instance of the function; rather than invoking a new instance it simply re-invokes the same instance with modified arguments. Going back to our traversal function, once the function has printed the current node's value, we no longer need to remember the current node, we can simply assign its right node as the current node and go back to the beginning of the same instance of the function. This is much more efficient because we only perform one assignment as opposed to going to the expense of a function call, which results in a minimum of three pushes and three pops from the call stack.

Answer 2

Iterations are the looping conditions which continues till a particular condition is met whereas the recursions are related to calling the function itself repeatedly