Accumulator passing style in C++

Question

I'm trying to emulate (in C++) the accumulator passing style that I learned in SICP (Structure and Interpretation of Computer Programs by Abelson/Sussman). They used Scheme for the their implementations, although the same idea works in other languages that support higher-order functions. For example, here is the factorial function using accumulator passing style in Python:

def fac(n):
    def facAcc(i, acc):
        if (i == n): 
            return acc
        else:
            return facAcc(i+1, (i+1)*acc)

    return facAcc(0, 1) # 0! = 1

>>> list(map(fac, range(0,6))) 
[1, 1, 2, 6, 24, 120]

Since C++ supports lambdas, it seems like it should be possible to do the same thing in C++. I tried that but could not get g++ to compile the recursive lambdas.

Answer 1

Not sure why you insist on having a lambda, but here's one version with your inner function as a lambda:

#include <iostream>
#include <functional>

long long fac(int n)
{
    std::function<long long(int, long long)> facAcc;
    facAcc=[n, &facAcc](int i, long long acc) -> long long {
        if (i==n)
        {
            return acc;
        }
        else
        {
            return facAcc(i+1, (i+1)*acc);
        }
    };

    return facAcc(0, 1);
}

int main()
{
    for (int i=0; i<6; i++)
    {
        std::cout << fac(i) << '\n';
    }
}

stieber@gatekeeper:~ $ g++ Test.cpp && ./a.out
1
1
2
6
24
120

---

You can, in many cases, simulate local functions by wrapping them into a class. Compared to lambdas, you loose the capture ability:

#include <iostream>

long long fac(int n)
{
    class FacAcc
    {
    public:
        static long long facAcc(int n, int i, long long acc)
        {
            if (i==n)
            {
                return acc;
            }
            else
            {
                return facAcc(n, i+1, (i+1)*acc);
            }
        }
    };

    return FacAcc::facAcc(n,0,1);
}

int main()
{
    for (int i=0; i<6; i++)
    {
        std::cout << fac(i) << '\n';
    }
}

which, of course, you could simulate with actually using the class as such:

#include <iostream>

long long fac(int n)
{
    class FacAcc
    {
    private:
        const int n;

    public:
        FacAcc(int n_) : n(n_) { }

    public:
        long long operator()(int i, long long acc) const
        {
            if (i==n)
            {
                return acc;
            }
            else
            {
                return (*this)(i+1, (i+1)*acc);
            }
        }
    };

    return FacAcc(n)(0,1);
}

int main()
{
    for (int i=0; i<6; i++)
    {
        std::cout << fac(i) << '\n';
    }
}

But, just for completeness, it's weird way to do a recursive factorial. While I would never do it recursively, the easier way is to simply...

#include <iostream>

long long fac(int n)
{
    return (n==0) ? 1 : n*fac(n-1);
}

int main()
{
    for (int i=0; i<6; i++)
    {
        std::cout << fac(i) << '\n';
    }
}