• Recurrence Relation:
  • A relation between successive values of a function that allows the systematic calculation of values, given an initial value
• Recursion:
  • Formal - Computation using a recurrence relation
  • Informal - A function is recursive (or "uses recursion") if it calls itself

There are two kinds of people in the world, those who divide the world into two kinds of people and those who do not.

Recursion (n) See "Recursion"

GNU

(Courtesy of xkcd)

(Courtesy of xkcd)

• One Answer:
  • The definition/object/action involves the definition/object/action itself.
• Another Answer:
  • Refinement/Nesting/"Looking Deeper"

• The Concept:
  • A function is defined recursively if the value of the base cases are given (e.g., \(f(0)\) is given) and the value of \(f(n)\) is given in terms of \(f(n-1)\) for the other cases (e.g., for \(n > 0)\)
• An Example - A Recursive Definition of the Factorial:
  • \(0! = 1\) (i.e., \(f(0) = 1\))
  • \(n! = (n-1)! \cdot n\) for \(n > 0\) (i.e., \(f(n) = f(n-1) \cdot n\) for \(n > 0)\)

• Recursive Definitions Can Be Convenient:
  • \(0! = 1\)
  • \(n! = (n-1)! \cdot n\) for \(n > 0\)
• Recursive Definitions Aren't Always Necessary/Used:
  • \(0! = 1\)
  • \(n! = \prod_{i=1}^{n} i\) for \(n > 0\)

• Another Example - Fibonacci Numbers:
  • \(F(0) = 0\)
  • \(F(1) = 1\)
  • \(F(n) = F(n-1) + F(n-2)\) for \(n > 1\)
• Fibonacci Numbers - Some Things to Note:
  • There is more than one base case
  • The function calls itself from more than one place (making it more complicated and inefficient than it seems at first glance)

• Some Situations:
  • The recursive algorithm is easy to identify because a recursive definition was used to describe the problem
• Other More Interesting Situations:
  • The problem is not defined using recursion but can be most easily solved using recursion (which requires a different way of thinking than you are used to)
• Some Problematic Situations:
  • A recursive definition was used to describe the problem but a recursive algorithm is inefficient/inappropriate

• Identifying the Base Case:
  • What is (are) the easy cases(s)? In other words, what case(s) can I solve trivially?
• Refining the Difficult Cases:
  • How can I refine/reduce a difficult case to make it easier? In other words, how can I make progress?

• The Base Case:
  • The number is 0
• Refinement:
  • Reduce the number by 1 and evaluate the factorial
  • Multiply the result and the number

• The Base Case:
  • The number consists of 1 digit
• Refinement:
  • Make the number one digit smaller (e.g., integer division by 10) and recurse
  • Print the digit that was removed

• An Complaint:
  • What a stupid example -- this isn't useful at all
• A Response - Even "Stupid" Examples can be Instructive:
  • Suppose you have to print numbers in other bases?
  • Why does the order of the two steps in the algorithm matter?

• The Problem:
  • Find the definition of a word that may or may not be in a range of pages in a dictionary (that, for simplicity, contains one word per page)
• The Base Case:
  • You have one page to "search"
• Refining the Difficult Cases:
  • Search through the first half of the range of pages and search through the second half of the range of pages

• An Iterative Algorithm:
  • We could just start at the first page in the range and iteratively check each subsequent page
• Suppose the Book is a Dictionary:
  • The words are sorted so we can easily determine if a range of pages can possibly contain a given word (by looking at the word on the first page and the word on the last page)
• A Brief Introduction to a Topic of Subsequent Courses:
  • For a dictionary, the "efficiency" of the iterative and recursive algorithms are very different

• The Problem:
  • Determine the minimum number of coins needed to make a particular amount, \(K\), of "change"
• The Base Case:
  • When we can make change with exactly one coin
• Refining Difficult Cases:
  • For every value of c, we can compute the minimum number of coins to make c cents in change and K-c cents in change. (We assume that there is always a 1-cent coin and, hence, that there is always an answer.)

• A Greedy Algorithm:
  • Iteratively subtracting off the largest possible coin
• Performance of the Greedy Algorithm
  • Very fast
  • Works with U.S. money
  • Doesn't always work (e.g., suppose we had an 8 cent coin and wanted to change 13 cents -- the greedy algorithm's answer is one 10 and three 1s; the optimal answer is one 8 and one 5)

• The Process:
  • Identify the Base Case(s) (i.e., the case(s) that can be solved without recursion)
  • Refine the Other Cases (i.e., develop a way to move the other cases towards a/the base case; make progress)
• Refinement and Recursive Functions:
  • Move the parameters of the function that correspond to other cases towards the parameters that correspond to base cases
  • Use the value returned by the function call to move the answer closer to the correct answer

Recursive algorithms can be elegant, but require a different way of thinking (which can be difficult):

(Courtesy of Hackles)

• Classic Examples:
  • Towers of Hanoi
  • Eight Queens Problem
• Practical Examples:
  • Operating on directory "trees"
  • Compiling classes that depend on other classes
  • Expansion of #include statements by the C/C++ preprocessor