Share via

Recursive Algorithm in C++

  • Article

Many recursive algorithms have initial parameters. For example, Fibonacci Number is defined as: Fn = Fn-1 + Fn-2, with F1 = F2 = 1.

By giving different values to F1 and F2, we can generate different sequence of numbers.

1. If we implement the algorithm using functions, we have to either define these parameters as global variables or pass them in each recursive iteration.

int Fib(int n, int f1, int f2)
{
    if (n < 1) return 0;

    if (n >= 3) {
        return Fib(n - 1, f1, f2) + Fib(n - 2, f1, f2);
    } else if (n == 2) {
        return f2;
    } else {
        return f1;
    }
}

2. Recursive functor can store the initial parameters as the class data member. Here is the example.

struct FibFunctor
{
    FibFunctor(int f1, int f2) : m_f1(f1), m_f2(f2) {}
    int m_f1, m_f2;

    int operator()(int n) const {
        if (n < 1) return 0;

        if (n >= 3) {
            return (*this)(n - 1) + (*this)(n - 2);
        } else if (n == 2) {
            return m_f2;
        } else {
            return m_f1;
        }
    }
};

int Fib(int n, int f1, int f2)
{
    FibFunctor f(f1, f2);
    return f(n);
}

3. Lambda is a new core language feature introduced in C++0x to define implicit function object. However, "this" is not valid inside lambda expression.

This post Visual C++ Team Blog - Stupid Lambda Tricks shows how to write a recursive lambda. So the above functor can be rewritten as:

int Fib(int n, int f1, int f2)
{
    auto f = [&](int n) -> int {
        if (n < 1) return 0;

        if (n >= 3) {
            return f(n - 1) + f(n - 2);
        } else if (n == 2) {
            return f2;
        } else {
            return f1;
        }
    };
    return f(n);
}

Here, [&] is equivalent to [&f, &f1, &f2].

(According to C++03 3.3.1/1: "The point of declaration for a name is immediately after its complete declarator and before its initializer (if any).", it is legal to capture f in the lambda expression. That means:

struct A {
    A(A*);
};

int main()
{
    A a = A(&a); // OK
})

Comments