Понимание, рекурсия в Ruby

В рекурсии метод вызывает сам себя. Я не слежу за ним, когда есть возвращаемые значения. Например, в книге «Учитесь программировать» Криса Пайна есть пример с факториалами.

def factorial num 
  if num < 0
    return 'You cant\'t take the factorial of a negative number!'
  end
  if num <= 1
    1
  else 
    num * factorial(num-1)
  end
end

Если я вызову метод factorial(3), он перейдет к else части кода и будет выглядеть так:

3 * factorial(3-1)

и должен вернуть 6 с 3*2=6. factorial(3-1) вызывает метод factorial, передавая 2 внутри рекурсии. num = 2 и, следовательно, 2 * factorial(2-1) и 2*1=2.

Что происходит с 6, полученным при первом прогоне кода? Теперь, когда num = 1, похоже, теперь будет возвращаться 1 и переходить к концу кода. Но, насколько я понимаю, у нас все еще есть 6 и 2 из предыдущих рекурсий. Прав ли я в этом предположении, так как мы вызывали факториальную функцию, когда умножали на num? Может ли кто-нибудь помочь мне понять это лучше? Скажем, мы позвонили factorial(10), как это сработает?


ruby recursion factorial
person Ordep81    schedule 21.05.2013    source источник
comment
Вы смотрели "Начало"?   -  person oldergod    schedule 21.05.2013
comment
Весь этот код... когда все, что вам нужно было сделать, это: def fact(n) (1..n).inject(1) {|r,i| r*i } end :)   -  person Nir Alfasi    schedule 21.05.2013
comment
Функция факториала всегда используется в качестве примера для рекурсии, когда это ужасный способ решить эту проблему. Я думаю, что это нанесло начинающим программистам всевозможные повреждения мозга, поскольку вскоре каждая проблема становится чем-то, что нужно решать с помощью рекурсии, а не с помощью правильной техники, такой как стек.   -  person tadman    schedule 21.05.2013

Ответы (3)


arrow_upward
0
arrow_downward

Во-первых, вы должны заменить return 'blabla' на raise 'blabla', потому что ваша функция возвращает числовое значение, а не строку.

Тогда смотри так

factorial(3)
  3 * factorial(2)
        2 * factorial(1)
              1  # no more recursion, let's go up replacing 
                 # the function calls by the returned value
            end
      end
end
# ↓
factorial(3)
  3 * factorial(2)
        2 * 1  # let's go up again !
      end
end
# ↓
factorial(3)
  3 * 2 # finally
end
# ↓
6
person oldergod    schedule 21.05.2013

arrow_upward
4
arrow_downward

Что теперь происходит с 6, которые мы получили при первом прогоне кода?

Не было 6 с первого запуска; 6 появилось только в конце.

Вот что происходит:

factorial(3) → 3 * factorial(2)
factorial(3) → 3 * 2 * factorial(1)
factorial(3) → 3 * 2 * 1

В вашей функции нет «памяти» о предыдущих вызовах, каждый раз, когда вызывается factorial(), это похоже на совершенно новую функцию; это яснее, когда написано как несколько функций?

def factorialof3
  3 * factorialof2
end

def factorialof2
  2 * factorialof1
end

def factorialof1
  1
end
person Patrice Levesque    schedule 21.05.2013

arrow_upward
1
arrow_downward

Ответ Патриса, разделяющий его на отдельные функции, хорош, и если у вас есть какие-либо знания в области компьютерных наук, это также поможет подумать о том, какие структуры данных, вероятно, здесь работают, в основном Стек

Поэтому, когда вы вызываете factorial(3), он перейдет к этому блоку else и "сложится" при другом вызове factorial(2)

а затем сложите еще один с вызовом factorial(1).

в этот момент, поскольку num = 1 (рекурсия всегда должна иметь базовый случай), factorial(1) вернет 1.

Затем из-за стека последний входящий является первым исходящим, поэтому факториал (1) вернет 1, и это «упадет» обратно до вызова factorial(2), и поскольку он был вызван в этом блоке else, вызов factorial(2-1) теперь будет заменен на 1, и вы получите 2*1, и я думаю, что теперь вы поняли картину

Также важно отметить, что этот пример пытается научить вас рекурсии в целом, и этот пример на самом деле не идиоматический ruby. Решение alfasin, опубликованное в качестве комментария, больше похоже на это.

person darethas    schedule 21.05.2013