Urok9_6

Урок 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-/*

 

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

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

 

Translate Переводчик

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

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

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