CODEWITHSUNDEEP
scalarecursiontail-recursionperfect-numbers
petereg157
petereg157

Reputation: 57

Facing Issues in Recursion of Perfect Number Problem

I've been working on the scala recursion problem. I used to develop the program using loops and then use the concept of recursion to convert the existing loop problem in a recursive solution.
So I have written the following code to find the perfect number using loops.

  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
  }

Here is my attempt to convert it into a recursive solution. But I'm getting the incorrect result.

  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
  }

Thank you in advance.

Upvotes: 2

Views: 302

Answers (1)

Mario Galic
Mario Galic

Reputation: 48420

Here is a tail-recursive solution

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
}

As a side-note, functions that have side-effects such as state mutation scoped locally are still considered pure functions as long as the mutation is not visible externally, hence having while loops in such functions might be acceptable.

Upvotes: 3

Related Questions