Trouble with infinite recursion in function

I've been working since yesterday to get this function working, but its just not. I've tried everything. I'm using a function that has depth recursion. The output I get is very strange:

Im going in with depth: 8
Depth in builder: 8
Depth in builder: 7
Depth in builder: 6
Depth in builder: 5
Depth in builder: 4
Depth in builder: 3
Depth in builder: 2
Depth in build开发者_StackOverflow中文版er: 1
Depth in builder: 0
Depth in builder: 0
Depth in builder: 0
Depth in builder: 0
Depth in builder: 1
Depth in builder: 0
Depth in builder: 0
Depth in builder: 0
Depth in builder: 0
Depth in builder: 1

.....

and then it alternates between those 1's and 0's for ever. How can this be possible? This line shouldnt even display if depth is 0. Why does this just keep going and going?

In case you're wondering, the constructor for the node does not call again the builder. The constructor does not call any outside functions, so now way that its coming from there.

I'm not sure that it actually displays them forever; it might just go on for a while.

Your recursive function makes four recursive calls at each level and runs from depth 8 to depth 0. This means that there are a total of 4⁸ = 65536 recursive calls at the bottom, 4⁷ = 16384 calls at depth 1, etc. for a total of 87381 calls being made, and if each call prints out one line of text and does a memory allocation it wouldn't surprise me if it went on for a long time. Also, since you're taking the BMP by value, you're making a copy of the image on each iteration (unless it does something fancy internally), which would slow the whole process down even more.

As for why you're seeing 1 0 0 0 1 0 0 0, I think it's because every time you expand out a node at depth d, you'll fully expand out all of its children before you back up to level d - 1. This means that when you first try expanding out a node at depth 2, you'll expand out four nodes at level 1, each of which prints out 1 0 0 0, before you'll finish expanding out that node at depth 2 and go on to its sibling at depth 2 which will then print out 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 again.

In short, I'm not sure that this really is a bug in your code or just a very large number of recursive calls.

It's not an infinite recursion, but it will execute 87381 times for an initial depth of 8.

Try simplifying it down to just the recursive part so that you can see what's going on:

//
// builder.cpp
//

#include <iostream>

using namespace std;

void builder(int depth) {

    cout << "Depth in builder: " << depth << endl;

    if (depth <= 0) {
        return;
    }
    if (depth > 0) {
        builder(depth - 1);
        builder(depth - 1);
        builder(depth - 1);
        builder(depth - 1);
    }
}

int main(void)
{
    builder(8);
    return 0;
}

$  g++ -Wall builder.cpp -o builder
$  ./builder | wc -l
   87381

If you look at your code in it's simplest form (not actually doing anything, just for tracing):

void f(int depth)
{
   // print depth
   cout << depth << endl;
   if(depth <= 0)
      return
   else
   {
      // **FOUR** more calls to the recursive function.
      f(depth - 1);
      f(depth - 1);
      f(depth - 1);
      f(depth - 1);
   }
}

Now think of tracing through at depth 1, your output is 1 - 0 - 0 - 0 since each call to f(1) generates four calls to f(0). Now think of the output of f(2) - you would get 2 - <output of f(1) four times>. This pattern can be extended so your expected output is

Output(f(n)) =
                    n
                    Output( f(n-1) )
                    Output( f(n-1) )
                    Output( f(n-1) )

This resembles pre-order traversal. print depth at root node and then call recursively on its children (here 4.). Given that depth is 8 and branching factor is 4. at level 1 we have 4^1 nodes. at level 2 we have 4^2 at with depth 8 we have 4^8 nodes at bottom. therefore you can expect to see 4^8 0's being printed and 4^7 1's being printed etc.... it wont' be infinite. I think you should try with small depth per say 3 or 4 and the you will see that it terminates. I see no reason why it is infinite recursion.

Seems fine to me. It's not actually infinite. Look further down your output, eventually you'll see things like 210000, 310000, etc. You're calling the function 4 times for each pass where depth > 0.