Recursion

Discussion in 'iOS Programming' started by Branda22, Jun 29, 2013.

  1. Branda22 macrumors newbie

    Joined:
    Jun 17, 2013
    Location:
    Curitiba, Brasil
    #1
    I would like to understand the concept of recursion beyond "It's a function that calls itself".

    If I write the following code:

    Code:
    void stack(int num)
    {
        if (num == 0)
        {
            printf("we are done \n");
        }
        else
        {
            printf("%d has been added to the stack \n", num);
            stack(num - 1);
            printf("%d has been removed from the stack \n", num); 
        }
    }
    
    
    
    int main(int argc, const char * argv[])
    {
    
        stack(10); 
       
        return 0;
        
    }
    
    The following will print

    Code:
    10 has been added to the stack 
    9 has been added to the stack 
    8 has been added to the stack 
    7 has been added to the stack 
    6 has been added to the stack 
    5 has been added to the stack 
    4 has been added to the stack 
    3 has been added to the stack 
    2 has been added to the stack 
    1 has been added to the stack 
    we are done 
    1 has been removed from the stack 
    2 has been removed from the stack 
    3 has been removed from the stack 
    4 has been removed from the stack 
    5 has been removed from the stack 
    6 has been removed from the stack 
    7 has been removed from the stack 
    8 has been removed from the stack 
    9 has been removed from the stack 
    10 has been removed from the stack
    
    I need help in understanding how the stack unwinds. :confused:

    Regards
     
  2. ArtOfWarfare macrumors 604

    ArtOfWarfare

    Joined:
    Nov 26, 2007
    #2
    I suggest running stack(2); by hand

    Think about the order that each command gets called.
     
  3. chown33 macrumors 604

    Joined:
    Aug 9, 2009
    #3
    First, do you understand how the stack "winds"? That is, how it reaches the point where it will unwind. It's this code:
    Code:
            stack(num - 1);
    

    Second, the recursion starts unwinding here:
    Code:
        if (num == 0)
        {
            printf("we are done \n");
        }
    
    So when num is equal to 0, it prints that line.

    What happens next? It returns.

    And where does it return to? To immediately after the last point it was called from.

    Where was that? Here:
    Code:
            stack(num - 1);
    
    What happens next? This:
    Code:
            printf("%d has been removed from the stack \n", num); 
    
    And what happens after that? It returns.
    And where does it return to? Wait, hasn't this question been asked before? What happened then?

    This illustrates an important principle in programming: Break It Down. That is, analyze and understand larger problems by breaking them down into smaller ones, until you get to problems you can solve.

    Here, the problem was solved by breaking things down step by step and following each step precisely. Try walking through exactly what happens if stack() is called with the value 4. This will illustrate recursion and unwinding the same as a value of 10, but it will be a shorter and less boring process to do it manually.
     
  4. Branda22 thread starter macrumors newbie

    Joined:
    Jun 17, 2013
    Location:
    Curitiba, Brasil
    #4
    Thank you so much for the explanation. It has really helped me understand what happens after num == 0; :D
     
  5. subsonix macrumors 68040

    Joined:
    Feb 2, 2008
    #5
    If you are using the terminal you can observe what happens by stepping through the code while the program is running with gdb like this:

    Code:
    % clang yourprogram.c -g
    % gdb a.out
    
    // then
    
    (gdb) start
    (gdb) step
    
    At this point, hit enter continually and look what lines gets executed and how the value of num changes.
     
  6. ArtOfWarfare macrumors 604

    ArtOfWarfare

    Joined:
    Nov 26, 2007
    #6
    For reasons like this, I'm thinking I may have been wrong when I started insisting beginners learn from a text editor and the command line... Using the graphical debugger is a lot easier than trying to learn how to use GDB from the command line.
     
  7. subsonix macrumors 68040

    Joined:
    Feb 2, 2008
    #7
    Sure, it's useful knowledge still. In this particular case there is no learning involved however, since I showed all steps necessary to step through the code.
     
  8. Duncan C macrumors 6502a

    Duncan C

    Joined:
    Jan 21, 2008
    Location:
    Northern Virginia
    #8

    Why would you have a beginner use the command line to step through his code? Ugh.

    I use the IDE debugger whenever possible. I know how to use the debugger command line. The IDE graphic debugger is much easier to use, the information it conveys is easier to follow, etc.

    Plus, gdb is no longer the default debugger, is deprecated, and will no longer be supported in Xcode very soon.
     
  9. MeFromHere macrumors 6502

    Joined:
    Oct 11, 2012
    #9
    The main problem I see with Xcode for beginners, is that it is really overwhelming. If I was using it to teach a beginner class, the first thing I'd try to do is turn off most of the features and hide most of the GUI. TextEdit with a "Run" button seems like about the right subset of Xcode at first. Don't need all the assistants, butlers, valets, pickers, choosers, browsers and dohickys at first. :)
     
  10. ArtOfWarfare macrumors 604

    ArtOfWarfare

    Joined:
    Nov 26, 2007
    #10
    Right, and hiding everything like that is totally possible. I think the Xcode project file stores information about which panels and views should be visible or hidden, so you could distribute that to them so that they never see the other stuff until they're ready.

    And if that doesn't work, I've been able to disable various views by writing Xcode plugins, so you could write some kind of "beginner edition" Xcode plugin.
     
  11. Branda22 thread starter macrumors newbie

    Joined:
    Jun 17, 2013
    Location:
    Curitiba, Brasil
    #11
    I used Xcode with the debugger and setting breakpoints in different parts of the code, then stepping through each line of code.
     
  12. ArtOfWarfare macrumors 604

    ArtOfWarfare

    Joined:
    Nov 26, 2007
    #12
    Excellent. That's exactly what I would have suggested to someone else that I thought had more experience.

    Using the debugger should probably be taught earlier... at my school I don't think there's ever any mention of techniques for debugging code...
     
  13. subsonix macrumors 68040

    Joined:
    Feb 2, 2008
    #13
    In this case it's really not that much to do, besides the compilation it's 2 steps. I rather test it fast right there, it's going to be done before Xcode has even launched.

    And why don't you show how to do it in the GUI, instead of criticizing my choice? The important part here is that stepping through the code in the debugger illustrates clearly what happens here, the important part is not what debugger you use.

    ----------

    But didn't.
     
  14. PhoneyDeveloper macrumors 68030

    PhoneyDeveloper

    Joined:
    Sep 2, 2008
    #14
    @OP, how would you write a function that prints out a description of all the views in a view hierarchy? We know that we can print out a desciption of a single view like this

    Code:
    NSLog(@"%@", view);
    and we know that all of the subviews of a view are held in the UIView @property named subviews. So something like

    Code:
    for (UIView* view in someView.subviews)
         NSLog(@"%@", view);
    
    will print out a description of all the subviews. But it won't print out all the subviews of the subviews. If you start from the window object you should be able to print out all the views in the hierarchy. Using recursion will help to accomplish this. You might want to inset each subview's subviews by some number of spaces or dots to indicate the hierarchy also.

    You might want to think about how traversing a tree data structure is facilitated by using recursion.
     

Share This Page