iOS Recursion

[Branda22]

I would like to understand the concept of recursion beyond "It's a function that calls itself".

If I write the following 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

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.

Regards

 

[ArtOfWarfare]

I suggest running stack(2); by hand

Think about the order that each command gets called.

 

[chown33]

First, do you understand how the stack "winds"? That is, how it reaches the point where it will unwind. It's this code:

        stack(num - 1);

Second, the recursion starts unwinding here:

    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:

        stack(num - 1);

What happens next? This:

        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.

 

[Branda22]

Thank you so much for the explanation. It has really helped me understand what happens after num == 0;

 

[subsonix]

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:

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

 

[ArtOfWarfare]

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:

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

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.

 

[subsonix]

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.

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.

 

[Duncan C]

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:

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

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.

 

[MeFromHere]

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.

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.

 

[ArtOfWarfare]

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.

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.

 

[Branda22]

I used Xcode with the debugger and setting breakpoints in different parts of the code, then stepping through each line of code.

 

[ArtOfWarfare]

I used Xcode with the debugger and setting breakpoints in different parts of the code, then stepping through each line of code.

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

 

[subsonix]

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.

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.

----------

Excellent. That's exactly what I would have suggested

But didn't.

 

[PhoneyDeveloper]

@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

NSLog(@"%@", view);

and we know that all of the subviews of a view are held in the UIView @property named subviews. So something like

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.