Рекурсия

Вычисление дискриминанта матрицы с использованием рекурсии

   Применяя для вычисления дискриминанта матрицы рекурсию вместо вложенных циклов (в случае метода Гаусса), мы можем получить очень простой и элегантный алгоритм.

   Для вычисления дискриминанта матрицы A размером N*N воспользуемся разложением по первому столбцу:

   function Discr(A: Ar2): Real;
   var i: Integer;
       D: Real;
   begin
   if High(A)=0 then//если макс. величина индекса массива = 0(массив размером 1*1), то
     begin
       Result:=A[0, 0];//значение функции равно данному числу
       exit;//выходим из функции
     end;
   D:=0;//инициируем начальное значение функции
   k:=1;//начальное значение коэффициента суммирования
   for i:=0 to N-1 do//цикл по первому столбцу
     begin
       D:=D+k*A[0, i]*Discr(Matr(A, i));//суммируем слагаемые дискриминанта, с учётом коэффициента суммирования
       k:=-1*k;//на очередной строке коэффициент суммирования меняется на противоположный
     end;
   Result:=D;
   end;

   Здесь Ar2 - тип данных, двумерный динамический массив, а Matr(A, i) - функция, возвращающая новую матрицу, получающаюся из текущей после удаления первого (нулевого, в программистской терминологии) столбца и i-й строки.

   Таким образом, видим, что громоздкая структура из вложенных циклов заменяется одной функцией, обращающейся к самой себе. Дополнительно лишь требуется написать ещё одну функцию, которая возвращает новую матрицу, получающуюся в результате удаления из текущей нулевого столбца и i-ой строки. Результатом такого удаления является матрица на единицу меньшего размера. Рекурсия работает до тех пор, пока мы не получим матрицу размером 1*1, дискриминантом которой является число A[0, 0]. Когда рекурсия достигнет этого, дальнейшие вызовы функции прекратятся, и дискриминант будет подсчитан.

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

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