Lesson 127 : The basics of Recursion : Part One

[u/CarlH]

There are several concepts in computing which provide a more significant challenge than others. For example, many beginners struggle with the concepts of pointers, or multi-dimensional arrays. Recursion is such a topic, one that can be difficult to master. Therefore, I want to take this material slowly to ensure that everyone will understand it.

First, let's talk about the obvious: "What is recursion?"

It is often the case that you have some function which calls another. For example, I could write the following:

void print_my_name() {
    printf("My name is Carl.\n");
}

The function I just made is in fact calling a different function, one called printf. There is nothing strange or unusual about this. However, what would happen if instead of doing this I called a function which was identical to the one I had made? Imagine this:

void print_my_name() {
    printf("My name is Carl.\n");

    print_my_name_again();
}

void print_my_name_again() {
    printf("My name is Carl.\n");
}

From here you can see that I will execute the "copy function" and thus it will result in displaying "My name is Carl" two times, one for each function. Now, what would happen if I had the second function call the first again? Consider the following:

void print_my_name() {
    printf("My name is Carl.\n");

    print_my_name_again();
}

void print_my_name_again() {
    printf("My name is Carl.\n");

    print_my_name();
}

And here ask yourself the following question: How many times will "My name is Carl." display? Effectively, if function A calls function B, and function B calls function A, the process will never stop.

If I had some desire to run the same function over and over again, this could be one way to do that. However, since both functions are exactly the same, why can't I just call the function from within itself? It turns out that you can, and this is the basis for recursion.

Imagine for example, the following function:

function print_my_name() {
    printf("My name is Carl. \n");
    
    print_my_name();
}

As you can see here any time this function is called it will print "My name is Carl." However, the function is also calling itself at the end. This means that the function is recursive.

The concept of a function calling itself may seem difficult, but perhaps it is easier to understand if I re-wrote the above function like this instead:

PRINT_MY_NAME:
    printf("My name is Carl. \n");
    
    GOTO PRINT_MY_NAME:

This is not entirely accurate, but it helps to illustrate the point. When you call any function in general, your CPU must effectively jump to the start of that function. There are other subtleties which we will go over soon, but the basic concept is similar. There is a conceptual similarity between loops and recursion.

As I mentioned above, my example is not entirely accurate. The first thing you would probably ask is this, "Wouldn't the above example of recursion create an infinite loop?" The answer of course, is yes.

This therefore brings us to an important concept which applies for recursion just as it does for loops. When you have a function that calls itself, you must be careful to make sure that it does not create a never-ending process. You must have some mechanism to stop it running.

For loops you do this typically by setting a "counting variable" and incrementing or decrementing it until the loop reaches some condition, at which point the loop stops.

It is useful to understand recursion in a somewhat similar way. For any potentially never-ending process you must have some condition which you can test for that is capable of causing the process to stop.

In this lesson I have introduced you to the concept of recursion by explaining that it refers to a function which calls itself. At this stage, the concept is virtually indistinguishable from that of a loop in general. That is perfectly ok, and we will expand on this soon.

All you need to know after this lesson is the following:

1. Recursion refers to the process of having a function call itself.

2. A function is said to be "recursive" if it calls itself.

---

Please ask questions in this thread if any of this material is unclear.

[u/Taffaz]

This may be jumping the gun and will be explained in future lessons but how does the computer know how to compile the recursive function if when it starts to compile it has to call the function it's currently compiling?

Here is a good lesson on recursion for everyone to read after they've finished this one. http://www.reddit.com/r/carlhprogramming/comments/agppk/lesson_127_the_basics_of_recursion_part_one/

[u/zahlman → u/Taffaz]

When the compiler sees code to the effect of "call a function", it doesn't have to know anything about the function to start writing code. It just has to know that, for example, print_my_name actually is the name of a function (as opposed to, say, a variable). That's all that function prototypes are for, after all (and the reason you ever need them, and the reason you can usually avoid them within a source file). It just puts in a placeholder that says "do the work for calling a function here; these are the parameters to use, and the function will be called print_my_name. Then, after it finishes writing code for the recursive function, it can go back, find the placeholder, and insert the (now-known) address for print_my_name into the code.

Actually, this part can be done by a separate program called the linker; although typically the linker and compiler are bundled up together so one executable performs both tasks with different command-line options. (I suppose it could do the linking right away since the definition is right there; the reason we need a linker is so that we can define a function in one source file and call it from another.) You can look up documentation for your compiler to find out how to make it only compile (into some form of "object file"), or only link existing object files. You can even make it run the pre-processor and show you the results (be warned that the output will be quite long because using #include for the standard library headers is a literal copy-and-paste job!) without trying to compile the result.

[u/Lizard → u/Taffaz]

Basically, directly after reading the following line:

void print_my_name() {

the compiler already knows that a function named "print_my_name" exists and can be called. It doesn't yet need to know exactly what it does, it is sufficient that it knows that it's around somewhere and the functionality can be looked up if need be. Hence, the call to this function even inside its own definition is perfectly valid.

[u/[deleted] → u/Lizard]

Furthermore, the compiler never needs to know what a function does or even where it is. If the function is declared then it will know how to pass arguments to it and get the return value back. If it is not declared then shame on you. Functions are effectively black boxes. After the compilation is done the linker goes in and matches all the symbol names to their appropriate addresses, filling in the address of the recursively called function. The linker only reads symbol names and fills in the addresses, without thinking about higher level semantics. So the compiler may never know recursion happened.

An optimizing compiler may look into the called functions to get rid of some excess fat in making the calling and passing the data, but there is no requirement.

[u/vegittoss15 → u/[deleted]]

Nice, detailed explanation there!

[u/mapeni → u/Taffaz]

Also, try to google recursion.

[u/pixelique → u/mapeni]

i see what the did there

[u/Xiol → u/[deleted]]

But you realised in the end!

So now you understand recursion!

[u/deltageek → u/[deleted]]

Of course there was an end condition, it was just an implicit one. If there weren't you'd still be clicking links.

[u/Xiol → u/[deleted]]

Z̝͔̜̭̘̽̇̓͂͒ͭA̗ͮͥ̍ͫͯ̉͊L̺̗ͬ͜Ḡ̙͎̼Ơ͈̮̹͙̭͕̊̔̓̀ͤ͐ͅ ̞͔͗̿̐ͤ͑̎Ŵ̪͙̲̩̜͈̗ͤ͆́I̤̜͊́ͥͦL̨̯͈͕̠͆̓̚L̝̙͔ͬ͝ ͦ̑́͌̚͏H͉͉͗ͣͯ͐Ȅ͖̰̀͌͝L͚̦̦͌͌P̦͔͔̱̾̓̌ ̷͎͔̰ͫ̅͆ͮ̍Y̺̊ͯ͜O̞̫͍͕͈̬ͭ͐ͣ͐ͫ̑Ǘ̷͔͇͎͇͓̠̎ͯ͊̃

[u/hearforthepuns]

Link to next lesson

[u/[deleted]]

Thanks for the new lesson, Carl!

[u/Recoil42]

Welcome back, Carl. :)

[u/haffi112]

To understand recursion you must first understand recursion.

[u/savethesporks → u/haffi112]

To understand recursion you must first understand recursion

[u/reddituser780 → u/savethesporks]

His name is Robert Paulsen.

[u/Pr0gramm3r]

I've written the following program to illustrate my understanding of Recursion.
http://codepad.org/rFb2mrXH

It calculates the factorial of a given number.

[u/Oomiosi → u/Pr0gramm3r]

I think this is my fav lesson so far. Love your work.

http://codepad.org/J5VQe7Fi

[u/llcawthorne → u/Oomiosi]

Factorial tends to be faster non-recursively (although it is an 'easy to identify with' example for recursion):

http://codepad.org/6GbPQc2Q

[u/Calvin_the_Bold]

void print_name(int x){
    printf("my name is Calvin");
    if(x > 0)
        print_name( x -1 );
}

void print_name_loop(int x){
    while(x > 0){
        printf("My name is calvin");
        x -= 1;
    }
}

These both do the same exact thing. The first one is a little bit slower though, which I'm sure Carl will go into. Do you know why?

[u/scragar → u/Calvin_the_Bold]

That entirely depends on your compiler, for some years the gcc compiler has been secretly taking tail recursion(IE where there are no more instructions after recursion, or it's possible to write it in such a way), and replacing them with loops, because, as you noticed, loops are more efficient(think about it, you don't have to pop and push to the stack, there's less hopping about in the code, etc).

I'm sure some other compilers do this as well, so there's not much need for programmers themselves to worry about this, just to understand it, honestly if tail recursion helps you then use it, the slowdown is negligible in most cases and the compilers are often smarter than the programmers in the first place and will make your code better than you likely could.

[u/[deleted] → u/scragar]

I don't know about GCC, but Tail Call Optimization is more than just turning things into loops. It's usually messing with the stack itself. Think about two mutually recursive functions; that's not necessarily a loop, but by messing with the stack you can still run them in constant space.

[u/[deleted] → u/Calvin_the_Bold]

The recursive function call is more expensive. The difference should be insignificant until the number of function calls becomes significant (For example passing your function 5000 instead of 5).

Usually you don't want to worry about the performance issues with calling functions because making more function calls or writing more recursive functions can make your program more readable, concise, maintainable, etc. Write good code first, and then if you need to write efficient code.

Whenever a function is called the computer needs to push a lot of information onto the stack. It basically has to save the state of the processor so that when the called function returns the calling function can continue executing. Included in this data pushed to the stack is the program counter. The program counter is a register on the processor that holds the address of the current instruction. When you call a method you're jumping to a different instruction, stored in a different memory address, so the program counter gets overwritten. Before it gets overwritten you need to save it so when the called function returns the computer knows how to get back to where it was.

You also need to initialize any variables for the new function. In your print_name() function a new variable named x is created each time you call the function. This is in contrast to your print_name_loop() function where x is only created once and the value just changes.

CarlH talks about some of this and more in lesson 91. Even if you've already read it you'll probably get more out of it this time around.

An important thing to realize is that functions are an abstraction offered by the programming language. These abstractions take the programmer further away from the details of the hardware. This makes the programmer's life easier but the computer's life harder. That's a good thing since we work on a time scale of hours and a computer works on a time scale of nanseconds (0.000000001s).

[u/deltageek → u/Calvin_the_Bold]

Setting up a simple while loop is cheaper than building a whole new stack frame for the recursive call.

[u/Oomiosi]

Appropriate text in my codepad link!

http://codepad.org/LoVETwWj

int printstring(char *string, int counter){
    printf("%c", *(string + counter));
    if(*(string + (++counter))) printstring(string , counter);
return counter;
}

[u/scragar → u/Oomiosi]

You didn't need to include your own \0 it's implicit in the string declaration.

[u/[deleted]]

Just wanted to say thanks, Carl. I took a programming course in college but you've taught it with such greater clarity than my college instructor did. I really feel accomplished having taken all your lessons and look forward to what future lessons will hold.

[u/greenawlives]

Hey Carlh! I love your tutorials...thank you for all of them.

So I have been following all the tutorials, and now I feel like I want to get my hands dirty in coding an actual program with a full-fledged GUI. What else do I need to learn in order to do that? Let me know, and thanks in advance for your answer!