Рекурсия

В теле функции известны все объекты, описанные во внешнем блоке, т.е. все глобальные переменные и имя самой функции.

Таким образом, внутри любой функции можно вызывать любую доступную функцию, в том числе и саму себя. Ситуация, когда функция вызывает саму себя, называется рекурсия.

Рекурсия возможна благодаря тому, что при вызове функции создаются новые экземпляры локальных переменных, которые сохраняются во внутреннем стеке машины. Стек функционирует по принципу LIFO - Last In – First Out (последний вошел – первый вышел).

Переменные помещаются в стек одна за другой и выбираются из стека в обратном порядке.

Обязательным элементом всякого рекурсивного процесса является утверждение, определяющее условие завершения рекурсии. Оно называется опорным условием рекурсии.

Если опорное условие выполняется, то может быть задано некоторое фиксированное значение, заведомо достижимое в ходе вычисления. Это позволит организовать своевременную остановку рекурсивного процесса.

Рассмотрим пример вычисления факториала 5.

, где - это 4!

т.е 5!=4! 5

Факториал нуля равен 1. Отсюда формула вычисления N-факториала:

Реализуем вычисление факториала в виде функции:

#include "stdafx.h"

float fact(int N) //рекурсивная функция вычисления факториала числа N

if (N==0)

return 1;

Else

return (fact(N-1)*N);

}

void main()

{ int N=15;

printf("факториал 15=%f\n", fact(N)); /* обращение к функции fact для вычисления факториала 15 */

}

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

Пример: Вычислить количество нулей в массиве А[10].

# include "stdafx.h"

const int n=10;

int kol(int i,int *A)

{ if (i==n) return 0;

else {

if(A[i]==0) return kol(i+1,A)+1;

else return kol(i+1,A);

}

}

int main()

{ int y[]={1,0,2,5,4,0,1,3,0,4,3};

int x=kol(0,y);

printf("количество нулей=%d\n",x);

}

Поиск по сайту: