Help to implement this equation with a recursive function:

  (A [i-20] * (A [i-19] * (A [i-18] * ... * (A [i-1] + B [i-1]) + B [i-2] ) + B [i-3]) + ... + B [i-20])
  • Why do you need recursion here? Horner's method is perfectly encoded iteratively, at the same time you do not load the stack. Or is it a learning task? - VladD
  • I am writing a lab on KMMM, I use this url to bring the matrix to a three-diagonal form, it seemed to me that it would be better to implement this ur-recursively, and how to do it iteratively? - Yura Kor'evikov
  • SO is not to do for you labs. First write your code, and if you have any questions about it - then ask. - Abyx

1 answer 1

Here is an iterative solution:

result = 1; for (int j = 1; j <= 20; j++) result = result * A[i - j] + B[i - j];

Recursion is not necessary in order not to hammer the stack in vain.

To warm up, here's a recursive solution:

 double GetResultRec(size_t minidx, size_t maxidx) { if (minidx > maxidx) return 1.0; return A[minidx] * GetResultRec(minidx + 1, maxidx) + B[minidx]; } double result = GetResultRec(i - 20, i - 1);

But the recursive, obviously supporting tail recursion:

 double GetResultTailRec(size_t minidx, size_t maxidx, double factor, double addend) { if (minidx > maxidx) return factor + addend; return GetResultTailRec( minidx + 1, maxidx, factor * A[minidx], addend * factor + B[minidx]); } double result = GetResultTailRec(i - 20, i - 1, 1.0, 0.0);

(Is there a simpler solution with tail recursion?)

  • That is, the use of recursion is not desirable when there is an opportunity to do this iteratively, right? - Yura Kor'evikov
  • Modern compilers know how to tail recursion , so the stack is not clogged, if you write correctly. But this is not C ++ - style, yes. - Athari
  • @ YuraKor'evikov: It depends on the language. Functional languages ​​like (and correctly know) recursion, there is a preferred option. Imperative languages ​​(for example, C ++) are better able to iterate (yes, they are ideologically closer), so it’s better to reduce them to iteration. - VladD
  • There is a simple and almost self-evident theorem that any recursion can be reduced to iteration (possibly with an additional stack). - VladD
  • @Athari: Nuuuuu ... Hoping that the compiler is smart is not worth it until the tail recursion is guaranteed by the standard. Because the conditions under which the compiler will apply tail call elimination depend on the compilation keys, the current day of the week, the phase of the moon, the direction of the wind, and the distance to Alpha Centauri. See, for example, a list of situations where C # does not apply it: blogs.msdn.com/b/davbr/archive/2007/06/20/… (this is not C ++, but still). - VladD