Wyo Data Structures - Ch. 5 Notes

Objective #1: Understand and explain the use of recursion.

• A recursive function is a function that calls itself
• A recursive function includes a base case and one or more recursive cases. A recursive function is usually implemented as an if, if/else, or if/else if/else statement.
• A recursive function is tail recursive if the recursive call is the last statement in the function. Since local variables no longer need to be kept in the stack frame, efficient compilers usually translate tail recursive C++ code into maching language that simply uses iterative code. In this case, the compiler treats function parameters as variables associated with the loop and no stack is required.
• The simplest kind of recursive function includes a base case and just one recursive case. This type of function typically results in a series of pushes to the stack and then a series of pops. More complicated recursive functions however include a base case and two or more recursive function calls. This type of function results in some pushes followed by a few pops but then more pushes and then a few pops until the stack grows to its largest size and then the reverse sequence with more pops than pushes.
• Do not use recursion when:
  • a function contains large local arrays since this will cuase large stack frames that eventually may cause stack overflow
  • a function manipulates any global variables
  • the same function could be implemented with plain loop iteration and result in faster performance
• Recursion should mainly be used to simplify your code without too much loss of performance. Recursion can be used rather efficiently with nested data structures or branching processes. For example, traversing trees is a good application for recursion. However, with linear structures such as arrays, you might as well use iteration rather than recursion.
• If you've studied mathematical induction in math class, you'll see that it relates to recursive programming.
• Try implementing the following algorithms with recursion rather than iteration and decide which ones are much more inefficient with the recursive solution:
  • computing a number to a power
  • computing the Fibonacci sequence
  • computing a factorial
  • detecting palindromes
  • a binary search
  • a selection sort
  • an insertion sort
  • a merge sort
  • a quicksort
  • printing the nodes of a linked list
  • printing the nodes of a linked list in reverse order
  • generating all of the possible permutations of a given set of characters
  • N Choose K (combinatorics)
  • Towers of Hanoi
  • Eight Queens