用std：：堆栈将Hermite多项式递归转化为解

Question

Hermite多项式由下列公式定义，其中n>0和x是实数：

​

我已经使用递归定义了一个解决方案：

int hermitPolynomial(int n, int x){
    if(n == 0){
        return 1;
    }
    if (n == 1){
        return x*2;
    }
    return 2*x*hermitPolynomial(n-1,x) + 2*(n-1)*hermitPolynomial(n-2,x);
} 

如何使用堆栈将函数转换为迭代解决方案？另外，使用堆栈将递归转换为迭代函数的基础是什么？

我设法将难度较小的递归(如Fibonacci)转换为迭代堆栈解决方案。

这是我尝试过的解决方案，但我没有想到一种跟踪"2x“和”2(n-1)“的方法：

int hermitPolynomialIter(int n, int x){
    std::stack<int> s;
    int result = 0;
    s.push(n);
    while(!s.empty()){
        int temp = s.top(); s.pop();
        if(temp == 1){
            result+=1;
        }
        else if(temp == 2){
            result+=2*x;
        }
        else{
            s.push(temp-1);
            s.push(temp-2);
        }
    }
    return result;
}

Answer 1

首先，让我注意到递推公式是

H_n(x) = 2xH_{n-1}(x) - 2(n-1)H_{n-2}(x)

(注意减号)。

这是一个解决方案，连同计算x=1和x=2上的第一个多项式的一个小测试。

#include <stack>
#include <iostream>

int hermitePolynomial(int n, int x)
{
  std::stack<int> s;
  if (n == 0)
    {
      return 1;
    }
  else if (n == 1)
    {
      return 2 * x;
    }
  else
    {
      s.push(1);
      s.push(2 * x);
      for (int k = 2; k <= n; ++k)
    {
      auto hermite_k_minus_1 = s.top();
      s.pop();
      auto hermite_k_minus_2 = s.top();
      s.pop();
      auto hermite_k = 2 * x * hermite_k_minus_1 - 2 * (k - 1) * hermite_k_minus_2;
      s.push(hermite_k_minus_1);
      s.push(hermite_k);
    }
      return s.top();
    }
}

int main()
{
  for (const int x : { 1, 2 })
    {
      std::cout << "Polynomials at x = " << x << std::endl;
      for (int i = 0; i < 5; ++i)
    std::cout << "H_" << i << "(" << x << ") = " << hermitePolynomial(i, x) << std::endl;
    }

  return 0;
}

看吧，住在Coliru。

其主要思想是在循环上迭代计算k-多项式，并在堆栈中保留2个最后多项式，即指数k-1和k-2的多项式。

Answer 2

提示：

注意，递归公式将Hn表示为前面的两个计算(即Hn-1和Hn-2)。因此，您可以只使用保存这些评估的两个变量(让H1和H2)来执行它，并在增加n时转移它们。

循环体读取

H0= 2 * X * H1 + 2 * (N-1) * H2;
H2= H1;
H1= H0;
N++;

以下不变量将保持不变：H1 = Hn-1 and H2 = Hn-2，用于所有迭代。

我让您了解如何初始化变量H0、H1和H2 (考虑N=2)。