Проблемы с рекурсией задачи о совершенном числе

Я работал над проблемой рекурсии scala. Раньше я разрабатывал программу с использованием циклов, а затем использовал концепцию рекурсии для преобразования существующей проблемы цикла в рекурсивное решение.
Поэтому я написал следующий код, чтобы найти идеальное число с использованием циклов.

  def isPerfect(n: Int): Boolean = {
    var sum = 1
    // Find all divisors and add them
    var i = 2
    while ( {
      i * i <= n
    }) {
      if (n % i == 0) if (i * i != n) sum = sum + i + n / i
      else sum = sum + i

      i += 1
    }
    // If sum of divisors is equal to
    // n, then n is a perfect number
    if (sum == n && n != 1) return true
    false
  }

Вот моя попытка преобразовать его в рекурсивное решение. Но я получаю неверный результат.

  def isPerfect(n: Int): Boolean = {
    var sum = 1
    // Find all divisors and add them
    var i = 2
    def loop(i:Int, n:Int): Any ={
      if(n%i == 0) if (i * i != n) return sum + i + n / i
      else
        return loop(i+1, sum+i)
    }
    val sum_ = loop(2, n)
    // If sum of divisors is equal to
    // n, then n is a perfect number
    if (sum_ == n && n != 1) return true
    false
  }

Заранее спасибо.


recursion scala tail-recursion perfect-numbers
person petereg157    schedule 01.03.2020    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Вот решение с хвостовой рекурсией

def isPerfectNumber(n: Int): Boolean = {
  @tailrec def loop(d: Int, acc: List[Int]): List[Int] = {
    if (d == 1) 1 :: acc
    else if (n % d == 0) loop(d - 1, d :: acc)
    else loop(d - 1, acc)
  }
  loop(n-1, Nil).sum == n
}

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

person Mario Galic    schedule 01.03.2020