Pascal triangle calculation without using for/while loop

Question

I would like to generate Pascal pyramid data from a given data set that looks like this

Pyramid(1,2,3,4,5,6,7,8,9);

This is what I have been doing but it reaches only the second layer while I want it to recursively loop till the top.

template<typename T>
const T Pyramid(T a, T b)
{   
    return a + b;
}

template<typename T, typename ...A>
const T Pyramid(T t1, T t2, A...a)
{

    return Pyramid(t1, t2) + Pyramid(t2, a...);
}

Could you help me fill up the next layers ? ;)

Answer 1

C++17

Here is the C++17 solution (using fold expressions):

#include <iostream>
#include <stdexcept>
#include <utility>


using Integer = std::uint64_t;


constexpr auto Factorial(const Integer n)
{
    Integer factorial = 1;

    for (Integer i = 2; i <= n; ++i)
    {
        factorial *= i;
    }

    return factorial;
}

constexpr auto Binom(const Integer n, const Integer m)
{
    if (n < m)
    {
        throw std::invalid_argument("Binom: n should not be less than m");
    }

    return Factorial(n) / Factorial(m) / Factorial(n - m);
}

template <Integer... indices, typename... Types>
constexpr auto PyramidImplementation(std::integer_sequence<Integer, indices...>, Types... values)
{    
    return ((Binom(sizeof...(values), indices) * values) + ...);
}

template <typename... Types>
constexpr auto Pyramid(Types... values)
{
    return PyramidImplementation(std::make_integer_sequence<Integer, sizeof...(values)>{}, values...);
}

// ...

constexpr auto pyramid = Pyramid(1, 2, 3, 4, 5, 6, 7, 8, 9);

std::cout << "Pyramid = " << pyramid << std::endl;

Live demo

This solution doesn't use the recursion, because the needed result for a[i] (i = 0 ... n - 1) can be calculated as a sum of binom(n, i) * a[i] (for i = 0 ... n - 1), where binom(n, m) is the binomial coefficient. The Binom function is implemented in the simplest way, so it will work only for small values of n.

C++14

The code can be made C++14-compatible via the following PyramidImplementation function implementation:

#include <type_traits>


template <Integer... indices, typename... Types>
constexpr auto PyramidImplementation(std::integer_sequence<Integer, indices...>, Types... values)
{
    using Do = int[];
    std::common_type_t<Types...> pyramid{};

    (void)Do{0, (pyramid += Binom(sizeof...(values), indices) * values, 0)...};

    return pyramid;
}

Live demo