Dave was on a roll. He asked, “Who has change for a dollar?” but nobody understood why he would derail an argument over proofs when everybody had already paid for the coffee. Alice was more to the point “You know Dave, sometimes I just don't understand why you say the things you do.” Dave smiled (maybe it was more of a smirk) “It's about making change. The terms in this sequence are the fewest number of coins required to make change.” Bob said “I don't get it.” Dave continued “The term $a_n$ is the fewest number of U.S. coins required to total to $n$ cents.” Now everyone groaned, everyone except Carlos, who thought that at least this time, Dave was really clever.
“Well”, said Bob, “that takes care of the strange sequence, but I still don't see any difference between induction and recursion.” Dave couldn't keep quiet “No one does.” Xing thought differently and said “In many programming languages, you try to avoid recursion, preferring to use loops instead. Otherwise, you wind up overloading the stack. As just one example, you can compute the greatest common divisor $d$ of $m$ and $n$, as well as find $a$ and $b$ so that $d=am+bn$ using a loop—with very little storage. The recursive approach discussed previously, with the inherent back tracking at the end, isn't really necessary.” Yolanda was impressed with Xing's extensive programming experience and knowledge, but Alice was less so.