Вычислить количество элементов списка с использованием рекурсивной функции

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

0

2

2

Сообщение от Catstail return 1+size_list(a[1:])

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

0

Сообщение от ujif там же в стек все время попадает единица , которая плюсуется с чем..

- при чем тут стек? Возвращается единица плюс результат вызова на укороченном списке.

Цепочка возвратов будет такая:

size_list([11,22,33]) -> 1+ size_list([22,33]) -> 1+1+size_list([33]) -> 1+1+1+size_list([]) -> 1+1+1+0 = 3

2

Сообщение от ujif как эта сумма работает, там же в стек все время попадает единица , которая плюсуется с чем..

с тем, что возвращает функция... из стека
А возвращает она сумму, формирующуюся на каждом шаге вызова, примерно так:
Допустим, у нас список из четырех элементов ['a','b','c','d'], тогда в стеке будут сформированы четыре ящичка-функции. Формирование этих ящичков-функций происходит до тех пор, пока длина списка, посредством срезов (на каждом шаге она уменьшается), не станет равна нулю:
1 + fun(a[1:])
1 + fun(a[1:])
1 + fun(a[1:])
1 + fun(a[1:])
здесь следует возврат 0, т.к. список закончился и сработал условный блок. Далее следует разбор стека (по принципу LIFO) в обратном порядке (ибо в каждое место вызова следует возвращаться, но уже с конкретным результатом):
return 1 + 0
return 1 + 1
return 1 + 2
return 1 + 3
- и вот тут происходит возврат в место первичного вызова функции, со значением той самой суммы которую хотели получить.

Добавлено через 44 секунды

Сообщение от Catstail - при чем тут стек?

Человек хочет понять, как устроена рекурсия в питон

Сообщение от Catstail Цепочка возвратов будет такая

не очень наглядно... когда впервые столкнулся с подобным объяснением, долго не втыкал: "а чего здесь происходит-то?"
Нагляднее показать через рекурсивную функцию факториала:
а далее происходит вызов без вычислений, пока не вернется последний вызов с конкретным числом, например, func(4) с номерами вызовов функции:
1. func(4)
2. 4 * func(3)
3. 4 * 3 * func(2)
4. 4 * 3 * 2 * func(1)
- и теперь пошли возвраты, но теперь уже с вычислениями:
4. 4 * 3 * 2 * 1
3. 4 * 3 * 2
2. 4 * 6
1. 24
- получен результат.

1

Сообщение от YuS_2 Нагляднее показать через рекурсивную функцию факториала:

- то же самое...

1

Сообщение от YuS_2 получен результат

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

0

Сообщение от ujif то она уже напрямую имеет отношение к списку

кто она? переменная х? она вообще ни к чему не имеет отношения так как не объявлена а так будет считаться сумма

2

ujif, посмотри прилагаемую презентацию:

Вложения

РЕКУРСИЯ.zip (224.6 Кб, 12 просмотров)

2

Сообщение от Catstail - то же самое...

это да, для тех кто понимает уже как работает алгоритм. Но для неподготовленного новичка, проще понять, имхо...

Сообщение от Catstail посмотри прилагаемую презентацию

эдак, мозги могут съехать, там же не питон... запутается страждущий знаний.

Сообщение от ujif и тогда единицы друг с другом складываются

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

Сообщение от ujif но если вместо единицы, например подставить переменную из списка lst

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

Добавлено через 7 минут
ujif, да, я там объясняя, чуток ошибся. Вызовы функции:

Сообщение от YuS_2 func(4)

должны быть такими в пояснениях: fact(4)

1

Сообщение от Semen-Semenich а так будет считаться сумма

да, ошибся, вместо lst[0] написал x[0]

0

Сообщение от YuS_2 там же не питон...

- реализация рекурсии от языка не зависит

0

Сообщение от Catstail реализация рекурсии от языка не зависит

Да-да... это понятно...
Только вот, чтобы понять, что такое רקורסיה , необходимо сначала прочитать буквы, как минимум

0

Сообщение от YuS_2 буквы, как минимум

еще и знать, с какой стороны начинать читать )

0