Recursive sum function, How do i limit the sum?

user_17336228 0
Viewed 94

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.

recursion scala functional-programming
2 Answers

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)
}
user_13051210

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).

user_27077920
Related