Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.82/11: Рейтинг темы: голосов - 11, средняя оценка - 4.82
22 / 19 / 6
Регистрация: 24.12.2012
Сообщений: 435
1

Не понимаю как работает рекурсия

16.03.2015, 21:49. Показов 2064. Ответов 3
Метки нет (Все метки)

Привет. Знаю, что таких тем много (Я читал их). Не нужно кидать ссылки. Я знаю что такое рекурсия, но не понимаю как она работает.
C++
1
2
3
4
5
6
7
8
9
10
int f(int n)
{
    int res;
    if (n == 1)
        res = 1;
    else
        res = f(n-1) * n;
 
    return res;
}
res = f(n-1) * n; Сначала функция f вызывается пока n != 1, при этом наполняется стэк. А потом стэк расскручивается n = 1, 2, 3, 4, ... как то так? Но я все равно до конца не понимаю. Что я только уже не читал (((
0

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

Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.03.2015, 21:49
Ответы с готовыми решениями:

Не понимаю, как работает рекурсия
Добрый день. Не совсем понимаю как работает рекурсия.. Например есть, Function F(n : integer)...

Рекурсия в JavaScript. Не понимаю вообще
Все привет! Не понимаю, как работают рекурсии! Рекурсия - это когда функция вызывает саму себя. Ну,...

Не понимаю, как работает программа
// Programm F 61 // Преобразование Fixed-Float # include stdio.h; # include conio.h; # include...

Я не понимаю как работает padding
http://************/lcre22 Мне нужно убрать эту торчалку. #wrapper { margin:auto; }...

3
2542 / 1201 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
16.03.2015, 22:16 2
Лучший ответ Сообщение было отмечено xSCJx как решение

Решение

Представьте, что вы компилятор.

Возьмите листочек выпишите функцию:
C++
1
2
3
4
5
6
7
8
9
10
int f(int n == 3)
{
    int res;
    if (3 == 1)
        res = 1;
    else
        res = f(3-1) * 3;
 
    return res;
}
Как дойдете до f(3-1) возьмите еще 1 листочек:
C++
1
2
3
4
5
6
7
8
9
10
int f(int n == 2)
{
    int res;
    if (2 == 1)
        res = 1;
    else
        res = f(2-1) * 2;
 
    return res;
}
Так само и еще 1
C++
1
2
3
4
5
6
7
8
9
10
int f(int n == 1)
{
    int res;
    if (1 == 1)
        res = 1;
    else
        res = f(1-1) * 3;
 
    return res;
}
На этом этапе ненадо еще листочков, так как последний код возвращает 1. Тоесть f(1) == 1. Чтобы легче было запомните это как переменная x.
Следовательно выкинув верхний листочек, под ним листочек с кодом
C++
1
2
3
4
5
6
7
8
9
10
int f(int n == 2)
{
    int res;
    if (2 == 1)
        res = 1;
    else
        res = f(2-1) * 2; // где f(1) == 1 и выэто знаете уже
 
    return res;
}
получается f(1) == 1, а f(2) == f(1) *2 == 2;
Выбрасываем листочек идём дальше:
C++
1
2
3
4
5
6
7
8
9
10
int f(int n == 3)
{
    int res;
    if (3 == 1)
        res = 1;
    else
        res = f(3-1) * 3; // f(2) == 2 как мы знаем уже
 
    return res;
}
Следовательно f(3) == f(2) * 3 == ( f(1) * 2) * 3 == 6

и того f(3) вернёт 6, если я трезво читаю код )

Добавлено через 16 минут
Да и для начала понимания рекурсия начните с простого:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;
 
void printNegative(int arr[], int currentIndex, int maxIndex, int wasFounded)
{
    bool isFoundSomething = false; // переменная которая изменится только если мы нашли отрицательное число
    if ( currentIndex > maxIndex ) // смысл рекурсии - объязательно иметь не рекурсивную точку выхода
    {
        cout << "Seach was end." << endl;
    }
    else // сама рекурсия
    {
        if ( arr[currentIndex] < 0 ) // если нашли отрицательное увеличим счётчик вывода на экран на +1 и выведем
        {
            isFoundSomething = true;
            cout << wasFounded + isFoundSomething << ": " << arr[currentIndex] << endl;
        }
        printNegative(arr, currentIndex + 1, maxIndex, wasFounded + isFoundSomething); // продолжим поиск с новыми даными (ключевое слово "новые" )
    }
}
int main()
{
    const int size = 9;
    int arr[size] = { 15, 14, 77, -15, 0, 98, 13, -177, 13 };
 
    printNegative(arr, 0, size - 1, 0); // -1 так как индексация с нуля
 
}
2
839 / 497 / 325
Регистрация: 29.12.2009
Сообщений: 1,106
16.03.2015, 22:25 3
Рекурсия
1
22 / 19 / 6
Регистрация: 24.12.2012
Сообщений: 435
17.03.2015, 00:48  [ТС] 4
спасибо большое за ответы.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.03.2015, 00:48

Не понимаю как работает код
Помогите разобраться в коде , мне дали задание написать программу на питоне , создание 3d фигур...

Не понимаю как работает функция
Прохожу видео уроки и тут появился вопрос как работает функция $function() которую до этого момента...

Не понимаю, как работает код?
int main(int argc, char** argv) //кол-во аргументов, указатель на массив указателей на сами...

Не понимаю,как работает программа
using System; using System.Collections.Generic; using System.Linq; using System.Text; using...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.