Блог

Главная - Вопросы по программированию - Альтернатива len() с использованием рекурсии в python

Альтернатива len() с использованием рекурсии в python

#python

#python

Вопрос:

Как часть проблемы для CS1301, я пытаюсь написать функцию с использованием рекурсии, которая будет выполнять то же самое, что и len() . Однако у меня есть две проблемы:

  1. Я использую глобальные переменные, где я еще не изучил это в курсе.
  2. Автоградер cs1301 сообщает мне, что моя функция возвращает 26 вместо 13 (хотя, когда я ее запускаю, она выводит 13). Не уверен, имеет ли это какое-то отношение к назначению глобальной переменной.

Rest не требует пояснений, как в приведенном ниже коде:

 #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"))

Комментарии:

1. Да, это, вероятно, из-за глобальных переменных. Вам нужно будет сбрасывать их перед каждым начальным вызовом. По таким причинам вам следует избегать глобальных значений. Глобальные состояния имеют тенденцию кусать вас. Кроме того, почему вы используете try here? Я не вижу кода в try ever throwing, поэтому он не служит цели.

2. @Carcigenicate return count 1 завершится ошибкой, если count он еще не определен; он определен в else ветке, которая, возможно, не была выполнена.

3. Почему эти глобальные переменные в первую очередь? Вы должны передавать их во вложенный вызов в качестве аргумента, а не через глобальные переменные.

4. Подобные задачи меня действительно огорчают. Это ничему не учит, кроме того, как неправильно использовать рекурсию. Пожалуйста, никогда не используйте global и (почти) никогда не используйте рекурсию. Рекурсия подходит для задач, которые имеют ветвление и уменьшают пространство поиска лучше, чем линейные, такие как разделяй и властвуй. Если вам нужно использовать рекурсию, вы можете найти длину строки, используя индекс, вместо того, чтобы копировать всю строку при каждом вызове с квадратичным фрагментом.

5. Не используйте глобальные переменные

Ответ №1:

Просто избегайте глобалов вообще. Здесь они не нужны.

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

Редактировать:
Если вы заинтересованы в черной магии, вы можете рассмотреть это. Но, пожалуйста, выясните сами, почему это работает.

 def measure_string(myStr):
    return ( 
        (not myStr) or
        (2   measure_string(myStr[:-1])) 
    ) - 1

Комментарии:

1. Спасибо! По какой-то причине я хотел начать с конца строки вместо начала — теперь я понимаю, почему это имеет такой смысл. Вместо того, чтобы увеличивать слишком далеко и потенциально выдавать ошибку, вы можете просто начать с конца, который автоматически остановится на первом символе (я думаю). Итак, учитывая, что это хвостовая рекурсия, добавление 1 необходимо для отражения удаления одного символа, а затем 1 из самой глубокой рекурсии возвращается на следующий уровень вверх? Рекурсия, безусловно, самая абстрактная вещь, которую я изучил в этом классе до сих пор.

2. @ash Рекурсия останавливается, потому что, если не осталось символов, функция примет if-ветвь, и в этом случае она не будет вызывать себя снова. Это не имеет ничего общего с тем, откуда вы удаляете символ. return 1 measure_string(myStr[1:]) также работает. Не уверен, но я думаю, что быстрее удалить последний символ … по, вы знаете, … причинам…

3. Вы правы. Я был во всем неправ. Начало в строке работает отлично. Даже если бы возникла проблема с веткой else один раз string = «» , это не имело бы значения, потому что вместо этого сработал бы if . Спасибо!

4. Одним из преимуществ рекурсивной функции вопроса по сравнению с рекурсией в этом ответе является то, что она является хвостовой рекурсией. На самом деле это не имеет значения для производительности, поскольку интерпретатор Python не выполняет устранение хвостового вызова, но если вы хотите заставить хвостовую рекурсивную функцию для этой проблемы работать без глобальных переменных, вы могли бы сделать это, передав count из исходного кода в качестве необязательного аргумента функции.