Рекурсия и возврат в javascript

Question

Я изучаю Javascript на CodeAcademy.com, и у меня возникли трудности с пониманием вопроса об упражнении, хотя я, кажется, нашел правильный ответ.

Код разработан, чтобы помочь кому-то решить, сколько изменений они должны отдать, когда кто-то что-то покупает. Он принимает число и вычисляет, сколько кварталов и сколько копеек они должны отдать.

Вот что я не понимаю:

• Не следует ли код остановки запуска в первый раз, он встречает линии 11? Если нет, почему бы и нет?

• Если код не работает, когда он входит в строку 11, почему я могу разместить код после строки 10, и он будет выполняться три раза, прежде чем будет дан ответ? Я обнаружил, что это так, поэтому я задал вопрос о том, как работает код! Я добавил строку quarters += 1; после строки 10 и возвращает 6.

var change = 0; 
var quarters = 0; 
function howManyQuarters(howMuchMoney) { 
    if (howMuchMoney < 0.25) { 
    change = howMuchMoney; 
    return 0; 
    } 
    else { 
    quarters += 1; 
    howManyQuarters(howMuchMoney-0.25); 
    return quarters; // << line 11 
    } 
} 

change = 0.99; 
console.log ("Pay out " + howManyQuarters(change) + " quarters"); 
console.log ("And you'll have " + change * 100 + " pennies left over"); 

Answer 1

Не обязательно. С рекурсией вы потенциально вызываете функцию несколько раз, и каждый вызов должен вернуться до того, как код будет выполнен для функции. Поэтому, если howManyQuarters вызывается 3 раза, он будет выполнять код сразу же после вызова функции (в данном случае оператора return) и много раз.

Надеюсь, что это ясно.

Answer 2

В этом весь смысл рекурсии: функция вызывает себя до тех пор, пока условие останова не будет выполнено и станет истинным, тогда оно больше не будет называть себя.

В этом случае, да, функция действительно остановится на линии return quarters;, но в этот момент она уже называла себя в строке раньше.

Условие остановки гарантирует, что у вас не будет бесконечного цикла - при вызове функции вы даете ей число - когда это число меньше 0,25, функция остановится. Итак:

Основные примеры:

1. Если начальное число было меньше, чем 0,25 функция будет работать только один раз, возвращаясь 0.
2. Если начальное число составляло от 0,25 до 0,5 функция будет дважды баллотировался - самозапуск (рекурсия) произойдет один раз, потому что значение не меньше 0,25, но самозапуск передаёт значение минус 0,25, так что теперь значение во втором вызове будет уже меньше 0,25 - условие остановки выполнено, все хорошо.

Само возвращаемое значение управляется глобальной переменной, объявленной вне функции - каждый раз, когда функция вызывает себя, она увеличивает эту переменную на 1, поэтому в конце вы знаете, сколько раз она была вызвана. Теперь это не очень умно, как вы можете видеть в this example - второй вызов функции с таким же количеством изменений приведет к неправильному результату.

Answer 3

код не останавливается работает в первый раз на линии 11, потому что первый раз она достигает 10-й строки она (эффективно) возвращается в линию 3.

Попробуйте изобразить его таким образом.Я выстроились уровни рекурсии:

1. (Line 15) howManyQuarters(0.99) 
    2. (Line 4) howMuchMoney is > 0.25...so else applies 
    3. (Line 10) howManyQuarters(0.74) --> 0.74 = 0.99-0.25 
     4. (Line 4) howMuchMoney is > 0.25...so else applies 
     5. (Line 10) howManyQuarters(0.49) --> 0.49 = 0.74-0.25 
      6. (Line 4) howMuchMoney is > 0.25...so else applies 
      7. (Line 10) howManyQuarters(0.24) --> 0.24 = 0.49-0.25 
       8. (Line 4) howMuchMoney is < 0.25...so enter main body of if clause 
       9. (Line 6) return 0; 
      11. (Line 11) return quarters; 
     12. (Line 11) return quarters; 
    13. (Line 11) return quarters; 
14. (Line 11) return quarters; 

Answer 4

Каждый раз, когда функция будет введена, она в конечном счете вышел через return. Вот диаграмма:

Enter howManyQuarters. 
    Enter howManyQuarters. 
    Enter howManyQuarters. 
     Enter howManyQuarters. 
     return 
    return 
    return 
return 

Answer 5

Извините, немного оффтопик, но зачем вам нужна такая сложная функция для простой математической работы? Это фактически необходимость в одной строке (но с агрегированным результатом).

function howMuchMoney(val) { 
    return [ 
     Math.floor(val/0.25), 
     parseFloat((val % 0.25).toFixed(2)) 
    ]; 
} 

Это он, так же просто.

http://jsfiddle.net/semencov/D8xUE/

Answer 6

Функция является правильным. Рекурсия - удивительный и мощный метод в информатике. Рекурсивная функция всегда имеет ту же структуру:

function myRecursive(nSizeData){ 
    if(baseCondition is TRUE){ 
    //compute the function with nSizeData 
    //do stuff here 
    } 
    else{ 
    //call the same function with a smaller size set of data 
    //this condition ensure that the baseCondition will eventually be matched 
    myRecursive(mSizeData); 
    } 
} 

Там является базовым условием, что представляют собой основу функции: если входные данные функции соответствуют baseCondition, функция может вычислить без вызова себя. В противном случае он называет себя передачей меньшего размера набора данных. Вычислительный процесс рекурсивной функции может быть представлен через стек: я вставляю в стек каждый раз, когда вызывается функция, я выталкиваю стек, когда функция возвращает значение. Первый поп всегда будет результатом блока baseCondition.

Предупреждение: если базовое условие никогда не сопоставляется, в конечном итоге произойдет переток стеков.

Классическим примером является факторный функция целого числа:

function factorial(n){ 
    if(n==0 || n==1){ 
    return 1; 
    } 
    else{ 
    return factorial(n-1); 
    } 
} 

См here для получения дополнительной информации.

Answer 7

Вот что я могу думать, что заявление

return quarters; 

не была выполнена только после того, как линии 10. Когда управление сталкиваются с заявлением

howManyQuarters(howMuchMoney-0.25); 

он называет себя, не выполнив строка 11. Когда все рекурсия выполнена, управление выходит из каждого цикла (рекурсия) и выполняет линию 11.