Chapter:

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Recursion vs. Iteration

In the preceding section, we studied a function that can easily be implemented either re-cursively or iteratively. In this section, we compare the two approaches and discuss why you might choose one approach over the other in a particular situation.

Recursion vs. Iteration

 

In the preceding section, we studied a function that can easily be implemented either re-cursively or iteratively. In this section, we compare the two approaches and discuss why you might choose one approach over the other in a particular situation.

 

Both iteration and recursion are based on a control statement: Iteration uses a repeti-tion statement (e.g., for, while or dowhile); recursion uses a selection statement (e.g., if, ifelse or switch). Both iteration and recursion involve repetition: Iteration explic itly uses a repetition statement; recursion achieves repetition through repeated function calls. Iteration and recursion each involve a termination test: Iteration terminates when the loop-continuation condition fails; recursion terminates when a base case is recognized. Iteration both with counter-controlled repetition and with recursion gradually approaches termination: Iteration keeps modifying a counter until the counter assumes a value that makes the loop-continuation condition fail; recursion keeps producing simpler versions of the original problem until the base case is reached. Both iteration and recursion can occur infinitely: An infinite loop occurs with iteration if the loop-continuation test never becomes false; infinite recursion occurs if the recursion step does not reduce the problem each time via a sequence that converges on the base case or if the base case is incorrect.

 

One negative aspect of recursion is that function calls require a certain amount of time and memory space not directly spent on executing program instructions. This is known as function-call overhead. Because recursion uses repeated function calls, this overhead greatly affects the performance of the operation. In many cases, using repetition statements in place of recursion is more efficient. However, some problems can be solved more ele-gantly (and more easily) with recursion.

In addition to the Factorial function examnple (Fig. 9.11), we also provide several recursion exercises—raising an integer to an integer power (Exercise 9.34), visualizing recursion (Exercise 9.35) and sum of two integers (Exercise 9.36). Also, Fig. 14.26 uses recursion to traverse an XML document tree.


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail


Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.