Какова последовательность выполнения рекурсивной функции?

@maks66 · Регистрация: 22.07.2013

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

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

Python
1
2
3
4
 def f(n):
... if n == 0:
... return 1
... return f(n-1)*n

Глядя, на эту функцию вообще не понятно как она работает. просто последовательно возвращает вызовы(никаких значений не возаращает), как все таки происходит вычисление?

accept · 22.07.2013, 03:10

разбери по шагам для небольшого n

@maks66 · 22.07.2013, 07:57 **[ТС]**

например, при n=4 последовательно возвращаются вызовы:
f(3)*2; f(2)*1, f(1). и как понимают вызов функции умноженный на число?

accept · 22.07.2013, 09:32

Code
1
2
3
f(4) превращается в f(3) * 4 -> f(3) превращается в f(2) * 3 -> f(2) превращается в f(1) * 2 -> f(1) превращается в f(0) * 1 -> f(0) превращается в 1
 
1 возвращается -> (1) * 1 возвращается -> (1 * 1) * 2 возвращается -> (1 * 1 * 2) * 3 возвращается -> (1 * 1 * 2 * 3) * 4 возвращается

Code
1
2
3
4
5
6
7
8
9
10
11
f(4) превращается в f(3) * 4
    f(3) превращается в f(2) * 3
        f(2) превращается в f(1) * 2
            f(1) превращается в f(0) * 1
                f(0) превращается в 1
 
1 возвращается
    (1) * 1 возвращается
        (1 * 1) * 2 возвращается
            (1 * 1 * 2) * 3 возвращается
                (1 * 1 * 2 * 3) * 4 возвращается

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

Python
1
2
3
4
def f(n):
    if n < 2:
        return 1
    return f(n - 1) * n

@maks66 · 22.07.2013, 09:32 **[ТС]**

А откуда операции умножения берутся? (1)*1, (1*1) *2,... По сути после возвращения f(0)*1, функция завершает работу

accept · 22.07.2013, 09:41

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

По сути после возвращения f(0)*1, функция завершает работу

она завершает работу, но только не вся, а та копия, которая вызывалась
и возвращаемое значение передаётся в копию, которая вызывалась до неё
потом она завершается и и возвращаемое значение передаётся в копию, которая вызывалась до неё

первая копия - f(4)
вторая копия - f(3)
третья копия - f(2)
четвёртая копия - f(1)
пятая копия - f(0)

@maks66 · 22.07.2013, 10:57 **[ТС]**

То есть я правильно понимаю: Когда запускается эта функция, сохраняются копии всех пяти вызовов, вычисление которых производится в конце после последнего вызова, а значения они получают от последнего, если f(0) = 1, то f(1) = 1*1, если f(1) = 1, f(2) = 1*2 и т.д.

accept · 22.07.2013, 12:15

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

Когда запускается эта функция, сохраняются копии всех пяти вызовов

каждый вызов создаёт свой набор переменных, все наборы переменных одинаковые, но это независимые друг от друга наборы переменных
первый вызов не может завершиться, пока не завершиться второй вызов, вызванный из него

@helter · 22.07.2013, 14:22

Функцию удобно мыслить как инструкцию, как руководство к действию. Задаём посчитать f(2). Функция говорит: это равно 2 * f(1), но сначала посчитать f(1). Как посчитать f(1)? Это 1 * f(0), а f(0) = 1. И возвращаемся. Таким образом, при выполнении рекурсии получается стек. В питоне глубина рекурсии ограничена и он принципиально не упрощает стек в случае хвостовой рекурсии.

@maks66 · 22.07.2013, 17:25 **[ТС]**

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

первый вызов не может завершиться, пока не завершиться второй вызов, вызванный из него

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

@helter · 22.07.2013, 17:40

Да нет никакой разницы, рекурсия или нет. Пусть надо посчитать
cos 1 + sin sqrt 2
Как будет вычислять? Ему нужно вычислять сумму двух слагаемых. Но слагаемые сами ещё не вычислены. Поэтому сначала вычисляем слагаемые cos 1 и sin sqrt 2. Первое вычисляется сразу. Чтобы вычислить второе, нужно сначала вычислить sqrt 2. Это считается. Подставляем в синус. Подставляем синус и косинус в сумму. Получаем окончательный ответ. Всё это можно нарисовать деревом:

Code
1
2
3
4
5
6
7
 --+--
 |   |
cos sin
 |   |
 1  sqrt
     |
     2

@maks66 · 22.07.2013, 21:55 **[ТС]**

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

@helter · 22.07.2013, 22:45

Да как же они завершили работу? Смотрите в моём примере: чтобы посчитать +, нужно посчитать дерево для первого аргумента и дерево второго аргумента. А только потом завершается +. Рекурсия - то же самое, только иногда в дереве встречается та же самая функция:

Code
1
2
3
4
5
6
7
 f(2)
  |
2 * f(1)
     |
   1 * f(0)
        |
        1

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

accept · 23.07.2013, 03:31

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

в момент последнего вызова все вызовы завершены

наоборот, не завершены
последний вызов завершается и передаёт значение в предпоследний
предпоследний вызов завершается и передаёт значение в предпредпоследний

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

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

значит так заложено в питоне?

это во всех языках так

@maks66 · 23.07.2013, 21:29 **[ТС]**

я попросил бы еще объяснить как происходит обход, рекурсивными вызовами, вложенных структур данных.

Python
1
2
3
4
5
6
7
8
9
def f(L):
y = 0
for x in L: 
if not isinstance(x, list):
y += x 
else:
y += f(x) 
return y
L=[1,[2,[3,4,5],6,[7,8]]

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

accept · 23.07.2013, 21:39

пиши с отступами, они являются аналогом фигурных скобок

@maks66 · 23.07.2013, 22:55 **[ТС]**

Python
1
2
3
4
5
6
7
8
9
10
def f(L):
    y = 0
    for x in L: 
        if not isinstance(x, list):
            y += x 
        else:
            y += f(x) 
    return y
 
L=[1,[2,[3,4,5],6,[7,8]]

accept · 23.07.2013, 23:18

Python
1
2
3
4
5
6
7
8
9
10
11
12
>>> def f(L):
...     y = 0
...     for x in L: 
...         if not isinstance(x, list):
...             y += x 
...         else:
...             y += f(x) 
...     return y
... 
>>> f([1, [2, [3, 4, 5], 6, [7, 8]]])
36
>>>

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

здесь не видно ни условия выхода из рек-х вызовов

выход из каждого вызова происходит в строке с return

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

ни извлечения вложенных структур

подсчёт суммы во вложенном списке происходит в строке с f(x)
после выполнения такого вызова возвращается число

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

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

при каждом вызове создаётся и новый набор переменных, и новый цикл по ним
в каждой копии свой цикл

@helter · 23.07.2013, 23:58

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

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

Чтобы найти сумму всех чисел, имеющихся в списке, нужно:
1. Сумму занулить.
2. Пройти по списку.
3. Если элемент - число, добавить его к сумме.
4. Если элемент - список, добавить к сумме сумму чисел, имеющихся в этом списке.

Инструкция абсолютно прозрачная, разве нет?

Может быть, вам было бы интересно почитать что-нибудь по функциональному программированию: лисп, хаскелл. По понятным причинам там рекурсии уделяется особое внимание.

Новые блоги и статьи Все статьи Все блоги /
Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .

accept 4866 / 3288 / 468 Регистрация: 10.12.2008 Сообщений: 10,570
	22.07.2013, 03:10
	разбери по шагам для небольшого n 0

@maks66 0 / 0 / 0 Регистрация: 22.07.2013 Сообщений: 53
	22.07.2013, 07:57 [ТС]
	например, при n=4 последовательно возвращаются вызовы: f(3)2; f(2)1, f(1). и как понимают вызов функции умноженный на число? 0

@maks66 0 / 0 / 0 Регистрация: 22.07.2013 Сообщений: 53
	22.07.2013, 09:32 [ТС]
	А откуда операции умножения берутся? (1)1, (11) 2,... По сути после возвращения f(0)1, функция завершает работу 0

@maks66 0 / 0 / 0 Регистрация: 22.07.2013 Сообщений: 53
	22.07.2013, 10:57 [ТС]
	То есть я правильно понимаю: Когда запускается эта функция, сохраняются копии всех пяти вызовов, вычисление которых производится в конце после последнего вызова, а значения они получают от последнего, если f(0) = 1, то f(1) = 11, если f(1) = 1, f(2) = 12 и т.д. 0

@helter 4528 / 3522 / 358 Регистрация: 12.03.2013 Сообщений: 6,038
	22.07.2013, 14:22
	Функцию удобно мыслить как инструкцию, как руководство к действию. Задаём посчитать f(2). Функция говорит: это равно 2 * f(1), но сначала посчитать f(1). Как посчитать f(1)? Это 1 * f(0), а f(0) = 1. И возвращаемся. Таким образом, при выполнении рекурсии получается стек. В питоне глубина рекурсии ограничена и он принципиально не упрощает стек в случае хвостовой рекурсии. 1

@maks66 0 / 0 / 0 Регистрация: 22.07.2013 Сообщений: 53
	22.07.2013, 21:55 [ТС]
	если все вызовы завершили работу, почему все таки происходит обратное раскручивание вызовов для нахождения результата, значит так заложено в питоне? 0

accept 4866 / 3288 / 468 Регистрация: 10.12.2008 Сообщений: 10,570
	23.07.2013, 21:39
	пиши с отступами, они являются аналогом фигурных скобок 0