/* The first of three files illustrating dynamic programming.  This 
   one uses recursion without dynamic programming, giving a run time
   that is O(2^T).  */

#include <iostream.h>

float R( int k, int T, float p) {  

  /*  Compute the probability of hitting 0 after T steps, starting
      at k now.  p is the probability that you go from k to k+1.
      1-p is the probability that you go to k-1.            */

   if ( T == 0 ) {  // If at the final time, you know the answer.

      if ( k == 0 ) return (float) 1; // The int -> float conversion may be 
                                      // automatic but let's be safe.  
      return 0;  // Don't need "else" because you wouldn't be here otherwise.

   }

 //     If T > 0, compute the consequences of the first step.

   return p * R( k+1, T-1, p) + ( 1-p ) * R( k-1, T-1, p); 

}

int main() {

  cout << "Here is a probability computed recursively... " << endl;
  cout << "   " <<  R( 0, 25, .6) << endl;
  cout << "How long did that take?" << endl;
}