The purpose of this quiz is to give you a chance to focus your knowledge of simple recursion in C++.
Label each 'part' of the following recursive definition. Explain (briefly) what each part's purpose is. (Hint: There are four parts to any recursion.)
n! = n(n-1)!
0! = 1
base case stops the recursion: 0! = 1
reduction step reduces the size of the problem for the recursive call:
(n-1)
recursive call defines the function in terms of a smaller version of
itself: (n-1)!
build phase puts the recursive result back together with problem size
n info to make the final answer: n(n-1)!
Show how to code this as a recursive function:
long long factorial(short n)
{
return n < 0 ? -1
: n < 2 ? 1
: n * factorial(n-1);
}
Find and fix any errors in the following function:
long fib(short n)
{
return fib(n-1) + fib(n-2);
}
It needs a pair of base cases. We can either let fib(0) be
0 or 1; but fib(1) needs to be 1. This can be done with a
simple ?: operation like so:
return n < 0 ? -1
: n < 2 ? 1
: fib(n-1) + fib(n-2);
(Also note that I've included error protection for invalid
domain values.)
Briefly explain the concept of memoization as it applies to recursive functions. (What's the basic approach? What is it trying to accomplish? When it is applicable? Etc.)
Memoization basically remembers previously calculated values to make
future recursive calls mere look-ups rather than re-calculations. Make
a static local array or vector and initialize the base case positions
-- once. Then, before making the recursive call, just see if you've
already calculated the requested value and, if so, return it from your
container. If not, recurse as normal, but save the result for future
calls.
Explain how the run-time stack is used during function calls. How can this lead to stack overflow? (No, not the website...)
Each function called gets a new slice of stack memory to store its
value parameters and local variables (and return value). Each new
slice is formed 'above' the caller's slice.
The stack is of finite size, however, so there are only so many calls
we can make -- as each takes up a little more of this stack space.
When too many functions are called, we'll run out of call stack and
suffer a stack overflow. (On the other hand, if too many returns are
executed, we'll suffer a stack underflow.)
Show how you would memoize either factorial or Fibonacci.
long long factorial(short n)
{
static vector<long long> fac_mem;
if (fac_mem.empty())
{
fac_mem.push_back(1);
fac_mem.push_back(1);
}
return (vector<long long>::size_type)n
< fac_mem.size()
? fac_mem[n]
: *fac_mem.insert(fac_mem.end(),
n * factorial(n-1));
}
long fib(short n)
{
static vector<long> fib_mem;
if (fib_mem.empty())
{
fib_mem.push_back(1);
fib_mem.push_back(1);
}
return (vector<long>::size_type)n
< fib_mem.size()
? fib_mem[n]
: *fib_mem.insert(fib_mem.end(),
fib(n-2) + fib(n-1));
}
Is memoization of recursive functions always a good idea...or even possible?
No. Any situation where we are recursively printing something could
not be memoized since the result is not a calculation but a screen
display. Also, sometimes the calculation has a rather large memory
footprint and shouldn't be remembered for sake of RAM. Other similar
situations should be evaluated with care.