Рекурсия и проблема с Python

Question

Я пытался понять рекурсию. Но я не думаю, что у меня все получилось.

Здесь контур для моего кода:

def f(): 

    used = [anything] 
    new = [] 

    while i < something: 
     new.append(i) 
     i += 1 

    for i in new: 
     if i in used: 
      f() 
     else: 
      return new 

Теперь, я не думаю, что я могу использовать это, потому что я не перебор и нет базового варианта. Мне нужно продолжать эту программу, пока я не получу набор значений (выбранных случайным образом), которые не используются. Какой был бы лучший способ достичь этого? Создать еще одну функцию?

Любая помощь будет принята с благодарностью.

Спасибо!

Answer 1

Вы должны добавить параметры функции и перенести правильный параметр на рекурсивные вызовы функций.

Например:

def f(new, used, i): 

Answer 2

Я думаю, что правильный в то время как петля будет решить эту проблему более здраво, чем рекурсивный вызов. Я не совсем понимаю, что вы пытаетесь достичь с помощью этого кода, но здесь он переписывается с тропами:

def f(used): 

    new = [] 

    while len(new) == 0 : 
     while i < something: 
      new.append(i) 
      i += 1 

     for i in new: 
      if i in used: 
       new = [] 
       break 

    return new 

Answer 3

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

f(x): 
    x-=1 
    if x < 5: 
     return x 
    else: 
     f(x) 

Точка рекурсии - это вызов функции внутри себя с помощью нового параметра. x каждый раз меняет значение, поэтому в конце концов, если оно опустится ниже 5 и вы вернете x (это будет 4). Таким образом, это будет f (7), вычесть 1, f (6), вычесть 1, f (5), вычесть 1, f (4), вернуть 4.

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

Answer 4

Я думаю, что пример, на котором вы фокусируетесь, является плохим примером рекурсии. Почти легко увидеть итерационное решение вашей проблемы. С отличным примером рекурсии трудно увидеть любое другое решение, чем рекурсивное решение.

Одним из классических примеров рекурсии является навигационная структура данных, ориентированная на дерево.

Вот простой пример (вряд ли испытания ...):

#!/usr/bin/python 

tree = {'text': '1', 
     'brnch': [{ 
        'text': '1.1', 
        'brnch': [{ 
          'text': '1.1.1', 
          'brnch': [{ 
             'text': '1.1.1.1', 
             'brnch': []}]}, 
          {'text': '1.1.2', 
          'brnch': []}, 
          {'text': '1.1.3', 
          'brnch': []}]}, 
       {'text': '1.2', 
        'brnch': []}]} 

def recurse_traverse(tree): 
    print ' ' * recurse_traverse.level + tree['text'] 
    for branch in tree['brnch']: 
     recurse_traverse.level += 1 
     recurse_traverse(branch) 
     recurse_traverse.level -= 1 

if __name__ == '__main__': 
    import os 
    print "testing", os.path.abspath(__file__) 
    recurse_traverse.level = 1 
    recurse_traverse(tree) 

Мелкая онлайн книга Think Like a Computer Scientist имеет больше примеров recursion.

Answer 5

Если я правильно понял, вы запрашиваете рекурсивную функцию для создания списка псевдослучайных значений, которые не включены в другой список. Эта рекурсивная функция будет генерировать size число псевдослучайных значений, которых нет в used.

from sets import Set 
import random 

used = Set([1,2,3,4,5]) 

def f(new, size): 
    # Check if we have enough 'new' values that are not in the 'used' set 
    if len(new.difference(used)) < size: 
    new.add(random.randint(0,100)) # Generate a pseudo-random value and 
            # add it to the 'new' set 
            # Values are between 0-100 inclusive 
            # but you can change that to whatever you like 
    new = f(new, size) # Append our results to `new`, this will get the result set 
    return new.difference(used) # Return only the different 
           # values between the two sets 

result = f(Set(), 10) # Start with a blank set and a request for a result with 10 values 
print(result)