Есть ли прок от рекурсии ?

Если проблема в том, что возникает stack overflow, то можно переписать через продолжения (Continuation Passing Style / CPS). Достаточно легко это делается на F# через монаду Async. Можно и на лиспе сворганить, но тут нужна аккуратность. Тогда стек уйдет в память.

Чем удобен F#, внутренний цикл for для суммы автоматически будет преобразован в функциональную форму через CPS. В общем, там всю нудную работу по переводу на язык продолжений сделают компилятор F# и стандартная библиотека.

Можно еще и хаскелевскую монаду Cont попробовать (родственница монаде Async из F#), если в исходной задаче возникает Stack Overflow.

Но запросто может статься, что решение через матрицы будет самым эффективным ;)

Не, хаскель, F# это все сложно для моего старого, зачерствевшего ума. Ладно, пусть будут матрицы. Просто хотелось сделать что нибудь, не как всегда, что можно показать другим и не краснеть.

Смотрите сами, но на F# это выглядит довольно просто. Может быть, слово монада пугает, но на по верхности там нет сложностей. Нужно написать почти «обычный» код на F#, завернув его в так называемое вычислительное выражение:

let f n1 n2 n3 = async {

   if n1 = -1 then return 0
   elif n2 = -1 then return 0
   elif n3 = -1 then return 0
   elif n1 + n2 + n3 = 100500 then return 0
   else

     let! x1 = f (n1 + 1) n2 n3
     let! y1 = f (n1 - 1) n2 n3

     let! x2 = f n1 (n2 + 1) n3
     let! y2 = f n1 (n2 - 1) n3

     let! x3 = f n1 n2 (n3 + 1)
     let! y3 = f n1 n2 (n3 - 1)

     return (x1 + n1 * y1) + (x2 + n2 * y2) + (x3 + n3 * y3)
}

Все волшебство заключено в return и let!. Изнутри там будут работать продолжения и хвостовая рекурсия.

В качестве информации.