Рекурсивный спуск. С++

[Александр222]

Нужно было решить задачу методом динамического программирования(решение ниже). Кто-нибудь может рассказать о рекурсивном спуске? Где, что почитать. Потому что все, что я имею сейчас, это небольшой пример ниже.(Так как эту задачу теперь необходимо решить рекурсивным спуском)

UPD: Добавил решение с рекурсией данной задачи, но не уверен, что это можно назвать рекурсивным спуском

Безымянный.jpg

Решение методом динамического программирования:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;


double minPoly( const string &S, double x )
{
   int LEN = S.size();

   vector< vector< vector<double> > > P( LEN, vector< vector<double> >( LEN, vector<double>( LEN, 0.0 ) ) );

   for ( int i = 0; i < LEN; i++ ) P[i][i][0] = S[i] - '0';                   

   for ( int run = 2; run <= LEN; run++ )                                   
   {                                                 
      for ( int i = 0, j = i + run - 1; i <= LEN - run; i++, j++ )          
      {
         P[i][j][0] = 10 * P[i][j-1][0] + P[j][j][0];                         
         for ( int deg = 1; deg < run; deg++ )                             
         {
            P[i][j][deg] = P[i][i][0] + x * P[i+1][j][deg-1];                 
            for ( int c = i + 1; c < j - deg + 1; c++ ) P[i][j][deg] = min( P[i][j][deg], P[i][c][0] + x * P[c+1][j][deg-1] );
         }
      }
   }

   return *min_element( P[0][LEN-1].begin(), P[0][LEN-1].begin()+LEN );       
}


int main()
{
   string S;
   double x;
   cout << "Input S: ";   cin >> S;
   cout << "Input x: ";   cin >> x;
   cout << "Minimum polynomial is " << minPoly( S, x ) << '\n';
}

С использованием рекурсиии

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;


double minPoly( const string &S, int i, double P1, double P2, double x, double xpower )
{
   if ( i == S.size() ) return P1 + P2;
   int digit = S[i] - '0';
   double left  = minPoly( S, i + 1, P1     , 10 * P2 + xpower * digit, x, xpower     );
   double right = minPoly( S, i + 1, P1 + P2,   ( xpower * x ) * digit, x, xpower * x );
   return min( left, right );
}


double minPoly( const string &S, double x )
{
   return minPoly( S, 1, 0, S[0] - '0', x, 1 );
}


int main()
{
   string S;
   double x;
   cout << "Input S: ";   cin >> S;
   cout << "Input x: ";   cin >> x;
   cout << "Minimum polynomial is " << minPoly( S, x ) << '\n';
}