Рекурсивная функция с возможностью заблокировать ввод некоторых параметров

@Goainwo · Регистрация: 18.10.2018

Author24 — интернет-сервис помощи студентам

Здравствуйте. Нужно что-то типа этого сделать:

Python

def my_range(start, stop, step=1, _now = None, _result = []):
    if step == 0:
        return float("inf")
    if _now is None:
        _now = start
    if step > 0:
        if start >= stop:
            return _result
    if step < 0:
        if start <= stop:
            return _result
    _result += [_now]
    _now += step
    return my_range(_now, stop, step, _now = _now, _result = _result)

То есть нужно создать рекурсивную функцию, которая возвращает список всех значений от start до stop(не включая stop) с шагом step. Но нужно чтобы параметры _now и _result нельзя было вводить вручную при вызове функции или вовсе отказаться от этих параметров, если возможно. Главное — функция рекурсивная, без циклов, не использует внешние переменные.

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

Тут нужно исправить три основных минуса:
1) она почему-то накапливает предыдущие результаты при повторных вызовах. Я так понимаю дело в том, что _result стала глобальной, потому что я из-за рекурсивного вызова сделал что-то типа замыкания??? Как это исправить? Предложите разные варианты, но с сохранением рекурсии.
При первом вызове и при повторном:

Рекурсивная функция с возможностью заблокировать ввод некоторых параметров

2) Умирает ядро в Anaconda, если вызовов где-то от 1 до 3000 с шагом 1. Если от 1 до 2969 с шагом 1 — выскакивает ошибка.

3) Нужно заблокировать для программиста вызов функции со своими значениями параметров _now и _result. Или вовсе не использовать эти параметры, если возможно. Сейчас же можно самому вводить эти параметры и это ничем не ограничено:

Для решения проблемы №3 я пока что придумал вот такой изврат:

Python

def my_range(start, stop, step=1, *last, _now = None, _result = []):
    if last:
        raise IOError("Недопустимое количество параметров. Функция должна принимать только 3 параметра!")
    if step == 0:
        return float("inf")
    if _now is None:
        _now = start
    if step > 0:
        if start >= stop:
            return _result
    if step < 0:
        if start <= stop:
            return _result
    _result += [_now]
    _now += step
    return my_range(_now, stop, step, _now = _now, _result = _result)

Но, к сожалению, данный изврат не дает возможности неявно принимать значения параметров, а если программист укажет их значения явно, с именем параметра, то программа будет всё равно выполняться.

@megacold · 19.10.2018, 03:14

Наверно как-то так:

Python

import sys
 
sys.setrecursionlimit(100500)
 
def my_range(start, stop, step=1):
    ls = []
    _now = None
    if step == 0:
        return float("inf")
    if _now is None:
        _now = start
    if step > 0:
        if start >= stop:
            return ls
    if step < 0:
        if start <= stop:
            return ls
    ls += [_now]
    _now += step
    
    return ls + my_range(_now, stop, step)
 
print( my_range(1, 400, 1) )
print( my_range(1, 400, 1) )

@Goainwo · 21.10.2018, 12:42 **[ТС]**

Даше с вашим кодом ядро умирает, если:

Python

1	print(my_range(1, 2969))

@ТабуретY · 21.10.2018, 12:53

Какой-то у вас jupiter неправильный, сколько памяти есть?

@megacold · 21.10.2018, 13:07

Тут несколько вариантов:
1. Поставьте нормальный Python (все летает меньше секунды)
2. Перепишите на циклы (если уж такой эстет)
3. Обновите среду в которой выполняете код
Если не помогли эти три пункта:
3. Купите новый компьютер - я тестил 10 000 итераций, на совсем "скромном" железе (2гига, проц Atom 1.8гц) и на Rasppery Pi - все летает, может у вас еще скромнее.

@Goainwo · 21.10.2018, 13:12 **[ТС]**

Сообщение от ТабуретY

Какой-то у вас jupiter неправильный, сколько памяти есть?

Так вы в своём примере только 400 показали. Попробуйте вбить, например 10000 или хотя бы 3000. Слабый ноут, 4Гб ОЗУ. Но я думаю, что это вполне должно бы хватать, чтобы запомнить каких-то 10000 чисел и стек программы. Это могут делать компьютеры двадцатилетней давности, а с 4Гб ОЗУ и подавно. Что-то не так работает, как нужно. Код следует переписывать или настройки не те. Юпитер стандартный, ничего не перенастраивал, всё со стандартной Анаконды. Есть 4Гб оперативной памяти.

Сообщение от megacold

на совсем "скромном" железе (2гига, проц Atom 1.8гц) и на Rasppery Pi - все летает, может у вас еще скромнее.

У меня ноут i3 шестое поколение, 4Гб ОЗУ и видео Radeon M330. Всё обновлено. Windows 10 LTSC (2018 с длительным сроком поддержки). Стоит стандартная Anaconda, без каких-либо дополнительных настроек.

vic5710 · 21.10.2018, 13:36

есть обертка для рекурсии
https://habr.com/post/158385/

Python

class recursion(object):
    "Can call other methods inside..."
    def __init__(self, func):
        self.func = func
 
    def __call__(self, *args, **kwargs):
        result = self.func(*args, **kwargs)
        while callable(result): result = result()
        return result
 
    def call(self, *args, **kwargs):
        return lambda: self.func(*args, **kwargs)
 
 
@recursion
def sum_natural(x, result=0):
    if x == 0:
        return result
    else:
        return sum_natural.call(x - 1, result + x)
 
# Даже такой вызов не заканчивается исключением
# RuntimeError: maximum recursion depth exceeded
print(sum_natural(1000000))

@ТабуретY · 21.10.2018, 13:36

Сообщение от Goainwo

Так вы в своём примере только 400 показали.

На 5220 StackOverflow, все равно рано у вас падает для такого железа

@megacold · 21.10.2018, 13:37

Каюсь, моя черепашка осилила:

Python

import sys
from timeit import default_timer as timer
 
sys.setrecursionlimit(100500)
 
def my_range(start, stop, step=1):
    ls = []
    _now = None
    if step == 0:
        return float("inf")
    if _now is None:
        _now = start
    if step > 0:
        if start >= stop:
            return ls
    if step < 0:
        if start <= stop:
            return ls
    ls += [_now]
    _now += step
    
    return ls + my_range(_now, stop, step)
 
start_time = timer() 
print( my_range(1, 6300) )
print("Время выполнения: {:g} сек.".format(timer() - start_time))
 
[B]Время выполнения: 3.7591 сек.[/B]

@Goainwo · 21.10.2018, 14:30 **[ТС]**

Сообщение от ТабуретY

На 5220 StackOverflow, все равно рано у вас падает для такого железа

Python

Python 3.7.1 (v3.7.1:260ec2c36a, Oct 20 2018, 14:05:16) [MSC v.1915 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>> 1 + 1
2
>>> 
================= RESTART: C:\Users\Goainwo\Downloads\111.py =================
Traceback (most recent call last):
  File "C:\Users\Goainwo\Downloads\111.py", line 25, in <module>
    print( my_range(1, 6300) )
  File "C:\Users\Goainwo\Downloads\111.py", line 22, in my_range
    return ls + my_range(_now, stop, step)
  File "C:\Users\Goainwo\Downloads\111.py", line 22, in my_range
    return ls + my_range(_now, stop, step)
  File "C:\Users\Goainwo\Downloads\111.py", line 22, in my_range
    return ls + my_range(_now, stop, step)
  [Previous line repeated 5230 more times]
  File "C:\Users\Goainwo\Downloads\111.py", line 16, in my_range
    if step < 0:
MemoryError: Stack overflow

Добавлено через 4 минуты
Я уже потерялся полностью. То есть на 4Гб оперативной памяти нельзя сделать то, что я хочу? Пробовал на чистом питоне, без анаконды, в IDLE. 5230 (в среднем) и потом Stack overflow (((

Добавлено через 8 минут

Сообщение от vic5710

есть обертка для рекурсии
https://habr.com/post/158385/

Я не могу понять как подстроить это под код:

Python

import sys
from timeit import default_timer as timer
 
sys.setrecursionlimit(100500)
 
def my_range(start, stop, step=1):
    ls = []
    _now = None
    if step == 0:
        return float("inf")
    if _now is None:
        _now = start
    if step > 0:
        if start >= stop:
            return ls
    if step < 0:
        if start <= stop:
            return ls
    ls += [_now]
    _now += step
    
    return ls + my_range(_now, stop, step)

Добавлено через 5 минут

Сообщение от vic5710

есть обертка для рекурсии
https://habr.com/post/158385/

Я понял, что эта обертка просто не годиться для данной функции, не универсальна. Получается, что нужно саму функцию переписывать, а это уже огромный минус обертки... То есть без циклов конкретно данную задачу в рекурсии нельзя выполнить, так как всегда будет переполнение стека... А эти обертки они рекурсию превращают по сути в тот же цикл, причем работают не всегда и требуют переписывания функции, потому что там получится, что мы к списку добавляем функцию...

vic5710 · 21.10.2018, 14:43

судя по описанию нужно добавить call в рекурсию, но глубоко я не вникал

Python

1 2	#return my_range(_now, stop, step, _now = _now, _result = _result) return my_range.call(_now, stop, step, _now = _now, _result = _result)

@Goainwo · 21.10.2018, 14:59 **[ТС]**

Сообщение от vic5710

судя по описанию нужно добавить call в рекурсию, но глубоко я не вникал

Это работает, если мы возвращаем функцию, но если мы конкатенируем, то не сработает.
Вот так не будет работать:

Python

import sys
 
sys.setrecursionlimit(100500)
 
class recursion(object):
    "Can call other methods inside..."
    def __init__(self, func):
        self.func = func
 
    def __call__(self, *args, **kwargs):
        result = self.func(*args, **kwargs)
        while callable(result): result = result()
        return result
 
    def call(self, *args, **kwargs):
        return lambda: self.func(*args, **kwargs)
 
@recursion
def my_range(start, stop, step=1):
    ls = []
    _now = None
    if step == 0:
        return float("inf")
    if _now is None:
        _now = start
    if step > 0:
        if start >= stop:
            return ls
    if step < 0:
        if start <= stop:
            return ls
    ls += [_now]
    _now += step
    return ls + my_range.call(_now, stop, step)
 
my_range(1, 100)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-2-3d4c74b29f81> in <module>()
     34     return ls + my_range.call(_now, stop, step)
     35 
---> 36 my_range(1, 100)
 
<ipython-input-2-3d4c74b29f81> in __call__(self, *args, **kwargs)
      9 
     10     def __call__(self, *args, **kwargs):
---> 11         result = self.func(*args, **kwargs)
     12         while callable(result): result = result()
     13         return result
 
<ipython-input-2-3d4c74b29f81> in my_range(start, stop, step)
     32     ls += [_now]
     33     _now += step
---> 34     return ls + my_range.call(_now, stop, step)
     35 
     36 my_range(1, 100)
 
TypeError: can only concatenate list (not "function") to list

vic5710 · 21.10.2018, 15:36

в таком случае конечно нет
типа так надо

Python

@recursion
def f(n, ls=[]):
    if not n:
        return ls
    ls.append(n)
    return f.call(n - 1, ls)
 
n = f(10000)
print(n)

Добавлено через 5 минут
или так

Python

@recursion
def f(n, ls=[]):
    if not n:
        return ls
    return f.call(n - 1, ls + [n])

@Goainwo · 21.10.2018, 15:37 **[ТС]**

Сообщение от vic5710

в таком случае конечно нет
типа так надо

Вы сами попробуйте свой код запустить. Если дважды вызывать функцию, то она копит результаты, наверное из-за того, что ls стал глобальным, а не локальный...

vic5710 · 21.10.2018, 15:41

Сообщение от Goainwo

Вы сами попробуйте свой код запустит

УМВР

Python

@recursion
def f(n, ls=[]):
    if not n:
        return ls
    return f.call(n - 1, ls + [n])
 
n = f(10000)
print(len(n),n[0],n[-1])

Bash

1	10000 10000 1

@Goainwo · 21.10.2018, 15:51 **[ТС]**

Я так сделал, так вроде работает хоть на миллионе:

Python

class recursion(object):
    "Can call other methods inside..."
    def __init__(self, func):
        self.func = func
 
    def __call__(self, *args, **kwargs):
        result = self.func(*args, **kwargs)
        while callable(result): result = result()
        return result
 
    def call(self, *args, **kwargs):
        return lambda: self.func(*args, **kwargs)
 
@recursion
def f(n, ls=[]):
    if not n:
        return ls
    ls_copy = ls + [n]
    return f.call(n - 1, ls_copy[:])

Сейчас все эти идеи в одну попробую скомпилировать, чтобы получить что-то работающее.

Добавлено через 1 минуту

Сообщение от vic5710

УМВР

Конечно теперь у вас работает, потому что вы исправили ошибку. Я говорил про то сообщение, которые вы отослали ранее. Потом вы его отредактировали и добавили рабочий код ))

Добавлено через 6 минут
Вот что я получил в конечном итоге. Если это как-то можно оптимизировать — предложите вариантов (ну кроме как переписать на циклы). Я пока ухожу, но потом сам посмотрю что да как. Видно я что-то лишнего совсем тут наделал, но работает ))

Python

class recursion(object):
    "Can call other methods inside..."
    def __init__(self, func):
        self.func = func
 
    def __call__(self, *args, **kwargs):
        result = self.func(*args, **kwargs)
        while callable(result): result = result()
        return result
 
    def call(self, *args, **kwargs):
        return lambda: self.func(*args, **kwargs)
 
@recursion
def my_range(start, stop, step=1, *last, _now = None, _result = []):
    if last:
        raise IOError("Недопустимое количество параметров. Функция должна принимать только 3 параметра!")
    if step == 0:
        return float("inf")
    if _now is None:
        _now = start
    if step > 0:
        if start >= stop:
            return _result[:]
    if step < 0:
        if start <= stop:
            return _result[:]
    _result_copy = _result[:]
    _result_copy += [_now]
    _now += step
    return my_range.call(_now, stop, step, _now = _now, _result = _result_copy)

vic5710 · 21.10.2018, 15:52

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

Python

@recursion
def f(n, ls=[]):
    if not n:
        return ls
    print(ls) # trace
    return f.call(n - 1, ls + [n])
 
n = f(10)

Bash

[]
[10]
[10, 9]
[10, 9, 8]
[10, 9, 8, 7]
[10, 9, 8, 7, 6]
[10, 9, 8, 7, 6, 5]
[10, 9, 8, 7, 6, 5, 4]
[10, 9, 8, 7, 6, 5, 4, 3]
[10, 9, 8, 7, 6, 5, 4, 3, 2]

@Garry Galler · 21.10.2018, 18:12

Сообщение от Goainwo

Главное — функция рекурсивная, без циклов, не использует внешние переменные

Рекурсия зло, если применять ее не по делу. В вашей задаче это именно так.
Простой while c yield создаст генератор на бесконечное число вызовов, который будет расходовать мизерный размер ОЗУ и тем более стека.

Можно, конечно, и генератор засунуть в рекурсию:

Python

def rec_gen_range(start,stop=None,step=1): 
    if stop is None:
        stop = start
        start = 0
    
    if (
        (step > 0 and start < stop) or 
        (step < 0 and start > stop)
        ): 
        yield start
        yield from rec_gen_range(
                start + step,
                stop,
                step
            )
 
for i in rec_gen_range(1,10000,1):
    print(i)

И это даже даст возможность выполнить (лимит рекурсии нужно будет все равно переустановить) порядка 10000 вызовов без ~~MemoryOverflow~~StackOverflow, но не вижу никакого практического смысла это делать.
Скажите вашему преподавателю, что в python нет оптимизации хвостовой рекурсии (Гвидо посчитал, что без этого вполне можно жить - то есть сразу писать итеративный код), поэтому нет никакого смысла использовать рекурсию нигде, кроме обхода древовидных структур.

@Goainwo · 21.10.2018, 23:38 **[ТС]**

Garry Galler,

Сообщение от Garry Galler

Скажите вашему преподавателю, что в python нет оптимизации хвостовой рекурсии

У меня нет преподавателя. Мне 24 и я изучаю всё это самостоятельно, для себя, а не для оценки. Хочу сам разобраться как и что работает.
Рекурсию я просто люблю, так как еще когда-то давно решал много мелких задачек на LISP, и просто влюбился в рекурсию. Думал тут это будет тоже работать хорошо и быстро, а оказалось всё сложнее.

@Garry Galler · 22.10.2018, 00:06

Сообщение от Goainwo

Думал тут это будет тоже работать хорошо и быстр

Нет. Все будет очень медленно работать. Рекурсия - жуткий тормоз для программы.
Возможно, в ЛИСПЕ это не так, но это значит, что там есть оптимизация ХР, а это, в свою очередь, значит, что хвостовые рекурсивные вызовы просто транслируются в итеративные компилятором.

@ТабуретY 1291 / 908 / 479 Регистрация: 05.12.2013 Сообщений: 3,073
	21.10.2018, 12:53	4
	Какой-то у вас jupiter неправильный, сколько памяти есть? Миниатюры 0

@megacold 24 / 19 / 6 Регистрация: 10.11.2016 Сообщений: 51
	21.10.2018, 13:07	5
	Тут несколько вариантов: 1. Поставьте нормальный Python (все летает меньше секунды) 2. Перепишите на циклы (если уж такой эстет) 3. Обновите среду в которой выполняете код Если не помогли эти три пункта: 3. Купите новый компьютер - я тестил 10 000 итераций, на совсем "скромном" железе (2гига, проц Atom 1.8гц) и на Rasppery Pi - все летает, может у вас еще скромнее. 0

@Goainwo 0 / 0 / 0 Регистрация: 18.10.2018 Сообщений: 9
	21.10.2018, 13:12 [ТС]	6
	Сообщение от ТабуретY Какой-то у вас jupiter неправильный, сколько памяти есть? Так вы в своём примере только 400 показали. Попробуйте вбить, например 10000 или хотя бы 3000. Слабый ноут, 4Гб ОЗУ. Но я думаю, что это вполне должно бы хватать, чтобы запомнить каких-то 10000 чисел и стек программы. Это могут делать компьютеры двадцатилетней давности, а с 4Гб ОЗУ и подавно. Что-то не так работает, как нужно. Код следует переписывать или настройки не те. Юпитер стандартный, ничего не перенастраивал, всё со стандартной Анаконды. Есть 4Гб оперативной памяти. Сообщение от megacold на совсем "скромном" железе (2гига, проц Atom 1.8гц) и на Rasppery Pi - все летает, может у вас еще скромнее. У меня ноут i3 шестое поколение, 4Гб ОЗУ и видео Radeon M330. Всё обновлено. Windows 10 LTSC (2018 с длительным сроком поддержки). Стоит стандартная Anaconda, без каких-либо дополнительных настроек. 0

@ТабуретY 1291 / 908 / 479 Регистрация: 05.12.2013 Сообщений: 3,073
	21.10.2018, 13:36	8
	Сообщение от Goainwo Так вы в своём примере только 400 показали. На 5220 StackOverflow, все равно рано у вас падает для такого железа 0

@Goainwo 0 / 0 / 0 Регистрация: 18.10.2018 Сообщений: 9
	21.10.2018, 15:37 [ТС]	14
	Сообщение от vic5710 в таком случае конечно нет типа так надо Вы сами попробуйте свой код запустить. Если дважды вызывать функцию, то она копит результаты, наверное из-за того, что ls стал глобальным, а не локальный... 0

@Goainwo 0 / 0 / 0 Регистрация: 18.10.2018 Сообщений: 9
	21.10.2018, 23:38 [ТС]	19
	Garry Galler, Сообщение от Garry Galler Скажите вашему преподавателю, что в python нет оптимизации хвостовой рекурсии У меня нет преподавателя. Мне 24 и я изучаю всё это самостоятельно, для себя, а не для оценки. Хочу сам разобраться как и что работает. Рекурсию я просто люблю, так как еще когда-то давно решал много мелких задачек на LISP, и просто влюбился в рекурсию. Думал тут это будет тоже работать хорошо и быстро, а оказалось всё сложнее. 0

@Garry Galler 5418 / 3842 / 1214 Регистрация: 28.10.2013 Сообщений: 9,554 Записей в блоге: 1
	22.10.2018, 00:06	20
	Сообщение от Goainwo Думал тут это будет тоже работать хорошо и быстр Нет. Все будет очень медленно работать. Рекурсия - жуткий тормоз для программы. Возможно, в ЛИСПЕ это не так, но это значит, что там есть оптимизация ХР, а это, в свою очередь, значит, что хвостовые рекурсивные вызовы просто транслируются в итеративные компилятором. 0