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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
nail25
0 / 0 / 0
Регистрация: 08.10.2011
Сообщений: 11
#1

нужна помощь с рекурсией. - C++

17.11.2011, 23:47. Просмотров 760. Ответов 9
Метки нет (Все метки)

Ребята, кто мне может объяснить доступно рекурсию на элементарном примере?
в интернетах в основном примеры с факториалом. вроде с ним разобрался.

допустим есть массив 5х10. с элементами от 1-50.
как с помощью рекурсии посчитать сумму каждой строки?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void summ(){}
 
int main(){
int p=1;
    int Mmass[5][10];
    for (int i=0;i<5;i++)
    {
        for (int j=0;j<10;j++)
        {
            Mmass[i][j]=p;
            p++;
            if (Mmass[i][j]<10) {cout<<" ";}
            cout<<Mmass[i][j]<<" ";
        }
    cout<<endl;
    }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
R136a1
142 / 111 / 15
Регистрация: 14.04.2011
Сообщений: 261
18.11.2011, 00:38     нужна помощь с рекурсией. #2
ValeryLaptev довольно подробно изложил про рекурсию.
Рекурсия: вычисление суммы ряда
nail25
0 / 0 / 0
Регистрация: 08.10.2011
Сообщений: 11
18.11.2011, 00:45  [ТС]     нужна помощь с рекурсией. #3
спасибо. прочту.
но подскажите как конкретно в данной задаче сделать выход из рекурсии?

Добавлено через 36 секунд
спасибо. прочту.
но подскажите как конкретно в данной задаче сделать выход из рекурсии?
alkagolik
Заблокирован
18.11.2011, 02:22     нужна помощь с рекурсией. #4
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
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
int summa(int *arr, int m, int sum)
{
    sum += *arr;
    if (m > 1)
        sum = summa(arr + 1, m - 1, sum);
    return sum;
}
 
int main(void)
{
    const int n = 5, m = 10;
    int arr[n][m], sum;
    srand(time(0));
 
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            arr[i][j] = rand() % n;
 
    for (int i = 0; i < n; ++i)
    {
        puts("");
        for (int j = 0; j < m; ++j)
            printf("%d ", arr[i][j]);
    }
 
    for ( int i = 0; i < n; ++i)
    {
        sum = 0;
        sum = summa(arr[i], m, sum);
        printf("\n%2d", sum);
    }
 
    return 0;
}
easybudda
Эксперт С++
9456 / 5469 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
18.11.2011, 02:45     нужна помощь с рекурсией. #5
Цитата Сообщение от alkagolik Посмотреть сообщение
C
1
2
3
4
5
6
7
int summa(int *arr, int m, int sum)
{
    sum += *arr;
    if (m > 1)
        sum = summa(arr + 1, m - 1, sum);
    return sum;
}
Проще надо быть!
C
1
2
3
int rec_sum(const int * arr, size_t size){
    return ( size ) ? *arr + rec_sum(arr + 1, size - 1) : 0;
}
alkagolik
Заблокирован
18.11.2011, 02:50     нужна помощь с рекурсией. #6
да хотел "на пальцах" показать. Да еще и пассажир тут наблюдательный имеется за моими рекурсиями...
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.11.2011, 06:07     нужна помощь с рекурсией. #7
Цитата Сообщение от nail25 Посмотреть сообщение
допустим есть массив 5х10. с элементами от 1-50. как с помощью рекурсии посчитать сумму каждой строки?
Способов много. Можно каждую строку разбить пополам и сложить суммы по половинам, можно откусить один элмент и сложить с суммой остальных, можно на каждом шаге рекурсии складывать не два, а три слагаемых, или сразу четыре. Если комп тянет массиврованный параллелизм (может выполять очень много параллельных ветвей), то лучше всего будет разделдить строку на две равные части, а при нечётной длине - на части, длина которых различается на один элемент, а обе суммы по этим частям считать в отдельных ветвях. В результате получим дерево, на самом нижнем уровне сложится по два соседних элемента.
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
29
30
31
32
33
34
35
36
37
38
39
int summ(int *a, int n)
{
 int *s;
 int *e;
 if (n>2)
 {
  s=a+n/2-1;
  e=a+n-1;
  return summ(a, s-a)+summ(s, e-s);
 }
 *e=a+1;
 return *a+*e;
}
float summ(float *a, int n)
{
 float *s;
 float *e;
 if (n>2)
 {
  s=a+n/2-1;
  e=a+n-1;
  return summ(a, s-a)+summ(s, e-s);
 }
 *e=a+1;
 return *a+*e;
}
double summ(double *a, int n)
{
 double *s;
 double *e;
 if (n>2)
 {
  s=a+n/2-1;
  e=a+n-1;
  return summ(a, s-a)+summ(s, e-s);
 }
 *e=a+1;
 return *a+*e;
}
Можешь по аналогии перегрузить для любого типа.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
18.11.2011, 07:13     нужна помощь с рекурсией. #8
Цитата Сообщение от nail25 Посмотреть сообщение
допустим есть массив 5х10. с элементами от 1-50.
как с помощью рекурсии посчитать сумму каждой строки?
Данная задача не должна решаться при помощи рекурсии. И это самое главное, что ты должен знать о рекурсии.
Рекурсия должна использоваться там, где должна использоваться рекурсия, а не там, где должны использоваться циклы.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.11.2011, 07:18     нужна помощь с рекурсией. #9
Цитата Сообщение от Deviaphan Посмотреть сообщение
Рекурсия должна использоваться там, где должна использоваться рекурсия, а не там, где должны использоваться циклы.
Согласен. Рекурсия должна использоваться только в том случае, если использована в постановке задачи, или если рекурсивны сами данные. Например, все функции, работающие с деревьями должны быть рекурсивными. Но это не озанчает, что рекурсию нельзя писать вместо цикла в качестве наглядного пособия, как делать не надо. Кроме того, если ТС научится применять рекурсию даже там, где она не нужна, он тем болене её напищет там, где она будет нужна.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.11.2011, 07:19     нужна помощь с рекурсией.
Еще ссылки по теме:

C++ find_if, нужна помощь
C++ Нужна помощь с программой
C++ Нужна помощь с ассемблером.
C++ Нужна помощь с комментариями.

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

Или воспользуйтесь поиском по форуму:
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
18.11.2011, 07:19     нужна помощь с рекурсией. #10
Цитата Сообщение от taras atavin Посмотреть сообщение
в качетсве наглядного пособия, как делать не надо
Главное не забыть жирным подписать, что так делать не надо.
Yandex
Объявления
18.11.2011, 07:19     нужна помощь с рекурсией.
Ответ Создать тему
Опции темы

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