recursion

[lulipeng]

I have trouble in programming with recursion!
It seems beyond me.It so hard to figure out the expression.
Can you give me some tips to help me out?
Thank you a million.

[Telion]

It's much easier if someone tells you what the recursive function is supposed to do. Assume that the recursive call does exactly what they said the function would do, and then just make sure that everything makes sense.

For example, you would probably have a hard time figuring this out:

int f(int n)
{
    return n > 4 ? f(n / 2 + 1) : n;
}

If I write a function that serves a real purpose, it makes a bit more sense:

int huh(int n)
{
    if(n == 0 || n == 1) return 1;
    return n / huh(n - 1)
}

Now if I tell you that this function is the same as factorial, but backwards and with division instead of multiplication, does it make sense? Just assume that huh(n - 1) does what it is supposed to do, and then you only have to analyze a 2-line function.

[hanst99]

The idea behind recursion is usually "I can solve this large problem if I solve a smaller problem first".

For example, the factorial (n! = 1*2*3*4*..*n) is too hard for us to calculate. But if we had the factorial (n-1)!, we could just multiply it with n to get n!. But (n-1)! is still too hard - we can get this by multiplying (n-1) with (n-2)!. That way we reduce the problem to calculate smaller and smaller factorials until we end up at 1! (or 0! - both are 1). That's of course just an example, and the 'reduction' is sometimes hard to see. But the usual pattern is:

I have a hard problem that I want to solve. I can solve it by solving a slightly easier problem first. Also, there is a trivial problem that I can solve immediately, and which I am certain all other problems in the class can be reduced to.

That's not necessarily the only application of recursion, but this is what you will encounter most of the time. It's vital that there is always a condition to stop the recursion, just like there needs to be a condition to stop a loop from continuing indefinitely.

[lulipeng]

Hi,Telion,
Thank you.You reply helps me a lot.As you said,i should focus on the function
itself.
like this example:
int huh(int n)
{
if(n == 0 || n == 1) return 1;
return n / huh(n - 1)
}

focus on the two lines in the function.As to the huh(n-1),it just a call.

[lulipeng]

hi,hanst99,

It makes sense,but the true problem is i can not control the function.That is the calls is so complicated .
Maybe i should learn something about function call to figure out what are perpared when a function is called.
Thank you!

[Duthomhas]

The trick with recursion is that there are several things you are keeping track of:

1 - the return value. This can be combined by using some operation between a value and another invocation, or by passing a modified version of it as argument to the invocation.

2 - the control arguments. This is how you keep track of what is happening.

Here is a loop that prints 1 to 10:

for (int n = 1; n <= 10; ++n)
  cout << n << endl;

Recursively, there is no result, and the control argument is the number n:

void print_range( int n, int max_n )
  {
  cout << n << endl;
  if (n < max_n)
    print_range( ++n, max_n );
  }

print_range( 1, 10 );

When you want to create something, like a list, it helps to have an argument to keep it:

vector <int> ns;
for (int n = 1; n <= 10; ++n)
  ns.push_back( n );

Recursively:

void generate_range( int n, int max_n, vector <int> & ns )
  {
  ns.push_back( n );
  if (n < max_n)
    generate_range( ++n, max_n, ns );
  }

vector <int> ns;
generate_range( 1, 10, ns );

This last example shows something. There are two objects named 'ns': the one that the function works on, and the reference argument. I could, conceivably, made 'ns' global and just referred to it directly, but by using a reference argument I can modify any vector I want.

The other way is by modifying it -- directly through return values -- is tricky. You have to keep in mind exactly when a thing is modified, and how to modify it properly. I recommend you avoid it for now and stick with reference arguments.

This last function is called a 'generator', because it creates a thing.
Another type is called a 'consumer', because it eats something up:

int sum = 0;
int values[] = { 1, 2, 3, 4, 5, 6, 7 };
for (int n = 0; n < 7; ++n)
  sum += values[ n ];

Recursively:

int sum_list( int n, int size, int* values )
  {
  if (n < size)
    return values[ n ] + sum_list( n + 1, size, values );
  else
    return 0;
  }

int values[] = { 1, 2, 3, 4, 5, 6, 7 };
int sum = sum_list( 0, 7, values );

Hopefully you should be able to get your head around this one if you followed the last two. So long as the index into the list ('n') is less than the size of the list (the same thing we do in the loop), we add the indexed element into the result, and add the sum of the remainder of the list.

Hence, we are really saying:

    sum = (1 + (2 + (3 + (4 + (5 + (6 + (7 + 0))))))));

One last thing to notice: when using recursion we often have to have a lot more arguments to our functions than we would think we would. (In actuality, we use the same arguments in our loops, but since we only say them once, it seems odd to have to repeat them over and over in the recursion.)

Well, I hope this helps somewhat.

[lulipeng]

Hi duoas,

Thanks a million.I appreciate it.