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

Простые примеры программ на рекурсию - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 357, средняя оценка - 4.81
antikiler
 Аватар для antikiler
0 / 0 / 0
Регистрация: 26.10.2009
Сообщений: 49
19.02.2010, 16:29     Простые примеры программ на рекурсию #1
Всем привет! У кого есть простые примеры программ на рекурсию, забросьте пожалуйста!!!
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
19.02.2010, 16:44     Простые примеры программ на рекурсию #2
Рекурсивное вычисление факториала:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
 
size_t fact(size_t n)
{
    if(n==0) return 1;
    return n*fact(n-1);
}
 
int main()
{
    std::cout << fact(12) << std::endl;
    return 0;
}
insideone
Модератор
Автор FAQ
 Аватар для insideone
3620 / 898 / 47
Регистрация: 10.01.2010
Сообщений: 2,421
19.02.2010, 16:44     Простые примеры программ на рекурсию #3
Рекурсия факториала
unsigned long Fl(9)
{
if( 9 <= 1 )
return 1;
else
return 9 *
Fl( 9 - 1 )


unsigned long Fl(8)
{
if( 8 <= 1 )
return 1;
else
return 8 *
Fl( 8 - 1 )


unsigned long Fl(7)
{
if( 7 <= 1 )
return 1;
else
return 7 *
Fl( 7 - 1 )


unsigned long Fl(6)
{
if( 6 <= 1 )
return 1;
else
return 6 *
Fl( 6 - 1 )


unsigned long Fl(5)
{
if( 5 <= 1 )
return 1;
else
return 5 *
Fl( 5 - 1 )


unsigned long Fl(4)
{
if( 4 <= 1 )
return 1;
else
return 4 *
Fl( 4 - 1 )


unsigned long Fl(3)
{
if( 3 <= 1 )
return 1;
else
return 3 *
Fl( 3 - 1 )


unsigned long Fl(2)
{
if( 2 <= 1 )
return 1;
else
return 2 *
Fl( 2 - 1 )


unsigned long Fl(1)
{
if( 1 <= 1 )
return 1; // STOP
else
return 1 * Fl( 1 - 1 );
}

;
}

;
}

;
}

;
}

;
}

;
}

;
}

;
}



Но факториал это плохой пример, т.к. факториал можно посчитать и без рекурсии (а рекурсия это не гуд вообще то говоря)
Хороший пример - функция считывания файлов из директории. Если она считывает что в папке есть папка то рекурсивно считывает файлы и из неё и так далее в самую глубину
darkAngel
Технофашист
206 / 187 / 3
Регистрация: 11.03.2009
Сообщений: 829
19.02.2010, 16:45     Простые примеры программ на рекурсию #4
Классический пример - вычисление факториала:
C++
1
2
3
4
5
6
int fac(int n)
{
   if (n==0) return 1;
   n=n*fac(n-1);  //Рекурсия
   return n;
}
Добавлено через 32 секунды
))) ))))))))
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
19.02.2010, 16:47     Простые примеры программ на рекурсию #5
Я первый))
Вычисление n-ного числа Фибоначчи:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
 
size_t fib(size_t n)
{
    if(n==0||n==1) return 1;
    return fib(n-1)+fib(n-2);
}
 
int main()
{
    std::cout << fib(5) << std::endl;
    return 0;
}
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
19.02.2010, 16:49     Простые примеры программ на рекурсию #6
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
 
/* печать числа в двоичном виде */
 
void binPrn(unsigned num){
    if ( num / 2 )
        binPrn(num / 2);
    putchar( num % 2 + '0' );
}
 
int main(void){
    int c;
    
    while ( 1 ){
        printf("Number: ");
        if ( scanf("%d", &c) != 1 || !c )
            break;
        binPrn(c);
        putchar('\n');
    }
    return 0;
}
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
19.02.2010, 16:50     Простые примеры программ на рекурсию #7
insideone, наглядно...
insideone
Модератор
Автор FAQ
 Аватар для insideone
3620 / 898 / 47
Регистрация: 10.01.2010
Сообщений: 2,421
19.02.2010, 17:01     Простые примеры программ на рекурсию #8
Цитата Сообщение от Nameless One
insideone, наглядно...
Мне даже стало интересно до какой вложенности можно дойти, однако, я побоялся модераторов

C++
1
2
3
4
5
6
7
8
9
size_t FileCount(DIR CurDir){
   while ( CurDir->end_of_files() )
   {
       if ( (CurObj = CurDir->NextFile()) == DIR )
         Count += FileCount(CurObj);
       else
         Count++;
   }
return Count;
Вот такой псевдокод можно применить к подсчету файлов...
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
19.02.2010, 17:05     Простые примеры программ на рекурсию #9
insideone, тогда логичней будет так:
C++
1
while ( !CurDir->end_of_files() )
insideone
Модератор
Автор FAQ
 Аватар для insideone
3620 / 898 / 47
Регистрация: 10.01.2010
Сообщений: 2,421
19.02.2010, 17:14     Простые примеры программ на рекурсию #10
Сообщение было отмечено автором темы, экспертом или модератором как ответ
2 Nameless One угу, не углядел...

PS. "Чтобы понять рекурсию, нужно сначала понять рекурсию"
antikiler
 Аватар для antikiler
0 / 0 / 0
Регистрация: 26.10.2009
Сообщений: 49
19.02.2010, 18:10  [ТС]     Простые примеры программ на рекурсию #11
как будет выглядет рекурсия которая вычисляет ???
d(1)=0, d(2)=1, d(n)=n*d(n-1)+(-1)^n, n>3
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
19.02.2010, 18:18     Простые примеры программ на рекурсию #12
Как-то так:
C++
1
2
3
4
5
6
7
8
size_t d(size_t n)
{
    if(n==1) return 0;
    if(n==2) return 1;
    size_t temp=(n%2) ? (-1) : 1;
    temp+=n*d(n-1);
    return temp;
}
insideone
Модератор
Автор FAQ
 Аватар для insideone
3620 / 898 / 47
Регистрация: 10.01.2010
Сообщений: 2,421
19.02.2010, 18:20     Простые примеры программ на рекурсию #13
C++
1
2
3
4
double d(double n){
   if ( n == 1 ) return 0;
   if ( n == 2 ) return 1;
   return n * d(n-1) + pow(-1, n);
double d(4){
if ( 4 == 1 ) return 0;
if ( 4 == 2 ) return 1;
return 4 *
d(4-1)


double d(3){
if ( 3 == 1 ) return 0;
if ( 3 == 2 ) return 1;
return n *
d(3-1)


double d(2){
if ( 2 == 1 ) return 0;
if ( 2 == 2 ) return 1; // STOP
return 2 * d(2-1)+ pow(-1, 2);
}

+ pow(-1, 3);
}

+ pow(-1, 4);
}

Может так, вы попробуйте главное ж разобраться)
antikiler
 Аватар для antikiler
0 / 0 / 0
Регистрация: 26.10.2009
Сообщений: 49
19.02.2010, 20:17  [ТС]     Простые примеры программ на рекурсию #14
Как будет выглядеть полный код?
insideone
Модератор
Автор FAQ
 Аватар для insideone
3620 / 898 / 47
Регистрация: 10.01.2010
Сообщений: 2,421
19.02.2010, 20:24     Простые примеры программ на рекурсию #15
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include "math.h"
using namespace std;
 
double d(double n){
   if ( n == 1 ) return 0;
   if ( n == 2 ) return 1;
   return n * d(n-1) + pow(-1, n);
}
 
int main(){
   cout << d(4);
}
Так
cibertronic
 Аватар для cibertronic
255 / 142 / 13
Регистрация: 27.12.2009
Сообщений: 893
19.02.2010, 20:40     Простые примеры программ на рекурсию #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
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
void rec(int,int,int,int);
main()
{
system("title ханойские башни");
 
int n;
system("echo введите количество дисков на первом стержне");
cin>>n;
rec(n,1,2,3);   // функция рекурсии
 
getch();
}
void rec(int n,int i,int j,int w)
{
if(n>1)
{
rec(n-1,i,w,j);    //вот тут и есть рекурсия
rec(1,i,j,w);       //а именно - функция вызывает саму себя
rec(n-1,w,j,i);
}
else cout<<"c "<<i<<" na "<<j<<endl;
return;
}
antikiler
 Аватар для antikiler
0 / 0 / 0
Регистрация: 26.10.2009
Сообщений: 49
19.02.2010, 20:43  [ТС]     Простые примеры программ на рекурсию #17
а этот!!
Код
size_t d(size_t n)
{
    if(n==1) return 0;
    if(n==2) return 1;
    size_t temp=(n%2) ? (-1) : 1;
    temp+=n*d(n-1);
    return temp;
}
insideone
Модератор
Автор FAQ
 Аватар для insideone
3620 / 898 / 47
Регистрация: 10.01.2010
Сообщений: 2,421
19.02.2010, 20:58     Простые примеры программ на рекурсию #18
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include "math.h"
using namespace std;
 
size_t d(size_t n)
{
    if(n==1) return 0;
    if(n==2) return 1;
    size_t temp=(n%2) ? (-1) : 1;
    temp+=n*d(n-1);
    return temp;
}
 
int main(){
   cout << d(4);
}
вот так!! (чувства так и хлещут? )
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
20.02.2010, 07:52     Простые примеры программ на рекурсию #19
Цитата Сообщение от antikiler Посмотреть сообщение
Всем привет! У кого есть простые примеры программ на рекурсию, забросьте пожалуйста!!!
И вообще, любую корректную рекуррентную формулу уже по определению можно реализовать в виде рекурсивной функции
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.02.2010, 23:22     Простые примеры программ на рекурсию
Еще ссылки по теме:

Задача на рекурсию C++
У кого нибудь есть приложение Win32 на c++! Примеры программ, с вводом и выводом данных! чтобы нагляднее было! C++
C++ [C/C++] Примеры программ парсеров

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

Или воспользуйтесь поиском по форуму:
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
20.02.2010, 23:22     Простые примеры программ на рекурсию #20
Рекурсия. Функция аккермана:

C++
1
2
3
4
5
6
7
8
int Akk(int m, int n){
     if (!m and n)
     return (n+1);
     else
     if (m and !n)
     return Akk(m-1,1);
     return Akk(m-1,Akk(m,n-1));
}
Yandex
Объявления
20.02.2010, 23:22     Простые примеры программ на рекурсию
Ответ Создать тему
Опции темы

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