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? :confused:
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).

Example: BuildWall(3)
- height (=3) > 0 is true
-- Call BuildWall(3 - 1 = 2)
--- height (=2) > 0 is true
---- Call BuildWall(2 - 1 = 1)
----- height(=1) > 0 is true
------ Call BuildWall(1 - 1 = 0)
------- height (=0) > 0 is false
------- Call AddBrickLayer
------ Function end
----- Call AddBrickLayer
---- Function end
--- Call AddBrickLayer
-- Function end
- Call AddBrickLayer
Function end

A function calling itself is no different than calling some other function. You can think of every call to BuildWall as a call to another function. The arguments are passed to the function and it starts to execute. When it's finished, it returns to the function that called it and resumes executing the next statement after the function call.

This is a toy example. Yes, you can certainly build it beginning from height 0 if you want. You simply have to change the logic height > 0 to something like height < N (and the call to height + 1). It makes no difference.

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.

Quote:

---

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.

Quote:

---

Originally Posted by papagym177

The author could have simply said this is not normally done.

---

Recursion is actually quite common. You need to remember that the implementation of a software model of a physical activity is often quite different from its physical reality. Recursion is a perfectly legitimate way to model building a wall. Looping is also appropriate, and often more understandable to beginners.

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???

Quote:

---

Originally Posted by papagym177

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...

---

Each time the function is called, height - 1 is passed to it.
Consider 4 exactly like functions a, b, c and d. Then the example becomes:

Example: a(3)
- height (=3) > 0 is true
-- Call b(3 - 1 = 2)
--- height (=2) > 0 is true
---- Call c(2 - 1 = 1)
----- height(=1) > 0 is true
------ Call d(1 - 1 = 0)
------- height (=0) > 0 is false
------- Call AddBrickLayer
------ Function end
----- Call AddBrickLayer
---- Function end
--- Call AddBrickLayer
-- Function end
- Call AddBrickLayer
Function end

Each of the functions look like:

Code:

---

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

---

So "3" is passed as height to "a", "2" is passed as height to b, and so on. Eventually, as we reach d, height will be 0.

Quote:

---

Originally Posted by papagym177

...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.

---

It does not need a parameter. See how it gets called 4 times? Each time it adds a brick.
If you're still confused, I'd suggest you use a debugger to step through the code. Examine the variable height on each function call.

Quote:

---

Originally Posted by papagym177

Does the Compiler do this???

---

Not sure I know what you mean by this.

Quote:

---

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.

Quote:

---

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.

Quote:

---

Originally Posted by papagym177

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.

---

This is not guaranteed. The C++ standard says nothing about this, and indeed, some compilers do not always do this. You need only think about separate instances of the same function called with different arguments.

Quote:

---

Originally Posted by rcgldr

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

---

Quote:

---

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.

I think at this point you should not worry about how compiler implements it. Just care about the logic of recursion which is the main point. You may provide a non-recursive function to do the job but that does not mean you don't need to know about recursive functions.

To build a brick wall of height N, you first build a brick wall of height N-1, and then add a layer of brick to it.

Sounds like the normal way of building a brick wall to me...