Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
botasa
3 / 3 / 0
Регистрация: 18.01.2011
Сообщений: 131
22.09.2012, 20:54     Принцип работы рекурсии #1
Искал в инете и в поиске, но никак не могу понять принцип работы рекурсии программно.
Допустим есть функция
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 строчка будет сперва и по каких правилах будет вызывать, понятно что сверху в низ, но как оно работает не понятно)

В инете нашел много теории и всякие мат. и другие задачи, но сам ПРИНЦИП работы рекурсии ПРОГРАММНО не увидел
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.09.2012, 20:54     Принцип работы рекурсии
Посмотрите здесь:

объясните принцип работы цикла : ? C++
объсните принцип работы C++
Принцип работы конструктора C++
Принцип работы switch C++
C++ Принцип работы программы
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
22.09.2012, 20:56     Принцип работы рекурсии #2
Цитата Сообщение от botasa Посмотреть сообщение
но сам ПРИНЦИП работы рекурсии ПРОГРАММНО не увидел
Вот тут я когда то давно попытался объяснить. Написано не очень грамотно, но вроде понятно
botasa
3 / 3 / 0
Регистрация: 18.01.2011
Сообщений: 131
22.09.2012, 23:54  [ТС]     Принцип работы рекурсии #3
спасибо, пошел читать, если что я сюда отпишу !

Добавлено через 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.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
23.09.2012, 00:10     Принцип работы рекурсии #4
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
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
23.09.2012, 00:33     Принцип работы рекурсии #5
Насколько же с моделью подстановки всё проще объясняется...
Yandex
Объявления
23.09.2012, 00:33     Принцип работы рекурсии
Ответ Создать тему
Опции темы

Текущее время: 21:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru