Как работает рекурсивная функция

@fire_Rising · Регистрация: 11.05.2016

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

Есть функция вывода бинарного дерева

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Node 
{
   int x;
   Node *l,*r;
};
void show(Node *Tree) 
{
    if (Tree!=NULL)
    {
       show(Tree->l);
       cout<<Tree->x;
       show(Tree->r);
    }
}

Я не могу понять, как show(Tree->l); и show(Tree->r); все выведут. Ведь при вызове допустим show(Tree->l); параметр изменится на Tree->l, далее он проверит пусто ли, если не пусто он опять вызовет show(Tree->l); потом снова и пока до пустого не дойдет и не выйдет из самой void show, до cout даже не дойдет, хотя на практике он как-то перелетает и выводит. Прошу объяснить.

@MansMI · 08.10.2016, 15:22

что непонятного, дойдет до левого дна(пустого), вернется, покажет узел cout<<Tree->x; и пойдет проверять правую ветвь

@fire_Rising · 08.10.2016, 20:43 **[ТС]**

MansMI, при проверке правой ветви снова будет вызываться show(Tree->l) ?

@MansMI · 08.10.2016, 20:47

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

@GbaLog- · 08.10.2016, 20:50

fire_Rising,

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
            9
           / \
          /   \
         7    10
        / \
       1   3
                                                                                         exit()
show(9)                                                     cout(9)                       ↑
    ↓                                                       ↑    ↓                        ↑
    show(7)                                            cout(7)  show(10)    cout(10)      ↑
        ↓                       show(3)     cout(3)    ↑             ↓      ↑     ↓       ↑
        show(1)     cout(1)     ↑    ↓      ↑    ↓     ↑            show(null)    show(null)
            ↓       ↑    ↓      ↑   show(null)  show(null)
            show(null)  show(null)

@fire_Rising · 08.10.2016, 20:55 **[ТС]**

GbaLog-, а как он переходит после cout(1); show(null) к show(3) ? То есть после вывода 1 он проверяет правого потомка у 1 и видит, что его нет, а потом поднимается на 1 наверх и уже у узла(7) проверяет правого потомка и находит его.

@GbaLog- · 08.10.2016, 20:56

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

а как он переходит после cout(1); show(null) к show(3) ? То есть после вывода 1 он проверяет правого потомка у 1 и видит, что его нет, а потом поднимается на 1 наверх и уже у узла(7) проверяет правого потомка и находит его.

Верно.
На рисунке стрелками вверх показаны выходы из функции show(), а стрелками вниз вхождения в эту функцию.

Новые блоги и статьи Все статьи Все блоги /
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. На мобильном - сканируйте QR-код. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .

@MansMI 1617 / 1182 / 553 Регистрация: 08.01.2012 Сообщений: 4,561
	08.10.2016, 15:22
	что непонятного, дойдет до левого дна(пустого), вернется, покажет узел `cout<<Tree->x;` и пойдет проверять правую ветвь 1

@fire_Rising 10 / 11 / 7 Регистрация: 11.05.2016 Сообщений: 113
	08.10.2016, 20:43 [ТС]
	MansMI, при проверке правой ветви снова будет вызываться show(Tree->l) ? 0

@MansMI 1617 / 1182 / 553 Регистрация: 08.01.2012 Сообщений: 4,561
	08.10.2016, 20:47
	будет, но только ниже этой правой без привычки, рекурсию лучше на бумаге разбирать 1

@fire_Rising 10 / 11 / 7 Регистрация: 11.05.2016 Сообщений: 113
	08.10.2016, 20:55 [ТС]
	GbaLog-, а как он переходит после cout(1); show(null) к show(3) ? То есть после вывода 1 он проверяет правого потомка у 1 и видит, что его нет, а потом поднимается на 1 наверх и уже у узла(7) проверяет правого потомка и находит его. 0

Как работает рекурсивная функция

Решение