Рекурсия: различия между версиями

 

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

 

Например, рекурсивный алгоритм вычисления чисел Фибоначчи легко дополнить тремя «строчками»: 1) создать глобальный массив <math>FD</math> , состоящий из нулей; 2)&nbsp;после вычисления числа Фибоначчи <math>F(n)</math> поместить его значение в <math>FD[n]</math>; 2) в начале рекурсивной процедуры сделать проверку на то, что <math>FD[n]=0</math> и, если <math>FD[n]\ne 0</math>, то вернуть <math>FD[n]</math> в качестве результата, а иначе приступить к рекурсивному вычислению <math>F(n)</math>.