0
$\begingroup$

I'm reviewing the definition of recursion and in my notes are two questions about a recursive problem. One question asks about the base case, the other one about the small version of the problem, I always get confused about which is which... can you help me to find a way to better understand these concepts?

The examples in the exercise are:

  • a function that determines if there is a "x" element in an array
  • a function that determines if the string is palindrome or not

for both:

  1. Find the base case
  2. Find the small version of the problem
  3. (Implement the recursive solution)
$\endgroup$
2
$\begingroup$

When you use recursion to solve a problem, you typically partition your input into one or more smaller instances (and possibly a part that you don't process further). Those smaller instances are what your exercise calls the small version.

Upon recursing, your inputs get smaller and smaller until it is no longer possible (or sensible) to further split them up. The inputs that are left to be solved directly are called the base case.

$\endgroup$
  • $\begingroup$ Am I the only one who finds the term "recursing" loathsome? $\endgroup$ – Rick Decker Oct 2 '14 at 15:50
0
$\begingroup$

"Small version" is wrong. What you have to find is a way to operate on the n+1 element assuming that the previous (or next) n elements have already been considered.

E.g.

Is there x in an array?

  • If the array is empty then no.
  • If the array is not empty then check the first element, if the first element is x then yes, if not then apply recursion, i.e. the answer is whether x is in the remainder of the array.

The second point is not a "small case", it is smaller in exactly one element than the general case. Infinite (arbitrarily long) minus one doesn't make for something "small".

$\endgroup$
  • $\begingroup$ You don't have to recurse into an instance that is exactly 1 smaller. (Think e.g. of binary sort.) $\endgroup$ – FrankW Oct 2 '14 at 14:17
  • $\begingroup$ I know, and I know quick sort. However the basic explanation of recursion and the way to understand it is just like that, from the n case to the n+1. That's the mathematical/theoretical way to see it, even if computationally there are more efficient options. $\endgroup$ – Trylks Oct 2 '14 at 14:20
  • $\begingroup$ @FrankW I would say it's even dubious whether we are speaking about a recursive function or something else if it cannot be modelled as $f(f(f\ldots(f(e))\ldots))$, where each application of $f$ produces the output for the n+1 case with the input for the n case. $\endgroup$ – Trylks Oct 2 '14 at 14:27
  • 2
    $\begingroup$ If $f(f(..),f(..))$ is not recursion for you, then you're using a definition, that is not very widespread in computer science. $\endgroup$ – FrankW Oct 2 '14 at 14:43
  • $\begingroup$ Fair enough, but still the application would happen in terms of case $n$ and $n\pm i$, just like Fibonacci $f(n) = f(n-1) + f(n-2)$. Note that $n$ may not be a parameter of the function, simply the case that requires one additional recursion step. $\endgroup$ – Trylks Oct 2 '14 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.