Урок 9.6. Рекурсивные функции

9.6. Рекурсивные функции

В языке Си функции могут вызывать сами себя непосредственно или косвенно, т.е. могут быть рекурсивными. Если функция непосредственно вызывает саму себя – то это называется прямой рекурсией, а если функция вызывает какую-либо другую функцию, которая либо сама, либо посредством другой функции вызывает исходную функцию – то это называется косвенной рекурсией.

Каждая цепочка рекурсивных вызовов должна на каком-то шаге завершиться. Условие полного окончания работы рекурсивной функции должно находиться в самой функции (иначе произойдет зацикливание), а именно, любая рекурсивная функция должна содержать рекурсивный вызов внутри условного оператора.

Применять рекурсивные методы программирования стоит в тех задачах, где рекурсия использована в определении обрабатываемых данных. Это, как правило, связано с такими динамическими структурами данных как стеки, деревья, очереди и др. Многие задачи, решаемые при помощи рекурсии, более эффективно решаются либо с помощью итеративных алгоритмов либо с помощью подпрограмм. Например, вычисление факториала, которое мы рассмотрим, удобно для объяснения рекурсии, однако не дает никакого выигрыша в программной реализации. Более того, рекурсивный алгоритм вычисления факториала работает медленнее итеративного алгоритма, за счет накладных расходов на вызов функции и возврат значений.

Рассмотрим пример программы вычисляющей факториал положительного числа.

#include <stdio.h>
#include <conio.h>
#include <iostream>
using namespace std;
void main()
{
   int f(int k); //функция вычисления факториала
   int fact = f(5);
   cout << "fact! = " << fact;
getch();
}
// Рекурсивная функция вычисления факториала
int f(int k)
{
if (k < 0)  return 0;
if (k == 0) return 1; //т.к. 0! == 1
return k * f(k-1);
}

При первом вызове f(5) функция возвращает выражение 5*f(4), т.е. функция f() фактически не возвращает значение, а вызывает сама себя с другим значением. Рекурсивные вызовы будут продолжаться до тех пор, пока k не станет равным 0. Будет создана следующая цепочка возвращаемых выражений:

5*f(4), 4*f(3), 3*f(2), 2*f(1), 1*f(0)

Вызов f(0)не провоцирует дальнейших вызовов, а возвращает значение 1, произведение 1*1 будет возвращено предыдущему вызову и т.д. до вызова f(5), которому возвращается значение 120. Тем самым будут организованы следующие умножения:

1*1*2*3*4*5, а в общем случае 1*1*2*3*4*5*…*(k-1)*k

Рассмотрим еще один традиционный пример функции, представленной в форме прямой рекурсии, – печать чисел как последовательности символов.

#include <stdio.h>
#include <conio.h>
 
void main()
{ void printd(int n); 
  int n;
  n = 135;
  printd(n);
_getch();
}
//Рекурсивная функция 
void printd(int n) // печать n
{ int i;
  if (n < 0) 
  {
     putchar('-'); // печать минуса для отрицательных чисел
     n=-n;
  }
  if ((i = n / 10)!= 0) printd(i);
  putchar(n%10+'0'); // преобразование цифры в символ
}

Рассмотрим работу этой функции для числа n=153. Поскольку число положительно, то операторы печати знака минус putchar('-'); и смена знака числа n=-n; пропускаются.

Оператор if ((i=n/10)!=0) printd(i); проверяет целую часть частного 153/10 = 15 на ноль. Если целая часть не ноль, то с этим значением (15) идет вновь обращение к функции printd(), а после возврата из нее оператором putchar(n%10+'0'); печатается остаток от деления 153%10 = 3, т.е. 3. Аналогично, вторая printd() передает третьей 1 (та печатает ее), а затем сама печатает 5.

Таким образом, однократное обращение извне к функции printd(); вызовет трехкратное ее срабатывание.

Задание на дом: напишите рекурсивную функцию вычисления целой степени вещественного числа.

Решение:

#include <stdio.h>
#include <conio.h>
#include <iostream>
 
using namespace std;
void main()
{  double power(double a, int n);//прототип функции
   double a = 5;
   int n = - 3;
 
   double d = power(a, n);
   cout << a << "^" << n << " = " << d; 
_getch(); 
} 
// Рекурсивная функция вычисления целой степени вещественного числа
double power(double a, int n)
{
   if (n == 0) return 1;
   if (a == 0) return 0;
   if (n > 0)  return a * power(a, n-1);
   if (n < 0)  return power(a, n+1) / a;
}

Задание на дом: напишите рекурсивную функцию вычисления суммы элементов вектора. Тело функции должно состоять из одной строчки.

Решение (2 варианта summa() и summa1()):

#include <stdio.h>
#include <conio.h>
#include <iostream>
using namespace std;
void main()
{
   double summa (int *v, int n); //прототипы функций
   double summa1(int *v, int n);
   int v[5] = {1, 2, 3, 4, 5};
   double s = summa(v, 5);
   cout << "s = " << s << endl;
   double s1 = summa1(v, 5);
   cout << "s1 = " << s1 << endl; 
_getch(); } 
// Рекурсивные функции вычисления суммы элементов вектора 
double summa(int *v, int n) 
{    
   return n > 0 ? summa(v, n-1) + v[n-1] : 0;
}
double summa1(int *v, int n)
{
   return n > 0 ? summa(v+1, n-1) + *v : 0;
}

Рассмотрим пример косвенной рекурсии. Пример принадлежит к классу алгоритмов, работающих с данными, структура которых тоже определяется рекурсивно. Характерной задачей такого рода является преобразование простых выражений в соответствующую постфиксную форму (иначе Полиз – польскую инверсную запись), т.е. в форму, при которой знак операции следует за операндами. Выражение будем определять в виде РБНФ[*] так:

Выражение = Слагаемое{("+" I "-")Слагаемое}.
Слагаемое = Множитель{("*" I "/")Множитель}.
Множитель = Буква I "("Выражение")" I "["Выражение"]"

Обозначая выражение как Е, слагаемые как Т1, Т2, а множители как F1, F2, запишем правила преобразования:

T1+T2 --> T1T2+
T1-T2 --> T1T2-
F1*F2 --> F1F2*
F1/F2 --> F1F2/
(E) --> E
[E] --> E
___________________________________________________________________
[*]
РБНФ - расширенная форма Бэкуса-Наура, метанотация (формализм) для записи синтаксических конструкций. В данном примере использованы такие метасимволы:.,+,{,},(,),I. Эти метасимволы читаются следующим образом:

  • А = ВС - синтаксическая конструкция А состоит из следущих друг за другом конструкций В и С.
  • А = В I С - А состоит либо из В, либо из С.
  • А = {B} - А может состоять из конкатенации любого числа (включая ноль) конструкций В.

Наша программа отражает структуру синтаксиса входных выражений. Поскольку синтаксис рекурсивен, рекурсивна и сама программа.

#include <stdio.h>
#include <conio.h>
 
#define EOL 0x0a
char *ch = new char [100];
char *rez = new char [100];
char *rez1;
 
void Mnoj(); // множитель 
void Slag(); // слагаемое
void Vir();  // выражение
void main()
{
  rez1 = rez; //адрес rez будет меняться, а для вывода результата 
              //нужно начало строки
  scanf("%30s", ch); //не более 100 символов
  Vir();
  *rez = '\0'; 
  puts("rez1=");
  puts(rez1);
_getch();
}
 
void Vir() /* выражение */
{  char OpSl;
   Slag();
   while( (*ch == '+') || (*ch == '-')) 
       {
	 OpSl =* ch++; // операция сложения 
	 Slag();
	 *rez++ = OpSl;
       }
  //*rez = '\0';
} // конец выражения 
 
void Slag() /* слагаемое */
{  char OpUmn;
   Mnoj();
     while ((*ch == '*') || (*ch == '/')) 
	{
	   OpUmn =* ch++;
	   Mnoj();
	   *rez++ = OpUmn;
	}
}
 
void Mnoj() /* множитель */
{
   if (*ch == '(') 
	  { ch++; 
	    Vir();
	    while (*ch++ != ')'); 
	    return;
	   }
	else
	   if (*ch == '[') 
		  { ch++; 
		    Vir();
		    while (*ch != ']') ch++;
    	          }
	    else
		 while ((*ch < 'a') || (*ch > 'z'))
			ch++;
   *rez++ = *ch++;
} // конец множителя 
 
//Результат работы:
 >a+b          ab+
 >a*b+c        ab*c+
 >a+b*c        abc*+
 >a*(b/[c-d])  abcd-/*

 

При повторном входе в рекурсивную функцию в памяти машины создаются копии всего набора локальных переменных этой функции, организуемые в виде стека.

Рекурсии, как правило, не предусматривают никаких механизмов защиты памяти, так что иногда стек обрабатываемых величин может переполняться. Возможные ошибки такого рода должен предотвращать сам программист.

 

рассказать друзьям и получить подарок

Оставить комментарий

Ваш email не будет опубликован. Обязательные поля отмечены *

Вы можете использовать это HTMLтеги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Translate Переводчик

Подписка на новости

SmartResponder.ru
Ваш e-mail: *
Ваше имя: *

Хостинг для Wordpress сайтов