Что делает эта рекурсивная функция?

Question

Я получил этот вопрос в интервью.Таким образом, это кажется мне запутанным последовательностью Фибоначчи.Генератор суммы, и это дает стекопотока.Потому что if(n==0) should be if(n<3) (условие выхода неверно).Каким должен быть точный ответ на этот вопрос?Что ожидается в качестве ответа?

foo (int n) {
if (n == 0) return 1;
return foo(n-1) + foo(n-2);
}

ОБНОВЛЕНИЕ

Что делает эта рекурсивная функция?

Что вы выводите, когда видите3 строки кода.Без отладки.

Answer 1

Да, это просто рекурсивный метод Фибоначчи с неверным базовым регистром (хотя я не думаю, что я бы использовал n < 3 либо ... это зависит от того, как вы его определили).

Что касается "того, что ожидалось в качестве ответа" - это будет зависеть от вопроса. Вам задали точно вопрос в заголовке вашего сообщения? Если это так, то ответ будет «он повторяется вечно, пока не взорвет стек, когда вы передадите ему любое значение, кроме 0» - с объяснением, конечно. (Это никогда не закончится, потому что либо n-1 не равно 0, или n-2 не равно 0, или обоим.)

РЕДАКТИРОВАТЬ: выше ответ на первый вопрос. Чтобы ответить «Что вы выводите, когда видите эти 3 строки кода» - я бы заключил, что разработчик, о котором идет речь, никогда не запускал код со значением, отличным от 0, или не заботился о том, работает ли код.

Answer 2

Проблема с опубликованным кодом заключается в том, что если мы оцениваем 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);
     }
}

Answer 3

Игнорируя неверное условие завершения, код является «наивной» рекурсивной реализацией функции Фибоначчи. У него очень плохая сложность. Это будет работать нормально для малых n, но если n больше, чем, скажем, 50 (я просто угадываю это число), тогда для запуска потребуется «навсегда».

Answer 4

Это рекурсивная функция Фибоначчи с 0-м элементом, равным 1.

Answer 5

предположим, что вы вызываете 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);
}