Binomial coefficient using tail recursion/an accumulator in Prolog

Question

Is there any way to program calculation of C(n,k) using tail recursion/an accumulator in Prolog? I can't figure out how to "reverse" classic recursive formula C(n,k) = C(n-1,k-1) + C(n-1, k). Maybe, there are some other ways to do it?

Answer 1

You can do this whith normal recursion, I found this answer thanks to Omri Barel's answer on the Pascal's triangle which is closely related to the binomial coefficient.

c(N,K,Out):-calc(N,K,1,0,Out),!.

calc(_,K,Out,K,Out).
calc(N,K,Prev,Count,Out):-
    C2 is Count+1,
    NewPrev is Prev*(N-Count)/C2,
    calc(N,K,NewPrev,C2,Out).

When you generate the pascal's triangle and consider it as a 2 dimensional matrix PT with a zero based index. C(n,k) is equal to PT(n,k).

So to find C(n,k) you can generate the n-th row of the triangle and find th k-th index. You don't actually need tail recursion since to calculate the (k+1)-th index of a Pascal's row you only need to know the value of the k-th index.(which is labeled as Prev)

Edit: In order to finish OPs homework, this version makes explicit use of an accumulator and tail recursion.

c(N,K,Out):-calc(N,[1],List),
    elemAt(K,List,Out).

calc(N,[H|T],Out):-length(T, N),
    Out = [H|T],!.
calc(N,[H|T],Out):-
    length(T, Length),
    X is H*((N-Length)/(1+Length)),
    RX is round(X),
    calc(N,[RX|[H|T]],Out).

elemAt(0,[H|_],H).
elemAt(K,[_|T],Out):-
    K2 is K-1,
    elemAt(K2, T, Out).