Python-Recursion-New для программирования

Question

Мне нужно проверить, что каждое число в numberList положительно и реализовать нижеследующую функцию с использованием рекурсии. Я застрял. Просто изучая рекурсию, и я полностью потерялся, поскольку я очень новичок в программировании. Помогите!

def isEveryNumberPositiveIn(numberList): 
     foundCounterexampleYet = False 

     for number in numberList: 
      if(number <= 0): 
       foundCounterexampleYet = True 
       return not(foundCounterexampleYet) 

Answer 1

Ваших отступы неправильно, но ваше мышление является правильным, хотя алгоритм не является рекурсивным. Вы могли бы сделать его немного более эффективным, хотя, выпрыгнув из цикла, когда отрицательное число обнаружено:

def isEveryNumberPositiveIn(numberList): 
    foundCounterexampleYet = False 
    for number in numberList: 
     if number <= 0: 
      foundCounterexampleYet = True 
      break 
    return not foundCounterexampleYet 

затем, например:

a = [1,-2,3,4,45] 
print(isEveryNumberPositiveIn(a)) 

возвращается False

Кстати , те скобки для if и not не нужны.

Answer 2

1. Ваша функция не является рекурсивным, так как он никогда не называет себя; рекурсивная версия будет выглядеть

   def all_positive(lst): 
       if lst: 
        return lst[0] > 0 and all_positive(lst[1:]) 
        #      ^
        #    this is the recursive bit - 
        #    the function calls itself 
       else: 
        return True 
        #  this keeps the function from looping forever - 
        #  when it runs out of list items, it stops calling itself 
   

2. Это плохой пример, чтобы выбрать для рекурсивной функции, потому что (а) существует простое нерекурсивно решение и (б) передавая ей большой список (т.е. более 1000) переполняет стек вызовов и разбивает вашу программу. Вместо этого попробуйте:

   def all_positive(lst): 
       return all(i > 0 for i in lst) 
   

Answer 3

С такого родом рекурсивных проблем, вот как вы должны думать об этом:

• Там должен быть «основа случай», который отвечает на вопрос тривиальным.

• Должна быть часть, которая делает что-то, что приближает вас к решению.

В этом случае «базовый регистр» будет пустым. Если список пуст, верните True.

Часть, которая приближает вас к решению: сократите список. Как только список будет укорочен вплоть до нулевого (пустого) списка, вы достигли базового варианта.

В псевдокоде:

define function all_positive(lst) 
    # basis case 
    if lst is zero-length: 
     return True 

    if the first item in the list is not positive: 
     return False 

    # the actual recursive call 
    return all_positive(lst[with_first_value_removed] 

Попытка преобразовать выше псевдокод в код Python и получить его работу. Когда вы будете готовы заглянуть в мой ответ, это ниже.

def all_positive(lst): 
    """ 
    Recursive function to find out if all members of lst are positive. 

    Because it is recursive, it must only be used with short lists. 
    """ 
    # basis case 
    if len(lst) == 0: 
     return True 

    if lst[0] <= 0: 
     return False 

    # recursive call 
    return all_positive(lst[1:]) 

Существует несколько способов написать это. Один из способов - использовать lst.pop(), чтобы удалить один элемент из списка. Вы могли бы объединить это с заявлением if, и это было бы изящно. Тогда список уже будет сокращен, и вы можете просто сделать рекурсивный вызов со списком.

if lst.pop() <= 0: 
     return False 

    return all_positive(lst) 

Есть одна проблема: это уничтожает список! Если вызывающий абонент не знает, что он уничтожает список, а вызывающий делает копию списка, это разрушительно. Это просто опасно. Безопаснее делать это так, как я написал выше, где вы используете «сортировку списка», чтобы сделать копию списка, который оставляет первый элемент.

Обычно на языке, таком как Python, мы хотим более безопасную программу, поэтому мы делаем копии вещей, а не разрушаем их («мутируем» их, как мы говорим).

Вот еще одна версия all_positive(), которая делает единственную копию списка, а затем уничтожает эту копию при ее работе. Он опирается на вспомогательную функцию; помощник разрушительный. Мы не ожидаем, что пользователь вызовет вспомогательную функцию напрямую, так что у нее есть имя, которое начинается с подчеркивания.

def _all_positive_helper(lst): 
    """ 
    Recursive function that returns True if all values in a list are positive. 

    Don't call this directly as it destroys its argument; call all_positive() instead. 
    """ 
    if len(lst) == 0: 
     return True 

    if lst.pop() <= 0: 
     return False 

    return _all_positive_helper(lst) 

def all_positive(lst): 
    """ 
    Return True if all members of lst are positive; False otherwise. 
    """ 
    # use "list slicing" to make a copy of the list 
    lst_copy = lst[:] 

    # the copy will be destroyed by the helper but we don't care! 
    return _all_positive_helper(lst_copy) 

В Python фактически можно использовать аргумент по умолчанию для реализации выше всего в одной функции.

def all_positive(lst, _lst_copy=None): 
    """ 
    Return True if all members of lst are positive; False otherwise. 
    """ 
    if _lst_copy is None: 
     return all_positive(lst, lst[:]) 

    if len(_lst_copy) == 0: 
     return True 

    if _lst_copy.pop() <= 0: 
     return False 

    return all_positive(lst, _lst_copy) 

Рекурсия на самом деле не поможет вам в этом. Лучшее использование для рекурсии было бы, например, посещением каждого узла в двоичном дереве.