Thread: Can some one please explain this recursion function to me.

I don't understand this simple function that come directly out of the book: Jumping into C++. It is supposed to be a recursive function.

First this function starts out with an unknown (int height), then it uses the if statement to compare the height to zero. Then (I believe it calling itself ?) and (then subtract 1 from the height ?) Until the height is zero? After this is true... Then it addBrickLayer.

Is my explanation right or wrong?
Why wouldn't you just start a wall from the ground rather then decrease the height? This does not make any sense to me.
One final question. Is (height-1) sent backs to (int height) as the argument?

Code:

void buildWall (int height) 
{ 
if ( height > 0 ) 
{ 
buildWall( height - 1 ); 
}
addBrickLayer(); 
} 

buildWall doesn't do anything except call itself until height <= 0, creating a stack of instances of calls to itself with decreasing values of height as a parameter. Only when an instance where the input parameter is 0, does buildWall start adding layers, then it returns to the previous instance, adds another layer, ... until it gets back to the original instance to add the final layer. So the layers are added bottom up. Note that it adds at least one layer (if height <= 0, it doesn't call itself, but it does add one layer).

In the real world you don't have a wall of any height and then continually subtract 1 from it until the height <=0. Then addBrickLayer to it. The author could have simply said this is not normally done. That's why the function didn't make any sense to me in the first place walls are not built that way. I guess the Designer in me could not pick up the logic.

Originally Posted by papagym177

In the real world you don't have a wall of any height and then continually subtract 1 from it until the height <=0. Then addBrickLayer to it.

Imagine you have a bunch of sheets of paper, the first sheet has the height on it, you place that sheet on a table face up. Then on the next sheet, you write the height - 1 from the first sheet, then place that sheet face up on the table. Then on the third sheet you write the height - 1 from the second sheet and place that sheet face up on the table. Eventually you write zero on a sheet and place it face up on the table. Then you start building the wall. The first sheet shows height 0 and you build a wall layer. You remove that sheet and the second sheet shows a height of 1 and you add another layer, you continue doing this until you run out of sheets. You end up building a wall with one more layer than the height. So the order of building the wall is normal, but the order of placing the sheets face up on the table is done backwards.

Thanks rcgldr and Elysia,
Both of your explanations are very good and easy to understand, but I'm still missing something here! What keeps track of the number of time that (height - 1) was subtracted and how does addBrickLayer () know how may layers to add back? This function has closed brackets after it, so I wouldn't think is gets any parameter. Does the Compiler do this???

Originally Posted by papagym177

What keeps track of the number of time that (height - 1) was subtracted?

The stack. Each time build wall calls itself, it pushes the value height-1 onto the stack, and then calls itself, which pushes the return address onto the stack (and any registers that need to be saved get pushed onto the stack at the start of build wall). So using height = 4 as an example, and ignoring saved registers, beginning with the call from main, the stack will contain 4, return address (to main), 3, return address (to build wall), 3, return address, 2, return address, 1, return address, 0, return address.

Originally Posted by papagym177

how does addBrickLayer () know how may layers to add back?

It doesn't. It only adds one layer to the wall. Just before build wall returns, it calls addbricklayer to add one layer to the wall. It's like the sheets of paper example I posted before. The guy working with the sheets doesn't need to know how many sheets were used, only that each time he removes a sheet from the stack of sheets, he adds one layer to the wall.

Thanks rcgldr, I just read the same thing on Learn C++, The numbers are first push onto the call stack then popped of to unwind it. It would have been nice if the author would have said this in the first place. Then we would not have to go through this.

Originally Posted by rcgldr

Each time buildWall calls itself, it pushes the value height-1 onto the stack

Originally Posted by Elysia

This is not guaranteed. The C++ standard says nothing about this, and indeed, some compilers do not always do this.

I used a simplified example. Instead of passing height on the stack, it could be passed in a register, and an optimizing compiler could detect that there's no need to ever save the height value on the stack since it's not used after the return from a recursive call to buildWall. So in this case, there are no instances of height saved on the stack, only the return addresses would be saved on the stack, and the register used to hold the height parameter would just get decremented with each recursive call. I don't know if a really clever optimizer would completely eliminate the recursion and simply call addBrickLayer() height+1 times.