Help in understanding this program

[icoolguy1995]

Hi,

I wanted to know how this program actually works:

unsigned int f1(unsigned int a, unsigned int b)
{
if (a == 0)
return b;
else if (b == 0)
return a;
else return f1(a, b-1) + b;
}

For example, how does it returns 24, when a = 3 and b = 6? Specifically what number it generates with the statement f1(a, b-1)?

[lastchance]

f(3,6)
= f(3,5) + 6
= f(3,4) + 5 +6
= f(3,3) + 4 + 5 + 6
= f(3.2) + 3 + 4 + 5 + 6
= f(3,1) + 2 + 3 + 4 + 5 + 6
= f(3,0) + 1 + 2 + 3 + 4 + 5 + 6
= 3 + 1 + 2 + 3 + 4 + 5 + 6
= 24


I should think it does the same as

unsigned int f1(unsigned int a, unsigned int b)
{
   return a == 0 ? b : a + b * ( b + 1 ) / 2;
} 

[JRManx]

Here is your function (not program, function), formatted so it's easier to read:

unsigned int f1 (unsigned int a, unsigned int b)
{
	if (a == 0)
		return b;
	else if (b == 0)
		return a;
	else 
		return f1 (a, b-1) + b;
}

Oh no, I hate function recursion...

At least, that's what this looks like. Where the function calls itself, and then you have a whole lovely loop of junk going back and forth until you can't tell which is which.

It's like looking in a mirror with another mirror behind you, and you can just keep looking at yourself looking in a mirror at yourself looking in a mirror at yourself looking in a mirror...Ugh.

So, if you call the function in main (or in another function), e.g.

unsigned number = f1 (3, 6);

then what it does is
1. It passes 3 and 6 to the function
2. The function reads the numbers, and neither "a" nor "b" == 0
3. So it goes to the "else"
4. And calls itself, passing 3 and 5
5. Then it does steps 2 and 3 again
6. And calls itself, passing 3 and 4 this time.
7. Then it goes on, and on, and on, and on for all of bloody eternity.

I'm actually getting a headache just trying to figure out how in the heck this even works.

Unless the unsigned return type has something to do with it. Maybe it stops it somewhere along the way; when "b" reaches 0 or something like that.

Edit:
@lastchance,
Yeah, something like that. Just ran it in my debugger using step-in, and that's what it looks like it does. Goes through it a bunch of times and then returns b = 0, so then it returns a, and does a bunch of other stuff that I didn't understand, and output 24.

Sorry about the rant, I just don't like recursive functions because of the repeating aspect. It's just confusing (and it can be very easy to get an infinite running if you do something wrong).

[dhayden]

To understand recursion, sometimes it helps to add code to show when the program enters and leaves the function:

#include <iostream>
#include <cstdlib>

using std::atoi;
using std::cout;

unsigned int f1(unsigned int a, unsigned int b)
{
    unsigned result;
    cout << "Entering f1(" << a << ',' << b << ")\n";
    if (a == 0)
	result = b;
    else if (b == 0)
	result = a;
    else result = f1(a, b-1) + b;
    cout << "Leaving f1(" << a << ',' << b << "), Result = " << result << '\n';;
    return result;
}

int main(int argc, char **argv)
{
    if (argc > 2) {
	unsigned res = f1(atoi(argv[1]), atoi(argv[2]));
	cout << "\nf1(" << argv[1] << ',' << argv[2] << ") = " << res << '\n';
    } else {
	cout << "Usage: " << argv[0] << " arg1 arg2\n";
    }
}

$ ./foo 3 6
Entering f1(3,6)
Entering f1(3,5)
Entering f1(3,4)
Entering f1(3,3)
Entering f1(3,2)
Entering f1(3,1)
Entering f1(3,0)
Leaving f1(3,0), Result = 3
Leaving f1(3,1), Result = 4
Leaving f1(3,2), Result = 6
Leaving f1(3,3), Result = 9
Leaving f1(3,4), Result = 13
Leaving f1(3,5), Result = 18
Leaving f1(3,6), Result = 24

f1(3,6) = 24

agent max wrote:

It's just confusing (and it can be very easy to get an infinite running if you do something wrong).

After learning that the hard way several times, I started coding all my recursive functions with this basic pattern:

if (base case) {
    return base value;
} else {
    return recursive call;
}

This forces me to always consider the base case first. It also makes a clear distinction between the base and recursive cases.

[icoolguy1995]

Thank you all for explaining this piece of code.

[JRManx]

Hey, @dhayden, thanks! That really helped me understand recursive functions a little better!