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

Question

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

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

UPDATE

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

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

Answer 1

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

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

EDIT: Вышеуказанные ответы на первый вопрос. Чтобы ответить «Что вы делаете, когда видите эти 3 строки кода», я бы сделал вывод о том, что разработчик, о котором идет речь, никогда не запускает код со значением, отличным от 0, или не заботится о том, работает ли код.

Answer 2

Проблема с отправленным кодом заключается в том, что если мы оценим foo (1), нам нужно найти foo (0) и foo (-1), foo (-1), тогда необходимо найти foo (-2) и foo (-3) и т. Д. Это позволит помещать больше вызовов в foo(), пока в памяти больше нет места, что приведет к переполнению стека. Количество звонков в foo будет зависеть от размера стека вызовов, который будет специфичным для реализации.

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

Чтобы сделать рекурсивную функцию Фибоначчи, которая не подведет для обув (1) или отрицательный вход мы получаем:

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

Edit: возможно возвращение на отрицательное число должно быть что-то еще, как последовательность фибоначчи не определена неявно для отрицательных индексов.

Однако, если мы будем использовать расширение, которое FIB (-n) = (-1)^(п + 1) выдумку (п) мы могли бы получить следующий код:

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

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

Answer 4

Его рекурсивная функция Фибоначчи с 0th элементом является 1.

Answer 5

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