Я получил этот вопрос в интервью. Итак, мне кажется, что это запутанная последовательность Фибоначчи. генератор суммы, и это дает stackoverflow. Потому что if(n==0) should be if(n<3) (условие выхода неверно). Каким должен быть точный ответ на этот вопрос? Что ожидалось в ответ?
foo (int n) {
if (n == 0) return 1;
return foo(n-1) + foo(n-2);
}
ОБНОВЛЕНИЕ
Что делает эта рекурсивная функция?
Что вы делаете, когда видите эти 3 строки кода. Нет отладки.
Да, это просто рекурсивный метод Фибоначчи с неправильным базовым регистром (хотя я не думаю, что я бы использовал n < 3 тоже... это зависит от того, как вы его определяете).
Что касается "что ожидалось в качестве ответа" - это будет зависеть от вопроса. Вам задали точно вопрос, указанный в заголовке вашего сообщения? Если это так, то ответ таков: «он рекурсирует вечно, пока не взорвет стек, когда вы передадите ему любое значение, отличное от 0» — с объяснением, конечно. (Это никогда не закончится, потому что либо n-1 не равно 0, или n-2 не равно 0, либо и то, и другое.)
РЕДАКТИРОВАТЬ: вышеизложенное отвечает на первый вопрос. Чтобы ответить «Что вы делаете, когда видите эти 3 строки кода», я бы сделал вывод, что рассматриваемый разработчик никогда не запускал код со значением, отличным от 0, или не заботится о том, работает код или нет.
Проблема с опубликованным кодом заключается в том, что если мы оцениваем foo(1), нам нужно найти foo(0) и foo (-1), foo(-1), затем нужно найти foo(-2) и foo(-3) и так далее. Это будет продолжать делать вызовы foo() до тех пор, пока в памяти не останется места, что приведет к переполнению стека. Количество вызовов foo будет зависеть от размера стека вызовов, который зависит от реализации.
Когда я вижу эти строки кода, у меня сразу создается впечатление, что тот, кто их написал, не подумал обо всех возможных входных данных, которые можно было бы передать функции.
Чтобы создать рекурсивную функцию Фибоначчи, которая не дает сбоев для foo(1) или отрицательного ввода, мы получаем:
foo (int n) {
if( n < 0 ) return 0;
if (n == 0) return 1;
return foo(n-1) + foo(n-2);
}
Редактировать: возможно, возврат для отрицательного числа должен быть чем-то другим, поскольку последовательность Фибоначчи не определена неявно для отрицательных индексов.
Однако, если мы используем расширение, что fib(-n) = (-1)^(n+1) fib(n), мы могли бы получить следующий код:
int fib(int n) {
if( n == -1){
return 1;
}else if ( n < 0 ){
return ( (-1)^(-n+1 ) * fib(-n) );
}else if (n == 0){
return 1;
}else{
return fib(n-1) + fib(n-2);
}
}
предположим, вы вызываете foo ( 1 ), у него будет два подвызова foo (0) и foo (-1). Как видите, как только вы доберетесь до foo(-1), n будет бесконечно уменьшаться и никогда не достигнет конечного состояния.
Точный ответ будет:
foo (int n) {
if (n <= 1) return 1; // assuming 0th and 1st fib is 1
return foo(n-1) + foo(n-2);
}
Это рекурсивная функция Фибоначчи, где 0-й элемент равен 1.
Игнорируя неправильное условие завершения, код представляет собой «наивную» рекурсивную реализацию функции Фибоначчи. У него очень плохая временная сложность big-O. Это будет нормально работать для небольших n, но если n больше, скажем, 50 (я просто угадываю это число), тогда для запуска потребуется «вечность».
