I\'m reviewing the definition of recursion and in my notes are two questions abo
ID: 651007 • Letter: I
Question
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)
Explanation / Answer
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.