Currently I'm experimenting a little bit with recursive functions in Python. I've read some things on the internet about them and I also built some simple functioning recursive functions myself. Although, I'm still not sure how to use the base case.
I know that a well-designed recursive function satisfies the following rules:
def checkstring(n, string):
if len(string) == 1:
if string == n:
if string[-1:] == n:
return 1 + checkstring(n, string[0:len(string) - 1])
return checkstring(n, string[0:len(string) - 1])
That is absolutely fine and valid function. Just remember that for any scenario that you can call a recursion function from, there should be a base case reachable by recursion flow.
For example, take a look at the following (stupid) recursive function:
def f(n): if n == 0: return True return f(n - 2)
This function will never reach its base case (n == 0) if it was called for odd number, like 5. You want to avoid scenarios like that and think about all possible base cases the function can get to (in the example above, that would be 0 and 1). So you would do something like
def f(n): if n == 0: return True if n == 1: return False if n < 0: return f(-n) return f(n - 2)
Now, that is correct function (with several ifs that checks if number is even).
Also note that your function will be quite slow. The reason for it is that Python string slices are slow and work for O(n) where n is length of sliced string. Thus, it is recommended to try non-recursive solution so that you can not re-slice string each time.
Also note that sometimes the function do not have strictly base case. For example, consider following brute-force function that prints all existing combinations of 4 digits:
def brute_force(a, current_digit): if current_digit == 4: # This means that we already chosen all 4 digits and # we can just print the result print a else: # Try to put each digit on the current_digit place and launch # recursively for i in range(10): a[current_digit] = i brute_force(a, current_digit + 1) a =  * 4 brute_force(a, 0)
Here, because function does not return anything but just considers different options, we do not have a base case.