recursive

[cougarclaws]

Is there an easier way to understand what this is doing step by step? I get very confused here, and I wonder if any of you fine people have a trick for breaking this down. I really want to get this, and understand the pattern, but what happens in the "else" return confuses me.

Thanks,

Cougarclaws

#include <iostream>
using namespace std;

float wk7recur (float value, int num)
{
      if (num == 0)
         return 1;
      else
          return ( value * wk7recur (value, num - 1) );
}
      
int main()
{
    
    float answer = wk7recur (1.0, 5);
    
    cout << answer;

   cout << endl << endl;
   system ("PAUSE");
   return 0;
   
}

[VernonDozier]

Is there an easier way to understand what this is doing step by step? I get very confused here, and I wonder if any of you fine people have a trick for breaking this down. I really want to get this, and understand the pattern, but what happens in the "else" return confuses me.

Thanks,

Cougarclaws

#include <iostream>
using namespace std;

float wk7recur (float value, int num)
{
      if (num == 0)
         return 1;
      else
          return ( value * wk7recur (value, num - 1) );
}
      
int main()
{
    
    float answer = wk7recur (1.0, 5);
    
    cout << answer;

   cout << endl << endl;
   system ("PAUSE");
   return 0;
   
}

The "else" is extraneous. Take it out and it's the exact same program. If the "if" statement is true, the function has already returned by the time the else statement is reached or anything potentially after the else statement is reached. Hence you can take "else" out if you wish.

The "if" part of the function is the base case, which you have to have in a recursive function or you'll never get out of it.

The example call is not a good one for understanding this function:

float answer = wk7recur (1.0, 5);

due to this line:

return ( value * wk7recur (value, num - 1) );

1.0 times anything is just itself, and the base case returns 1, so you're just going to get 1, no matter what you put for the second argument in this call. Change the first parameter to something besides 1.0.

Try replacing the call with some different lines like:

float answer = wk7recur (2.0, 3);    
    cout << answer << endl;
    answer = wk7recur (2.0, 2);    
    cout << answer << endl;
    answer = wk7recur (3.0, 3);    
    cout << answer << endl;
    answer = wk7recur (3.0, 2);    
    cout << answer << endl;
    answer = wk7recur (4.0, 3);    
    cout << answer << endl;
    answer = wk7recur (4.0, 2);    
    cout << answer << endl;

See if you see a pattern.

[cougarclaws]

Thank you very much! I do see that.

I guess what I am interested in is how the machine sees this to slove it. Is there a way to look at each call and understand it? It has been explained to me to be like a tree, first down, then back up. I have a few examples, but I am unclear.
Also, I am having trouble picturing the events that occur in the line after the else statement, no matter the value. I want to understand what is happening here when this executes. I created this to give me the answers, but it did not help me understand the recursive process itself.

I know I am asking much here, so I want to thank everyone in advance who responds....I may not have the mind for this, just want to try.

Thanks,

Cougarclaws

[Dave Sinkula]

Add some statements to display various parameters at key points in the function. For example,

float wk7recur (float value, int num)
{
   cout << "wk7recur(" << value << ", " << num << ")\n";
   if ( num == 0 )
   {
      cout << " num == 0\n";
      return 1;
   }
   cout << " num != 0\n";
   return( value * wk7recur (value, num - 1) );
}

[VernonDozier]

Thank you very much! I do see that.

I guess what I am interested in is how the machine sees this to slove it. Is there a way to look at each call and understand it? It has been explained to me to be like a tree, first down, then back up. I have a few examples, but I am unclear.
Also, I am having trouble picturing the events that occur in the line after the else statement, no matter the value. I want to understand what is happening here when this executes. I created this to give me the answers, but it did not help me understand the recursive process itself.

I know I am asking much here, so I want to thank everyone in advance who responds....I may not have the mind for this, just want to try.

Thanks,

Cougarclaws

As Dave says, add some cout statements (and some pauses). I changed the program a little. If you don't know what the stack is yet, it may be confusing, but hit RETURN every time it pauses and read the output.

#include <iostream>
using namespace std;


int currentStack = 1;

float wk7recur (float value, int num)
{
      cout << "Top of wk7recur with (" << value << ", " << num << ") parameters." << endl;
      if (num == 0)
      {
         cout << "Base condition reached.  Returning 1." << endl;
         cin.get ();
         return 1;
      }
      else
      {
         cout << "Calling wk7recur recursively.  value = " << value;
         cout << ", currentStack = " << currentStack << endl;
         cin.get ();
         currentStack = value * currentStack;
         return value * wk7recur (value, num - 1);
      }
}
      
int main()
{    
    cout << "Calling wk7recur from main with (3.0, 6) parameters.";
    float answer = wk7recur (3.0, 6);    
    cout << "Back in main" << endl;
    cin.get ();
    cout << answer << endl;

    cin.get ();
    return 0;  
}

If you haven't learned how to use a debugger yet, they're invaluable. You're multiplying, taking the result, sticking it on the stack, multiplying by that result, sticking it on the stack, etc. A bit confusing, again, if you haven't learned about the stack. The important thing to note is that the function gets called 6 times before it hits the base case, and each time the stack value is three times as big as it was last time. There are some good recursion tutorials out there that explain step by step.

[mrnutty]

I think this is supposed to be a recursive pow() function.

[vmanes]

I think this is supposed to be a recursive pow() function.

Nope, it another commonly used function. Step through it.

One way you might examine what's happening, and get an understanding of recursion, is to get a bunch of small pieces of paper. Use a piece for each recursive call. On it, show the values coming in to instance of the function. If you're at the base case, copy it's return value to the piece of paper that came before, other wise, start the calculation. Where you come to another call to the function, start a new piece of paper on the -- wait for it -- stack! Show the modified values sent to that new instance, and keep going till you've reached the base case, then work your way back down through the papers. Eventually you'll get back to that original call, and you'll have the answer.

[VernonDozier]

I think this is supposed to be a recursive pow() function.

Nope, it another commonly used function.

It's not? Looks like it to me. I'm getting the same results as pow . Displays all zeroes in the following program.

#include <iostream>
#include <cmath>
using namespace std;


float wk7recur (float value, int num)
{
      if (num == 0)
         return 1;
      else
          return ( value * wk7recur (value, num - 1) );
}
      
int main()
{    
    cout << wk7recur (5.0, 4) - pow (5.0, 4) << endl;
    cout << wk7recur (7.0, 3) - pow (7.0, 3) << endl;
    cout << wk7recur (6.0, 2) - pow (6.0, 2) << endl;
    cout << wk7recur (8.0, 5) - pow (8.0, 5) << endl;
    cin.get ();
    return 0;   
}

[vmanes]

It's not? Looks like it to me. I'm getting the same results as pow . Displays all zeroes in the following program.

Oops, pulling head out of nether regions! I misread it as a factorial computation.

Recursive functions and time travel stories - reasons aspirin was invented.

[cougarclaws]

You all rock! I think I have it now. I can see what the lines are doing at each call!!

I have used my debugger a bit, and it helps too, but not like this!!!

Thank so much!

Cougarclaws