- Forward


Recursive Thinking
An Introduction to Recursive Algorithms


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Definitions
Back SMYC Forward
  • 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
Nerd Humor
Back SMYC Forward

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

/upload

/imgs
(Courtesy of xkcd)

Nerd Humor (cont.)
Back SMYC Forward
/imgs
(Courtesy of xkcd)
What Do These "Jokes" Have In Common?
Back SMYC Forward
  • One Answer:
    • The definition/object/action involves the definition/object/action itself.
  • Another Answer:
    • Refinement/Nesting/"Looking Deeper"
Using Recursion in Definitions
Back SMYC Forward
  • 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)\)
Using Recursion in Definitions (cont.)
Back SMYC Forward
  • 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\)
Using Recursion in Definitions (cont.)
Back SMYC Forward
  • 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)
From Definition to Algorithm
Back SMYC Forward
  • 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
Designing Recursive Algorithms
Back SMYC Forward
  • 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?
An Obvious Example - Factorial
Back SMYC Forward
  • The Base Case:
    • The number is 0
  • Refinement:
    • Reduce the number by 1 and evaluate the factorial
    • Multiply the result and the number
An Example - Print the Digits of a Number
Back SMYC Forward
  • 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
About Printing the Digits of a Number
Back SMYC Forward
  • 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?
An Example - Searching through a Book
Back SMYC Forward
  • 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
About Searching through a Book
Back SMYC Forward
  • 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
An Example - Making Change
Back SMYC Forward
  • 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.)
About Making Change
Back SMYC Forward
  • 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)
Thinking Recursively - A Summary
Back SMYC Forward
  • 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
Thinking Recursively - An Observation
Back SMYC Forward

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

Hackles-Recursion
(Courtesy of Hackles)
Algorithms Involving Recursion
Back SMYC Forward
  • 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
There's Always More to Learn
Back -