Recursive function to calculate 25% of the sum of what is returned before

Question

I'd like to write a recursive function that returns a double and takes an int as input.

If input == 1, return 1.
If input == 2 the function must return 1.25 (the sum of what was previously returned, multiplied by 1.25)
If input == 3 the function must return the sum of input = 2 and input = 1, multiplied by 1.25, therefore (1 + 1.25) * 1.25 = 2.8126
If input == 4 the output must be (1 + 1.25 + 2.8126) * 1.25 = 6.32825

etc etc

My attempt:

double _calc(int index) {
    if (index == 1) return 1;
    double tot = 0;
    tot += _calc(index -1);
    return tot * 1.25;
}

But the result is not what I expected.

I can achieve the correct result with a non recursive function:

double _calc(int index) {
    if (index == 1) return 1;
    if (index == 2) return 1.25;
    var tmp = [for(var i=0; i<index; i+=1) 0.0];
    tmp[0] = 1;
    tmp[1] = 1.25;
    for (int i=2; i<index; i++) {
        for (int j=i; j>=0; j--) {
            tmp[i] += tmp[j];
        }
        tmp[i] = tmp[i] * 1.25;
    }
    return tmp[index-1];
}

If it's possible, I'd like to get the correct result with a recursive function

Thanks in advance

Answer 1

That's because your recursive function only handles the output from the prior step; directly multiplying by 1.25

But your definition of the function must handle output from all previous steps. (sum them together), before multiplying by 1.25.

To do the "summing" of previous steps I added a for loop. Please note this function is inefficient as OP commented on my answer(like how a bad recursive Fibonacci is inefficient, described here):

  double _calc_bad(int index) {
    if (index == 1) {
      return 1;
    }
    double tot = 0;
    for (int i = 0; i < index; i++) {
      tot += _calc_bad(i);
    }
    return tot * 1.25;
  }

---

If you want to try a more efficient recursive function, you can use a technique described in Data Structures and Algorithms in Python (direct PDF link here; see page 189) which creates a good_fibonacci instead of a bad_fibonacci by remembering the previous call results

  // recursive function returns more information for next call
  (double, List) _calc_cache(int index) {
    if (index == 1) {
      return (1, []);
    } else {
      var (prev, list_of_prev) = _calc_cache(index - 1);
      list_of_prev.add(prev);
      // sum using https://stackoverflow.com/a/13611678/1175496
      return (1.25 * list_of_prev.fold(0, (p, c) => p + c), list_of_prev);
    }
  }

  double _calc_good(int index) {
    var (result, l) = _calc_cache(index);
    return result;
  }

The technique here is similar to @lrn's answer which caches the previous results in a global List object _fCache. I don't use a global variable; I return the variable inside the recursive function, which requires a different function signature. I made _calc_cache(), which returns a record of the result, and the list of previous results. You can destructure the record to return just the result if you want... (see the _calc_good function I made)

However, your simple use of for-loops, or @lrn's mathematical simplification of using pow(2.25, ...), might both more efficient approaches!

Examples of output:

_calc_good(1)
> 1
_calc_good(2)
> 1.25
_calc_good(3)
> 2.8125
_calc_good(4)
> 6.328125

Answer 2

The most direct implementation would be:

import "dart:math" show pow;
double f(int index) {
  if (index < 1) throw ArgumentError.value(index, "index", "Must be >= 1");
  if (index == 1) return 1;
  return pow(2.25, index - 2) * 1.25;
}

(You can prove that it gives the correct value of all index >= 2 by induction, but I'll leave that as an exercise for the reader. )

If you want to compute it using a recursive function, this is the kind of calculation which really benefits from caching.

List<double> _fCache = [0.0, 1.0];
double f(int index) {
  if (index < 1) throw ArgumentError.value(index, "index", "Must be >= 1");
  if (index < _fCache.length) return _fCache[index];
  double result = 0.0;
  for (var i = 1; i < index; i++) result += f(i);
  result *= 1.25;
  assert(_fCache.length == index);
  _fCache.add(result);
  return result;
}