1

Edit: I am not looking for an algorithm, but actually a math equation similar to f(i) = sum i=0 to n-1 (C * A[i]), but with respect to n (length of the array) rather than i (iteration #).

I have an algorithm that loops through an array A of size n (with elements A[0] to A[n-1]) and does some computation with the elements of the array. I managed to extract the following recursive function f(i) for the output value of the algorithm, where i is the iteration of the loop:

  • f(0) = A[n-1]
  • f(i) = C * f(i-1) + A[n-1-i]

...where C is an integer constant.

Knowing that we loop through the whole array, we do n-1 iterations (we handle f(0) before the loop). I would like to express this recursive function as a direct iterative function, e.g. f(i) = sum i=0 to n-1 (C * A[i]), but I can't figure out how (it definitely isn't as simple as my example, if doable). I don't really know a formal method for doing this kind of thing, I usually figure it out by intuition for simpler problems.

Is it doable? If so, how? Hopefully I was clear enough, thanks.

mblitz
  • 189
  • 2
  • 10
  • If it works, why change it? – Ash Burlaczenko Oct 21 '13 at 22:20
  • @AshBurlaczenko I guess an iterative function might be more efficient than its recursive counterpart. – Terry Li Oct 21 '13 at 22:24
  • what is your A? is it 1..n? or something with clear increasing rate? – Saeed Amiri Oct 21 '13 at 22:40
  • @SaeedAmiri A is an array with n elements from index 0 to n-1. The value of each element is not known, but they are integers. – mblitz Oct 21 '13 at 22:43
  • Then just try an iterative way, your current recursion is inefficient. – Saeed Amiri Oct 21 '13 at 22:45
  • I think you may have chosen the wrong StackExchange site. If you aren't looking for an algorithm, you might have better luck on math.stackexchange.com – Tyler Bindon Oct 21 '13 at 22:47
  • Your question sounds kind of vague to me, but let me have a guess: are you looking for [tail recursion](http://stackoverflow.com/questions/33923/what-is-tail-recursion/33924)? – Terry Li Oct 21 '13 at 22:58
  • 1
    If each element `A[i]` is arbitrary, why do you expect you can find a closed-form formula for this algorithm with respect to `n`? The formula will be dependent to each element in the array, not just the length of the array. Probably you're trying to do weighted moving average? There is an efficient solution similar to this: http://www.daycounter.com/LabBook/Moving-Average.phtml – justhalf Oct 22 '13 at 01:24

3 Answers3

1

I would say the function you describe is simply

f(n) = sum (0 <= i < n: C^i * A[i])

which you could compute by

int c = 1;
int sum = 0;
for (int i = 0; i < n; i++) {
    sum += c * A[i];
    c *= C;
}
Vincent van der Weele
  • 12,927
  • 1
  • 33
  • 61
0
result=A[n-1];
for(count=1;count<n;count++)
{
    result=result*C+A[n-1-count];
}
return result;
Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
zubergu
  • 3,646
  • 3
  • 25
  • 38
0

Here's a solution in Java:

public static int[] f(int[] A) {
  int n = A.length();
  int[] result = int[n];
  result[0] = A[n-1];
  for (int i = 1; i < n; i++) {
    result[i] = result[i-1] + A[n-1-i];
  }
  return result;
}

Simply use a new array, and the translation from your original recursive algorithm is almost direct.

Carlos Salazar
  • 69
  • 7