Почему рекурсия — это все-таки зло? И как не нужно писать программки на собеседовании в Google?

Недавно столкнулся с интересной ситуацией, связанной с тем в какие неприятности можно попасть, написав совсем простой, маленький код, использующий рекурсию.

Классическим примером рекурсии является определение чисел Фибоначчи. N-е число Фибоначчи определяется как сумма (N-1)-го и (N-2)-го числа Фибоначчи. Исключение составляют первые два числа Фибоначчи — по определению первое равно 0, а второе равно 1.
F[0] = 0,
F[1] = 1,
F[n] = F[n-2]+F[n-1], для n >= 2.

Итак, два следующих алгоритма (код написан на языке Java) для нахождения n-го числа Фибоначчи являются очевидными. Первый из них рекурсивный и второй нерекурсивный.

long recursivefib(int n){
 if (n <= 0) return 0L;
 else if(n == 1) return 1L;
 else return recursivefib(n-1)+recursivefib(n-2);
 }

long nonrecursivefib(int n){
 if (n <= 0) return 0L;
 else if(n == 1) return 1L;
 else {
 long value0 = 0L;
 long value1 = 1L;
 long value2 = 1L;
 for (int i = 0; i < n-1; i++){
 value2 = value0+value1;
 value0 = value1;
 value1 = value2;
 }
 return value2;
 }
 }

Предположим, что индекс n не превышает 161 004 — это максимальное число Фибоначчи, помещающееся в 63 старших бита (не считая 0-го знакового) типа long и равное 7 829 159 639 441 890 064.

Далее если вы попробуете посчитать 5-е число Фибоначчи:

void main(String[] args) {
 System.out.println(recursivefib(5));
 System.out.println(nonrecursivefib(5));
 }

или 8-е

void main(String[] args) {
 System.out.println(recursivefib(8));
 System.out.println(nonrecursivefib(8));
 }

или даже 13-е

void main(String[] args) {
 System.out.println(recursivefib(13));
 System.out.println(nonrecursivefib(13));
 }

то скорее всего не увидите разницы.

Но если вы попробуете посчитать 43-е число Фибоначчи:

void main(String[] args) {
 System.out.println(recursivefib(43));
 System.out.println(nonrecursivefib(43));
 }

то наверное что-то заподозрите, а когда вы попробуете посчитать 65-е число Фибоначчи:

void main(String[] args) {
 System.out.println(recursivefib(65));
 System.out.println(nonrecursivefib(65));
 }
 

то поймете в чем проблема, и что проблема не в переполнении стека, а программа просто зависла и зависла так где-то лет на 200. Мы в своей собственной жизни не увидим 65-е число Фибоначчи, его увидят наши далекие пра пра пра… правнуки.

Что происходит?

Оказывается, что если, очевидно, порядок сложности второго нерекурсивного алгоритма равен O(n), где n-номер искомого числа Фибоначчи, то порядок сложности рекурсивного алгоритма, неочевидно, равен O(2^n) два в степени n.

Почему в рекурсивном алгоритме выполняется порядка 2^n операций — вам предлагается разобраться самостоятельно.

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

Кстати, есть и более быстрые громоздкие алгоритмы для вычисления чисел Фибоначчи, имеющие порядок сложности O(log2(n)).

И последнее, что хочется сказать, так это то, что никогда! никогда! не нужно писать такие «эффективные» рекурсивные программки на собеседовании в Google.