How do you implement a recursive function in a function in C++?

Question

I understand how lambda functions work. The problem is that the program calls the function recursiveFunction() before the compiler has deduced what 'auto' should be. The thing is, it's a recursive function so the function itself is in the definition.

#include <iostream>
using namespace std;

template <class T>
class Class {
    public:
        int foo(int x);
};

template <class T>
int Class<T>::foo(int x) {
    auto recursiveFunction = [=](int n)->int {
        if (n <= 1) return 1;
        else return n*recursiveFunction(n-1);
    };
    return recursiveFunction(x);
}

int main() {
    Class<int> c;
    cout << c.foo(5) << endl;
    return 0;
}

I've also implemented this using a class using templates in case that factors into the problem.

Here's the error message:

main.cpp: In instantiation of 'int Class<T>::foo(int) [with T = int]':
main.cpp:21:20:   required from here
main.cpp:14:40: error: use of 'recursiveFunction' before deduction of 'auto'
         else return n*recursiveFunction(n-1);

Thanks!

I actually don't understand why you need to use `auto` instead of clearly write the type signature like `function`. I mean, when we made a recursive function we usually need to know what's the return so we could use that and call the function all over again, right? — wisn, Oct 02 '19 at 01:51
Upvoted because it came with a minimal example! (Especially noteworthy from a new contributor.) — Unapiedra, Oct 02 '19 at 01:52
@WisnuAdiNurcahyo Yes - I was thinking the same thing. I had no idea `function` existed... Thanks! — Sam Williams, Oct 02 '19 at 02:00

Unapiedra · Answer 1 · 2019-10-02T02:02:36.567

4

Answered here:

The second snippet runs into [dcl.spec.auto]/10:

If the type of an entity with an undeduced placeholder type is needed to determine the type of an expression, the program is ill-formed.

The type of foo is needed to determine the type of the expression foo within the lambda body, but at that point you haven't deduced foo's type yet, so the program is ill-formed.

Further references:

Fix: https://godbolt.org/z/np3ULe

#include <iostream>
#include <functional>

template <class T>
class Class {
 public:
  int foo(int x);
};

template <class T>
int Class<T>::foo(int x) {
  std::function<int(int)> fac = [&fac](int n) -> int {
    if (n <= 1)
      return 1;
    else
      return n * fac(n - 1);
  };
  return fac(x);
}

int main() {
  Class<int> c;
  std::cout << c.foo(5) << std::endl;
  return 0;
}

edited Oct 02 '19 at 02:02

answered Oct 02 '19 at 01:50

Unapiedra

15,037
12
64
93

Nitpick: should `fib` be `fact`? – LegendofPedro Oct 02 '19 at 02:03
Yes, @LegendofPedro, I caught that just a few seconds before you. Good find, though! – Unapiedra Oct 02 '19 at 02:04
Let's say Class had a private variable, say, `int p`. Would any changes need to be made to `std::function fac = [&fac](int n) -> int` if I wanted function `fac` to be able to use it? – Sam Williams Oct 02 '19 at 02:22
You can capture `int p` either by value or by reference. It's important that you capture `fac` by reference. But `p` can be captured by value (i.e. it gets copied into the function and does not update if the p in the class changes.). If you capture by reference, the `p` used inside the lambda and the p in the class will always be the same. – Unapiedra Oct 02 '19 at 02:32
Maybe more specific: `std::function fac = [&fac, p](int n) -> int` – Unapiedra Oct 02 '19 at 02:36
@Unapiedra Is capturing `this` a sloppy way of accomplishing the same thing? – Sam Williams Oct 02 '19 at 02:36
@SamWilliams, sorry I was wrong! Here is how it works https://godbolt.org/z/5Fed2s. And one link: https://stackoverflow.com/a/32922183/461597 requires C++14. Yes, capturing 'this' works but is sloppy (discouraged by many style guides) as it captures everything in the class. – Unapiedra Oct 02 '19 at 02:40

score 0 · Answer 2 · answered Oct 02 '19 at 02:49

Couple possible answers:

type-erasure; you don't actually need to know the type of recursiveFunction, just enough to have pinned down its signature.

So you could just do without the problematic auto and associated deduction, and promise to know the type in advance.

template <class T>
int Class<T>::foo(int x) {
    std::function<int(int)> recursiveFunction;
    recursiveFunction = [=](int n)->int {
        if (n <= 1) return 1;
        else return n*recursiveFunction(n-1);
    };
    return recursiveFunction(x);
}

If this wasn't just an oversimplified example, you don't appear to actually be capturing any state, so you could just use a normal recursive function instead of a lambda.

namespace {
    int recursiveFunction(int) {
        if (n <= 1) return 1;
        else return n*recursiveFunction(n-1);    
    }
}

int Class<T>::foo(int x) {
    return recursiveFunction(x);
}

If the lambda aspect was actually important, you're looking for the "Y combinator". Which is not very straightforward in C++, but something like:

#include <iostream>
#include <functional>

template <class T>
class Class {
    public:
        int foo(int x);
};

template<class F>
struct function_traits;

template<class R, class T>
struct function_traits<R(T)> {
    typedef R return_type;
    typedef T arg_type;
};

// function pointer
template<class R, class... Args>
struct function_traits<R(*)(Args...)> : public function_traits<R(Args...)>{}};

template <typename Signature>
auto y (std::function<typename function_traits<Signature>::return_type(typename function_traits<Signature>::arg_type, std::function<Signature>)> f) 
    -> std::function<Signature>
{
    return [f](typename function_traits<Signature>::arg_type n) -> typename function_traits<Signature>::return_type { return f(n,y(f)); };
}

template <class T>
int Class<T>::foo(int x) {
   return y<int(int)>([=](int n, auto recursiveFunction) -> int {
        if (n <= 1) return 1;
        else return n*recursiveFunction(n-1);    
    })(5);
}

int main() {
    Class<int> c;
    std::cout << c.foo(5) << std::endl;
    return 0;
}

Y-combinator doesn't requires type erasure from `std::function` though. — Jarod42, Oct 02 '19 at 09:55
It shouldn't, but I couldn't figure out how to express the trailing return type without it (deduction won't work since the return expression mentions y. — puetzk, Oct 08 '19 at 02:44
Something like that: [Demo](http://coliru.stacked-crooked.com/a/6217a4c2025b6955). — Jarod42, Oct 09 '19 at 13:06

score 0 · Answer 3 · answered Oct 02 '19 at 09:53

If you want to avoid std::function, you might do (requires C++14 for generic lambda):

int Class<T>::foo(int x) {
    auto recursiveFunction = [](auto recFunc, int n) -> int
    {
        if (n <= 1) return 1;
        else return n * recFunc(recFunc, n - 1);
    };
    return recursiveFunction(recursiveFunction, x);
}

Demo

How do you implement a recursive function in a function in C++?

3 Answers3