Recursive sum function, How do i limit the sum?-CodePudding

The goal is to code this sum into a recursive function. Sum

I have tried so far to code it like this.

def under(u: Int): Int = {
    var i1 = u/2
    var i = i1 1
    if (  u/2 == 1 ) then u   1 - 2 * 1
    else   (u   1 - 2 * i)   under(u-1)
}

It seems like i am running into an issue with the recursive part but i am not able to figure out what goes wrong. In theory, under(5) should produce 10.

CodePudding user response：

Your logic is wrong. It should iterate (whether through loop, recursion or collection is irrelevant) from i=1 to i=n/2. But using n and current i as they are.

(1 to (n/2)).map(i => n   1 - 2 * i).sum

You are (more or less) running computations from i=1 to i=n (or rather n down to 1) but instead of n you use i/2 and instead of i you use i/2 1. (sum from i=1 to i=n of (n/2 1 - 2 * i)).

// actually what you do is more like (1 to n).toList.reverse
// rather than (1 to n)
(1 to n).map(i => i/2   1 - 2 * (i/2   1)).sum

It's a different formula. It has twice the elements to sum, and a part of each of them is changing instead of being constant while another part has a wrong value.

To implement the same logic with recursion you would have to do something like:

// as one function with default args

// tail recursive version
def under(n: Int, i: Int = 1, sum: Int = 0): Int =
  if (i > n/2) sum
  else under(n, i 1, sum   (n   2 - 2 * i))

// not tail recursive
def under(n: Int, i: Int = 1): Int =
  if (i > n/2) 0
  else (n   2 - 2 * i)   under(n, i   1)

// with nested functions without default args

def under(n: Int): Int = {
  // tail recursive
  def helper(i: Int, sum: Int): Int =
    if (i > n/2) sum
    else helper(i   1, sum   (n   2 - 2 * i))
  helper(1, 0)
}

def under(n: Int): Int = {
  // not tail recursive
  def helper(i: Int): Int =
    if (i > n/2) 0
    else (n   2 - 2 * i)   helper(i   1)
  helper(1)
}

CodePudding user response：

As a side note: there is no need to use any iteration / recursion at all. Here is an explicit formula:

def g(n: Int) = n / 2 * (n - n / 2)

that gives the same results as

def h(n: Int) = (1 to n / 2).map(i => n   1 - 2 * i).sum

Both assume that you want floored n / 2 in the case that n is odd, i.e. both of the functions above behave the same as

def j(n: Int) = (math.ceil(n / 2.0) * math.floor(n / 2.0)).toInt

(at least until rounding errors kick in).