Как вы реализуете рекурсивную функцию в функции в C ++?

Question

Я понимаю, как работают лямбда-функции. Проблема в том, что программа вызывает функцию recursiveFunction () до того, как компилятор определит, каким должно быть 'auto'. Дело в том, что это рекурсивная функция, поэтому сама функция находится в определении.

#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;
}

Я также реализовал это, используя класс с использованием шаблонов, на случай, если это приведет к возникновению проблемы.

Вот сообщение об ошибке:

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);

Спасибо!

Answer 1

ответил здесь :

Второй фрагмент работает в [dcl.spec.auto] / 10:

Если типсущность с неопределенным типом заполнителя необходима для определения типа выражения, программа некорректна.

Тип foo необходим для определения типа выражения foo в теле лямбды, но на тот момент вы еще не вывели тип foo, поэтому программа некорректна.

Дополнительные ссылки:

• лямбда-захват во время инициализациидолжна быть ошибка
• «переменная, объявленная с автоматическим спецификатором, не может появиться в своем инициализаторе»

Исправление: 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;
}

Answer 2

Если вы хотите избежать std::function, вы можете сделать (требуется C ++ 14 для общей лямбды):

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);
}

Демо

Answer 3

Пара возможных ответов:

1. тип-стирание;на самом деле вам не нужно знать тип функции recursiveFunction, достаточно просто закрепить ее подпись.

Так что вы можете просто обойтись без проблемного auto и связанного с ним вывода и пообещать знатьтип заранее.

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);
}

Если это был не просто упрощенный пример, вы, похоже, фактически не захватываете какое-либо состояние, поэтому вы можете просто использовать обычную рекурсивную функцию вместо лямбды.

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

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

Если лямбда-аспект был действительно важен, вы ищете "Y комбинатор". Что не очень просто в C ++, но что-то вроде:

#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;
}