Конструкција алгоритама рекурзијом тј. индукцијом

Један од основних механизама конструкције алгоритама подразумева да се до решења проблема долази тако што се проблем сведе на решавање једног или више потпроблема истог облика, али мање димензије. Свођење, наравно, не може да тече у недоглед, већ је потребно да проблеме мале димензије умемо да решимо директно, без даљег свођења. На пример, проблем димензије \(0\) се решава директно, док се за свако \(n > 0\), проблем димензије \(n\) своди на проблем димензије \(n-1\).

Имплементација овог поступка може бити реализована на два начина.

• Могуће је дефинисати рекурзивну функцију (функције која позива саму себе), којој се преко улазних параметара (уз евентуално коришћење додатних, глобалних променљивих) прослеђује опис проблема који се тренутно решава. Унутар функције се врши анализа да ли је прослеђени проблем довољно мале димензије да би се могао директно решити или се његово решење добија тако што функција позове сама себе да реши један или више мањих потпроблема.

• Могуће је дефинисати итеративни поступак, који подразумева да се у петљи променљиве ажурирају, кренувши од решења проблема мале димензије па проширујући решење мало по мало, све док се не дође до решења проблема тражене димензије.

Без обзира на то да ли се користи рекурзивна или итеративна имплементација, у основни оваквих алгоритама лежи исти поступак и њихова коректност следи на основу приниципа математичке индукције. Случај који се директно решава представља базу индукције. Индуктивна је претпоставка да су потпроблеми коректно решени и на основу те индуктивне претпоставке се доказује да се полазни проблем коректно решава. Стога ћемо често говорити о индуктивно-рекурзивној конструкцији и често ћемо приказивати и рекурзивну и нерекурзивну имплементацију (до које ћемо долазити било директно, било ослобађањем рекурзије).