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

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

Восстановить пароль Регистрация
 
nail25
0 / 0 / 0
Регистрация: 08.10.2011
Сообщений: 11
17.11.2011, 23:47     нужна помощь с рекурсией. #1
Ребята, кто мне может объяснить доступно рекурсию на элементарном примере?
в интернетах в основном примеры с факториалом. вроде с ним разобрался.

допустим есть массив 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;
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.11.2011, 23:47     нужна помощь с рекурсией.
Посмотрите здесь:

С, нужна помощь C++
C++ Нужна помощь.
C++ Нужна помощь
Нужна помощь C++
C++ Нужна помощь.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
R136a1
 Аватар для 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
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
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
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
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
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
18.11.2011, 02:50     нужна помощь с рекурсией. #6
да хотел "на пальцах" показать. Да еще и пассажир тут наблюдательный имеется за моими рекурсиями...
taras atavin
Ушёл с форума.
 Аватар для 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++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
18.11.2011, 07:13     нужна помощь с рекурсией. #8
Цитата Сообщение от nail25 Посмотреть сообщение
допустим есть массив 5х10. с элементами от 1-50.
как с помощью рекурсии посчитать сумму каждой строки?
Данная задача не должна решаться при помощи рекурсии. И это самое главное, что ты должен знать о рекурсии.
Рекурсия должна использоваться там, где должна использоваться рекурсия, а не там, где должны использоваться циклы.
taras atavin
Ушёл с форума.
 Аватар для 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++ Нужна помощь
Нужна помощь C++
C++ Нужна помощь

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

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

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