Принцип работы рекурсии

@botasa · Регистрация: 18.01.2011

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

Искал в инете и в поиске, но никак не могу понять принцип работы рекурсии программно.
Допустим есть функция

C++
1
2
3
4
int f(int n) {
   if(0 == n) return 0;
   else return n % 10 + f(n / 10);
}

если переделать данную функцию

C++
1
2
3
4
5
6
7
static int i;
int f(int n) {
   i = n;
   cout << i << endl;
   if(0 == n) return 0;
   else return n % 10 + f(n / 10);
}

и вызвать ее f(100500);

то результат в консоли будет
100500
10050
1005
100
10
1
0
6 - конечный результат в точке вызова. То есть данная рекурсивная функция подсчитает суму цифр в числе. НО как именно оно работает я не понимаю при передачи xxx + f(n / 10) тут понятно, почему дальше будет вот такой результат :
100500
10050
1005
100
10
1

НО тут не понятно как работает n % 10 в этой функции и куда оно это все присваивает, что в конце будет цифра 6. И тоже самое в Фибоначчи return f(n - 1) + f(n - 2). Тут не понятно, что сперва вызовет f(n - 1) или f(n - 2), наверно на 2 части разобьется, как ТРЕУГОЛЬНИК в инете видел, но КАК оно потом это все в кучку слепит и в конце даст один результат, то же самое и из ФАКТОРИАЛОМ n * f(n - 1), f(n - 1) - это будет постоянно вызывать а когда и как оно будет на n эти вызовы перемножать ????

То что оно постоянно уходит в глубину и ест много ресурсов понятно, и когда достигнет определенного момента проверки, при которой даст FALSE тоже понятно, но как оно вернет назад результат умножит и другие действия сделается не понятно !!! Вот например в рекурсивный способ решения задачи на сортировку СЛИЯНИЯМ там вроде 2 рекурсии потом и тоже самое в ХАНОЙСКИХ башнях (в башнях вопше не понятно 1 или 2 или 3 строчка будет сперва и по каких правилах будет вызывать, понятно что сверху в низ, но как оно работает не понятно)

В инете нашел много теории и всякие мат. и другие задачи, но сам ПРИНЦИП работы рекурсии ПРОГРАММНО не увидел

@Kastaneda · 22.09.2012, 20:56

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

но сам ПРИНЦИП работы рекурсии ПРОГРАММНО не увидел

Вот тут я когда то давно попытался объяснить. Написано не очень грамотно, но вроде понятно

@botasa · 22.09.2012, 23:54 **[ТС]**

спасибо, пошел читать, если что я сюда отпишу !

Добавлено через 2 часа 38 минут
Почитал я ваши посты, но так и не в курил.

я вот пробую разобраться на самом простом :

int f(int i)
{
if(i <= 1) return 1;
else return i * f(i - 1);
}
f(3);
то
i = 3;
i = 2;
i = 1;
и обратно.
но я так понимаю что при запуску i = 3, тогда потом f(i - 1), тогда i = 2 и т.д. потом обратно и начиная из с 1, оно начинает множить 1, потом на 2, потом на 3 и финал или как ??? или как то по другом ??? ну такой результат сверху мне показал debuger в

Добавлено через 2 минуты
Почитал я ваши посты, но так и не в курил.

я вот пробую разобраться на самом простом :

int f(int i)
{
if(i <= 1) return 1;
else return i * f(i - 1);
}
f(3);
то
i = 3;
i = 2;
i = 1;
и обратно.
но я так понимаю что при запуску i = 3, тогда потом f(i - 1), тогда i = 2 и т.д. потом обратно и начиная из с 1, оно начинает множить 1, потом на 2, потом на 3 и финал или как ??? или как то по другом ??? ну такой результат сверху мне показал debuger в IDE. Но если сделать 10 + i + f(i - 1) при f(3), тогда результат будет 46, то есть ЧИСЛО 10 будет 4 раза вызываться, а сама рекурсия показывает 3 вызова ...

Добавлено через 3 минуты
но если 10 * i + f(i - 1) при f(3) результат будет 600, уже 3 итерации ... при умножении и при додавание оно отличатся в 1 такт

@I.M. · 23.09.2012, 00:10

C++
1
2
3
4
5
int f(int i)
{
   if(i <= 1)return 1;
   return i+f(i-1);
}

Теперь вызываем f(3)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int f(3)
{
   if(3 <= 1)return 1;//false
   return 3+f(2);//вызывается f(2), а f(3) ждет, когда она доработает. Т.е. f(3) будет висеть в памяти
   //когда f(2) вернет результат, то к нему добавится 3. f(3) вернет эту сумму и закончит работать
}
 
int f(2)
{
   if(2 <= 1)return 1;//false
   return 2+f(1);//вызывается f(1), а f(2) ждет, когда она доработает. Т.е. f(2) будет висеть в памяти
   //когда f(1) вернет результат, то к нему добавится 2. f(2) вернет эту сумму и закончит работать
 
}
 
int f(1)
{
   if(1 <= 1)return 1;//true - выход из рекурсии
   return 2+f(0);//уже не выполнится
 
}

Таким образом, последовательность такая:
f(3) начинает работать
f(2) начинает работать
f(1) начинает работать
f(1) заканчивает работать
f(2) заканчивает работать
f(3) заканчивает работать

@OhMyGodSoLong · 23.09.2012, 00:33

Насколько же с моделью подстановки всё проще объясняется...

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@botasa 3 / 3 / 5 Регистрация: 18.01.2011 Сообщений: 131
	22.09.2012, 23:54 [ТС]
	спасибо, пошел читать, если что я сюда отпишу ! Добавлено через 2 часа 38 минут Почитал я ваши посты, но так и не в курил. я вот пробую разобраться на самом простом : int f(int i) { if(i <= 1) return 1; else return i * f(i - 1); } f(3); то i = 3; i = 2; i = 1; и обратно. но я так понимаю что при запуску i = 3, тогда потом f(i - 1), тогда i = 2 и т.д. потом обратно и начиная из с 1, оно начинает множить 1, потом на 2, потом на 3 и финал или как ??? или как то по другом ??? ну такой результат сверху мне показал debuger в Добавлено через 2 минуты Почитал я ваши посты, но так и не в курил. я вот пробую разобраться на самом простом : int f(int i) { if(i <= 1) return 1; else return i * f(i - 1); } f(3); то i = 3; i = 2; i = 1; и обратно. но я так понимаю что при запуску i = 3, тогда потом f(i - 1), тогда i = 2 и т.д. потом обратно и начиная из с 1, оно начинает множить 1, потом на 2, потом на 3 и финал или как ??? или как то по другом ??? ну такой результат сверху мне показал debuger в IDE. Но если сделать 10 + i + f(i - 1) при f(3), тогда результат будет 46, то есть ЧИСЛО 10 будет 4 раза вызываться, а сама рекурсия показывает 3 вызова ... Добавлено через 3 минуты но если 10 * i + f(i - 1) при f(3) результат будет 600, уже 3 итерации ... при умножении и при додавание оно отличатся в 1 такт 0

@OhMyGodSoLong ~ Эврика! ~ 1258 / 1007 / 74 Регистрация: 24.07.2012 Сообщений: 2,002
	23.09.2012, 00:33
	Насколько же с моделью подстановки всё проще объясняется... 0