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)
Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Am I the only one who finds the term "recursing" loathsome? $\endgroup$
    – Rick Decker
    Oct 2, 2014 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".

Improve this answer
$\endgroup$
5
  • $\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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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