2

As part of a problem for CS1301, I'm trying to write a function using recursion that will perform the exact same thing as len(). However, I have two issues:

  1. I'm using global variables, where I haven't learned this yet in the course.
  2. The cs1301 autograder is telling me that my function is returning 26 instead of 13 (although when I run it, it prints 13). Not sure if this has something to do with global variable assignment.

Rest is self-explanatory as within the code below:

#We've started a recursive function below called
#measure_string that should take in one string parameter,
#myStr, and returns its length. However, you may not use
#Python's built-in len function.
#
#Finish our code. We are missing the base case and the
#recursive call.
#
#HINT: Often when we have recursion involving strings, we
#want to break down the string to be in its simplest form.
#Think about how you could splice a string little by little.
#Then think about what your base case might be - what is
#the most basic, minimal string you can have in python?
#
#Hint 2: How can you establish the base case has been
#reached without the len() function?

#You may not use the built-in 'len()' function.

def measure_string(myStr):
    global ind
    global count
    if myStr == "":
        try: return count+1
        except: return 0
    else:
        ind = 0
        try: count +=1
        except: count = 0
        return measure_string(myStr[ind+1:])
    
    
#The line below will test your function. As written, this
#should print 13. You may modify this to test your code.
print(measure_string("13 characters"))
ash
  • 25
  • 3
  • 4
    Yes, that's likely due to the globals. You'll need to reset them before each initial call. It's reasons like this that you should avoid globals. Global states have a tendency to bite you. Also, why are you using `try` here? I can't see the code in the `try` ever throwing, so it isn't serving a purpose. – Carcigenicate Mar 27 '21 at 23:55
  • @Carcigenicate `return count + 1` will fail if `count` is not defined yet; it's defined in the `else` branch, which may not have executed. – kaya3 Mar 27 '21 at 23:56
  • 3
    Why are these globals in the first place? You should pass them to the subcall as an argument, not through globals. – SuperStormer Mar 27 '21 at 23:56
  • 3
    Tasks like this really sadden me. This doesn't teach much of anything except how to misapply recursion. Please never use `global` and (almost) never use recursion. Recursion is suited for problems that have branching and reduce the search space better than linear, like divide and conquer. If you _have_ to use recursion, you can find the length of the string using an index instead of copying the whole string on every call with a slice which is quadratic. – ggorlen Mar 27 '21 at 23:56
  • @kaya3 There are much better ways to do that than try-except, though the rest of the code isn't exactly the best quality. – SuperStormer Mar 27 '21 at 23:57
  • @kaya3 Ha, you're right. I don't think I've ever caught a `NameError` before. I didn't even think of that. – Carcigenicate Mar 27 '21 at 23:57
  • 2
    Don't use global variables – juanpa.arrivillaga Mar 27 '21 at 23:57
  • @SuperStormer Why are you telling me? – kaya3 Mar 27 '21 at 23:57

1 Answers1

5

Simply avoid globals altogether. They are not necessary here.

def measure_string(myStr):
    if myStr == "":
        return 0
    else:
        return 1 + measure_string(myStr[:-1])
        
measure_string('myStr')
# 5

Edit: If you are interested in black magic you may consider this. But please, figure out yourself why it works.

def measure_string(myStr):
    return ( 
        (not myStr) or
        (2 + measure_string(myStr[:-1])) 
    ) - 1
Durtal
  • 1,063
  • 3
  • 11
  • Thank you! I was wanting to start from the end of the string instead of the beginning for some reason - I now see why that makes so much sense. Instead of incrementing too far and potentially throwing an error, you can just start from the end, which will automatically stop at the first character (I think). So given that this is tail recursion, the adding of 1 is necessary to reflect the removal of one character -- and then that 1 from the deepest recursion is returned to the next layer up? Recursion is by far the most abstract thing I've learned in this class thus far. – ash Mar 28 '21 at 00:20
  • @ash The recursion stops because if there are no characters left, the function will take the if-branch, in which case it wont call itself again. This has nothing to do with from where you delete the character. `return 1 + measure_string(myStr[1:])` is also working. Not sure, but I think it is faster to remove the last character ... for, you know, ... reasons ... – Durtal Mar 28 '21 at 00:32
  • You're right. I was all sorts of wrong. Beginning at the string works perfectly fine. Even if there was a problem with the else branch once string = "", it wouldn't matter because if would kick in instead. Thanks! – ash Mar 28 '21 at 00:44
  • One virtue the question's recursive function has over the recursion in this answer is that it is tail recursive. That doesn't really matter for performance, since the Python interpreter doesn't do tail call elimination, but if you wanted to make a tail recursive function for this problem work without global variables, you could do it by passing the `count` from the original code as an optional argument to the function. – Blckknght Mar 28 '21 at 01:37