Почему рекурсия — это все-таки зло? И как не нужно писать программки на собеседовании в 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-го числа Фибоначчи являются очевидными. Первый из них рекурсивный и второй нерекурсивный.
Предположим, что индекс n не превышает 161 004 — это максимальное число Фибоначчи, помещающееся в 63 старших бита (не считая 0-го знакового) типа long и равное 7 829 159 639 441 890 064.
Далее если вы попробуете посчитать 5-е число Фибоначчи:
или 8-е
или даже 13-е
то скорее всего не увидите разницы.
Но если вы попробуете посчитать 43-е число Фибоначчи:
то наверное что-то заподозрите, а когда вы попробуете посчитать 65-е число Фибоначчи:
то поймете в чем проблема, и что проблема не в переполнении стека, а программа просто зависла и зависла так где-то лет на 200. Мы в своей собственной жизни не увидим 65-е число Фибоначчи, его увидят наши далекие пра пра пра… правнуки.
Что происходит?
Оказывается, что если, очевидно, порядок сложности второго нерекурсивного алгоритма равен O(n), где n-номер искомого числа Фибоначчи, то порядок сложности рекурсивного алгоритма, неочевидно, равен O(2^n) два в степени n.
Почему в рекурсивном алгоритме выполняется порядка 2^n операций — вам предлагается разобраться самостоятельно.
Наверное полностью отказываться от рекурсии не нужно, потому что самые эффективные алгоритмы часто используют рекурсию, например быстрая сортировка, сортировка слиянием, алгоритмы для работы с деревьями и графами, но то, что с рекурсией нужно быть осторожным, так это точно.
Кстати, есть и более быстрые громоздкие алгоритмы для вычисления чисел Фибоначчи, имеющие порядок сложности O(log2(n)).
И последнее, что хочется сказать, так это то, что никогда! никогда! не нужно писать такие «эффективные» рекурсивные программки на собеседовании в 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.