Skip to main content
GameDev.net gamedev.net
🔒 Locked

Simulating recursion

Started by Gage64 Dec 8, 2008 at 2:22 PM 23 replies 8.2k views
Original Post
Gage64
Gage64
I have the following function: 
int binomial(int n, int k) {
    if (n < k)
        return 0;
    
    if (k == 0)
        return 1;

    int result1 = binomial(n-1, k);
    int result2 = binomial(n-1, k-1);
    return result1 + result2;
}
I want to write an iterative version that simulates the recursion in that function. After reading through some stuff and trying to visualize how the compiler does this, I came up with this: 

const int GARBAGE = -999999;


enum Location {
    START,
    AFTER_FIRST,
    AFTER_SECOND,
};


struct StackFrame {
    int n, k;
    int result1, result2;
    Location returnAddress;

    StackFrame(int nn, int kk, Location ra, int res1 = GARBAGE, int res2 = GARBAGE)
        :n(nn), k(kk), returnAddress(ra), result1(res1), result2(res2) {}
};


int binomialIter(int an, int ak) {
    stack<StackFrame> stk;
    stk.push(StackFrame(an, ak, AFTER_SECOND));
    Location currLine = START;
    int returnValue = GARBAGE;

    while (!stk.empty()) {
        switch (currLine) {
            case START: {
                StackFrame &curr = stk.top();
                if (curr.n < curr.k) {
                    returnValue = 0;

                    currLine = curr.returnAddress;
                    stk.pop();
                } else if (curr.k == 0) {
                    returnValue = 1;

                    currLine = curr.returnAddress;
                    stk.pop();
                } else {
                    stk.push(StackFrame(curr.n-1, curr.k, AFTER_FIRST));
                    currLine = START;
                }

                break;
            }

            case AFTER_FIRST: {
                StackFrame &curr = stk.top();
                
                curr.result1 = returnValue;
                stk.push(StackFrame(curr.n-1, curr.k-1, AFTER_SECOND, curr.result1));
                currLine = START;

                break;
            }

            case AFTER_SECOND: {
                StackFrame &curr = stk.top();

                curr.result2 = returnValue;
                returnValue = curr.result1 + curr.result2;

                currLine = curr.returnAddress;
                stk.pop();

                break;
            }
        }
    }

    return returnValue;
}
This seems to work, but I think that I'm performing some redundant operations and that there's a simpler way to do this. The reason is that the iterative version is much slower than the recursive one. I counted the number of recursive calls in the first function and the number of loop iterations in the second function, and the latter is always much larger than the former, but shouldn't they be the same? How can I improve this implementation? Thanks in advance.
Aressera
Aressera
you're over-thinking the problem. Just use the definition of the binomial distribution:
Bin(n,k) = n!/(k!(n-k)!)

My code for this:
int binomialIter( int n, int k ){	int nMinusK = n - k;		// compute the numerator of the binomial distribution	int numerator = 1;		for ( int i = 2; i <= n; i++ )		numerator *= i;		// compute the denominator of the binomial distribution	int denominator = 1;		for ( int i = 2; i <= k; i++ )		denominator *= i;		for ( int i = 2; i <= nMinusK; i++ )		denominator *= i;		return numerator / denominator;}
Perost
Perost
The binomial coefficient is usually defined as
   n!--------k!(n-k)!

So if you wanted to you could just calculate each of those factorials with a loop. Otherwise, why would you want to write an iterative version of that function? I can't see any point in doing that, unless you're trying to understand something about recursion.

Edit: Too slow...
Sneftel
Sneftel
Quote:
Original post by Gage64
How can I improve this implementation?

A dynamic programming approach is likely to be more straightforward than a stack-based mechanical transformation. In this case, that basically equates to computing the first n levels of Pascal's triangle into a 2D array. Quick, simple (especially if you don't sweat the 2X memory overhead from representing the array as rectangular instead of triangular), and effective.

EDIT: Oh. Well, if you must use a stack, I would suggest that going straight to quicksort is probably simpler. The reason is, the recursive quicksort calls don't return any values: they just shuffle stuff around in the array. That's going to be a heck of a lot simpler; all you need is a stack of the parameter lists.
KulSeran
KulSeran
1) if you are going to use the binomial sugestions from above, you are better off looking at the fact that
n! / k! has k terms that cancel out, using this fact turn it into
numerator = 1;denominator = 1;for ( int i = nMinusK+1; i <= n; i++ )  numerator *= i;for ( int i = 2; i <= nMinusK; i++ )  denominator *= i;return numerator / denominator;


2) for quick sort you could just cheat and look at what std::sort does.
ToohrVyk
ToohrVyk
You have the general idea down, but you can do some optimizations (for instance, tail recursion). Check this out.
Blog — Facebook
johdex
johdex
Maybe you already have, but I would suggest tackling these problems first:
- Turn a tail-recursion into a loop
- Turn a linear recursion (which is not tail-recursive) into a loop
- Turn a non-linear recursion into a loop

An example of the first:

int int_op(int, int);int aux(int n, int result){   if (n == 1) return result;   return aux(n - 1, int_op(n, result));}


An example of the second:

std::string rev(std::string s){  if (s.empty()) return "";  return rev(s.substr(1, s.length()-1) + s[0];}


You already have an example of the third problem.
-- Top10 Racing Simulation needs more developers!http://www.top10-racing.org
Gage64
Gage64
Quote:
Original post by ToohrVyk
You have the general idea down, but you can do some optimizations (for instance, tail recursion). Check this out.


Thanks, but even without optimizations, should the iterative solution really be that slower than the recursive one? And should the number of loop iterations really be that much larger than the number of recursive calls? I mean, if I'm properly simulating what the compiler is doing, shouldn't they be the same?
Antheus
Antheus
Quote:
Original post by Gage64

Thanks, but even without optimizations, should the iterative solution really be that slower than the recursive one? And should the number of loop iterations really be that much larger than the number of recursive calls? I mean, if I'm properly simulating what the compiler is doing, shouldn't they be the same?


Yes, it's possible. You're using std::stack which may require additional copy for each "function call".

IMHO, this is one case where generic algorithm and its safety considerations may be sub-par choice. Ideally, you'd use stack-allocated buffer and manage it manually.
State stack[500];int sp;while (sp > 0) {  stack.x = 10;  stack.y = 20;  sp++;  ...};


While in general case std based algorithms compile into fairly minimalistic code, their algorithmic constraints remain. In this case you might be bringing in checked iterators, copy behavior and allocation space checks.

Function call has none of those.

In case of quicksort that properly handles degenerate case, the maximum stack space can be accurately determined, eliminating possibility of overflow.

Buttom-up equivalent of some recursion calls is also a for loop, so properly detecting those cases helps. While there might exist methods, recursive-iterative conversion is not necessarily straight-forward or even necessarily viable.
Gage64
Gage64
Antheus: Those are good points and may explain the difference in speed. However, they don't explain why the number of loop iterations is so large.

Actually, I just ran it a few more times, and the number of loop iterations is always twice the number of function calls minus one. For example, for n = 9 and k = 7 there are 239 function calls and 477 loop iterations. I guess yesterday I was too tired to notice this...

Can anyone explain this behavior?
DevFred
DevFred
Quote:
Original post by Gage64
if I'm properly simulating what the compiler is doing

But you aren't. Recursive function calls (and also non-recursive function calls) are compiled into instructions that use the hardware stack, like push, pop, enter, leave, call, ret. What you are doing is using a data structure stack, and while those things are akin, they are not the same.

Pushing onto the hardware stack is one machine instruction. Pushing onto your simulated stack is a lot more complicated.
Gage64
Gage64
Quote:
Original post by DevFred
Quote:
Original post by Gage64
if I'm properly simulating what the compiler is doing

But you aren't. Recursive function calls (and also non-recursive function calls) are compiled into instructions that use the hardware stack, like push, pop, enter, leave, call, ret. What you are doing is using a data structure stack, and while those things are akin, they are not the same.

Pushing onto the hardware stack is one machine instruction. Pushing onto your simulated stack is a lot more complicated.


That's basically what Antheus said, and while it might explain the difference in speed, it doesn't explain the difference in the number of "executions" (see my previous reply).
popsoftheyear
popsoftheyear
For the difference in number of "executions". You think they are different but they are not. They are the same :)

Let's take the simplest example with the parameters 2, 1.

Your recursive version will be called 5 times. It will reach the recursive code twice, resulting in 4 additional calls:
Initial call, Recursive call 1A, Recursive call 2A, Recursive call 2B, Recursive call 1B.

Your stack implementation will do the same thing. The thing is you can only count an "execution" as the number of times you hit the "Start" case. I assume this is the only time you count an execution in the recursive function, right??? By counting an execution as each time through your while loop, you are also counting every time you recurse, which goes back into a start case (which should be the only time you count an execution). Thus you are counting each recursion twice. Looking above, this would give you an "execution count" of 9. But it really was only 5.

Cheers
-Scott
Gage64
Gage64
popsoftheyear: Looks like you hit the nail on the head. I tried counting the number of times I hit the START case and now the two counts are the same. But I don't really understand this part:

Quote:
By counting an execution as each time through your while loop, you are also counting every time you recurse, which goes back into a start case (which should be the only time you count an execution). Thus you are counting each recursion twice.


Could you please explain it a bit more?

Thanks a lot. This was really driving me crazy. [smile]
popsoftheyear
popsoftheyear
Well, let's reverse it. Having an "ExecCount++" at the beginning of your while loop (as opposed to in the "start" case) is the same as if you had an "ExecCount++" in each case - Start, After_First, and After_Second.

So, to simulate the same thing in your recursive function, you would "ExecCount++" at the beginning of the function, as well as right before the line "int result1 = binomial(n-1, k);" and right before the line "int result2 = binomial(n-1, k-1);".

Thus, every time you recurse, you'll be doing an "ExecCount++" twice. Once, right before calling, and once inside the start of the function.

-Scott
popsoftheyear
popsoftheyear
I think you'll find if you try something more like this:
struct StackFrame {	int n, k;	StackFrame(int nn, int kk)		: n(nn), k(kk) {}};int binomialIter(int an, int ak) {	stack<StackFrame> stk;	stk.push(StackFrame(an, ak));	int result = 0;	while (!stk.empty()) {		static int Count = 1;		std::cout << "Count: " << Count++ << "\n";		StackFrame curr = stk.top();		stk.pop();		if (curr.n < curr.k) continue;		else if (curr.k == 0) {			result ++;			continue;		}		stk.push(StackFrame(curr.n-1, curr.k));		stk.push(StackFrame(curr.n-1, curr.k-1));	}	return result;}


The "execution count" will come out right in a more intuitive way... and the function will be closer to outperforming the recursive version.
Gage64
Gage64
Thanks, your version is quite a bit faster (about 3 times faster), though if I change this:

StackFrame curr = stk.top();

to this:

StackFrame &curr = stk.top();

then it becomes really faster (about 30 times faster), and some other optimizations are probably possible.

I'm not sure I understand how it works, but is it always possible to do something like this, or is there something about this specific problem that allowed you to do this?
popsoftheyear
popsoftheyear
I have yet to see an example where this is not possible. The very nature of recursive functions would indicate that a stack based implementation like this is always possible. In fact I don't even write recursive functions any more (well ok occasionally, but only in the rare case it makes things more complicated)
[edit] And also don't forget a recursive function can overflow the call stack on your system, whereas you have more control over your own stack-based version, and can even base it off a dynamically sized array if need be.

Just follow the logic in it for a really basic example and you'll see it doesn't work any different from the function you posted. It's a direct translation.

Instead of practically creating a virtual machine with an pseudo-instruction pointer, I just tracked the data I cared about - this is all your recursive function is essentially doing.

[edit - read antheus post ...] Yeah the reference way will be undefined.

-Scott

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.