Recursion: base case vs. small version 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:


Find the base case 
Find the small version of the problem
(Implement the recursive solution)
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.