Перетворення цілого числа в рядок з використанням стека (lst_recstack)
Кожен раз, коли викликається toStr. в стек поміщається символ. Повертаючись до попереднього прикладу, ми можемо побачити, що після четвертого виклику toStr стек буде виглядати, як показано на малюнку 5. Зверніть увагу: тепер ми можемо просто виштовхнути символи з стека і об'єднати їх в підсумковий результат "1010".
Малюнок 5: Рядки, поміщені в стек під час перетворення.
Попередній приклад дає нам деяке уявлення про те, як в Python реалізовані рекурсивні виклики. При виконанні функції для управління її локальними змінними виділяється фрейм стека. Значення, що повертається до моменту закінчення роботи функції буде лежати на вершині стека, доступне для викликає частини програми. Малюнок 6 ілюструє стек після оператора return в рядку 4.
Малюнок 6: Стек викликів, згенерований toStr (10, 2).
Зверніть увагу, що виклик toStr (2 // 2, 2) залишає повертається значення "1" в стеці. Потім воно підставляється замість функції toStr (1, 2) в вираз "1" + convertString [2% 2]. яке залишає на вершині стека "10". Таким чином, стек викликів Python працює так само, як і стек, який ми явно використовували в лістингу 4. У нашому суммирующем список прикладі ви можете думати про возвращаемом значенні в стеці, як про акумулюючої змінної.
Також фрейм стека надає область видимості для змінних, використовуваних функцією. Незважаючи на те, що ми знову і знову викликаємо одну і ту ж функцію, кожен виклик створює нову область видимості для її локальних змінних.
Якщо ви добре усвідомите для себе ідею стека, то вам буде набагато легше писати відповідні рекурсивні функції.