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

  1. #1
    Registered User
    Join Date
    Jul 2014
    Location
    Central Arizona
    Posts
    61

    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(); 
    } 
    

  2. #2
    Registered User
    Join Date
    Apr 2013
    Posts
    1,646
    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).

  3. #3
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Registered User
    Join Date
    Jul 2014
    Location
    Central Arizona
    Posts
    61
    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.

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    1,646
    Quote Originally Posted by papagym177 View Post
    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.

  6. #6
    Registered User
    Join Date
    Oct 2006
    Posts
    3,445
    Quote Originally Posted by papagym177 View Post
    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.
    What can this strange device be?
    When I touch it, it gives forth a sound
    It's got wires that vibrate and give music
    What can this thing be that I found?

  7. #7
    Registered User
    Join Date
    Jul 2014
    Location
    Central Arizona
    Posts
    61
    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???

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by papagym177 View Post
    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 View Post
    ...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 View Post
    Does the Compiler do this???
    Not sure I know what you mean by this.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Registered User
    Join Date
    Apr 2013
    Posts
    1,646
    Quote Originally Posted by papagym177 View Post
    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 View Post
    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.

  10. #10
    Registered User
    Join Date
    Jul 2014
    Location
    Central Arizona
    Posts
    61
    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.

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by papagym177 View Post
    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 Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    Registered User
    Join Date
    Apr 2013
    Posts
    1,646
    Quote Originally Posted by rcgldr View Post
    Each time buildWall calls itself, it pushes the value height-1 onto the stack
    Quote Originally Posted by Elysia View Post
    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.

  13. #13
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    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.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  14. #14
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,398
    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...
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 02-15-2013, 03:05 PM
  2. Recursion Function explain...
    By Siaw Ys in forum C Programming
    Replies: 9
    Last Post: 11-19-2011, 10:52 PM
  3. Please explain the following function
    By mahor1989 in forum C++ Programming
    Replies: 3
    Last Post: 07-24-2011, 11:18 PM
  4. can anyone explain the gets() function?
    By Ryan_P in forum C++ Programming
    Replies: 5
    Last Post: 05-18-2002, 01:17 PM