Блог

Новичок в Scala и пытаюсь разобраться в рекурсии.

Наличие определений в моем сеансе:

 def inc(n: Int) = n   1
def dec(n: Int) = n – 1
  

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

 add(n: Int, m: Int) = n   m
  

Мне интересно изучать как регулярную рекурсию, так и хвостовую рекурсию.

Спасибо

Как насчет этого:

 scala> def inc(n: Int) = n   1
inc: (n: Int)Int

scala> def dec(n: Int) = n - 1
dec: (n: Int)Int

scala> def add(n: Int, m: Int): Int = m match {
     |   case 0           => n
     |   case _ if m > 0  => add(inc(n), dec(m))
     |   case _           => add(dec(n), inc(m))
     | }
add: (n: Int, m: Int)Int

scala> add(100, 99)
res0: Int = 199

scala> add(100, -99)
res1: Int = 1
  

Или есть другое решение, которое является реализацией аксиом Пеано.

 scala> def add2(n: Int, m: Int): Int = m match {
     |   case 0           => n
     |   case _ if m > 0  => inc(add2(n, dec(m)))
     |   case _           => dec(add2(n, inc(m)))
     | }
add2: (n: Int, m: Int)Int
  

Насколько я понимаю, хвостовая рекурсия состоит из 3 частей:

• Условие для завершения рекурсии
• возвращаемое значение если условие выполнено, возвращаемое значение является одним (или производным от) параметров хвостовой рекурсивной функции
• и вызов самого себя, если условие не выполнено.

пример:

 def inc(n: Int) = n   1
def dec(n: Int) = n - 1


def add(n:Int, m:Int, sum: Int):Int = {
  //condition to break/end the recursion
  if (m <= 0) {
    // returned value once condition is met. This is the final output of the recursion
    sum
  } else {
    //call to itself once condition is unmet
    add(inc(n), dec(m), n   m)
  }
}
  

как вы можете видеть, такое ощущение, что вы выполняете цикл while, но более функциональным способом.

при рекурсии вызовы являются стеком, что приводит к тому, что размер стека вызовов равен глубине рекурсивных вызовов (что может привести к исключению stackoverflowexception). при хвостовой рекурсии это похоже на то, как интерпретируется цикл while.

пример рекурсии:

 def addAllNumberFromNToZero(n:Int):Int = {
  if (m <= 0) {
    sum
  } else {
    n   add(n - 1)
  }
}
  

Используя обычную рекурсию, вы могли бы попробовать что-то вроде:

   def inc(n: Int) = n   1
  def dec(n: Int) = n - 1

  def add(n: Int, m: Int): Int = {
    if (m == 0) n
    else add(inc(n), dec(m))
  }
  

add Функция рекурсивно вызывает саму add себя, каждый раз увеличивая n и уменьшая m . Рекурсия останавливается, когда m достигает нуля, после чего m возвращается точка.