Python: base case of a recursive function

Question

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:

• There is a base case.
• The recursive steps work towards the base case.
• The solutions of the subproblems provide a solution for the original problem.

Now I want to come down to the question that I have: Is it allowed to make up a base case from multiple statements?

In other words is the base case of the following self written script, valid?

def checkstring(n, string):

 if len(string) == 1:
    if string == n:
        return 1
    else:
        return 0


 if string[-1:] == n:
    return 1 + checkstring(n, string[0:len(string) - 1])
 else:
    return checkstring(n, string[0:len(string) - 1])
print(checkstring('l', 'hello'))

Answer 1

Yes, of course it is: the only requirement on the base case is that it does not call the function recursively. Apart from that it can do anything it wants.

Answer 2

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 = [0] * 4
brute_force(a, 0)

Here, because function does not return anything but just considers different options, we do not have a base case.

Answer 3

In simple terms Yes, as long as it does not require the need to call the function recursively to arrive at the base case. Everything else is allowed.