(adsbygoogle = window.adsbygoogle || []).push({}); Is recursion in c++ really really important(for game programming)? Im reading a book and i really understand the concept but then they give really challenging assignments which i just cant figure out. Should i burst a blood vessel trying to figure the problem out? or just forget it? like i said i understand it, but maybe its that i dont understand the algorithm they're giving me, idk? advice?

Preface

Before I begin, let me make the following recommendation: If, as you read my post, it all seems like review, read it all the way through and really try to understand what you're reading. From the mathematical functions to the code to the text. That way if you still need help later, I can at least assume we're on the same page as regards to what you know.

Also, before you begin reading, I'll assume you have a basic understanding of mathematics and that you know how functions work in C++ (I'll also assume that you're fluent in English).


On the Topic of Recursion

Recursion is an important concept in computer science, and as such computer programming, and as such is important to all programming languages. I'd say languages such as C++ (object oriented/procedural), generally rely less on recursion than others, and recursion probably isn't a vital, irreplaceable tool in most games.

Having said that, recursion can be one of those useful tools that you put in your programming toolbox. You might not use it often, but it's important to know (and it's hard to call oneself a "programmer" and not understand recursion at a basic level). Also, you'll look good if you use it in any computer science class you take in the future.


An Introduction

Now, because I am such a nice person, I will explain recursion to you.

Recursion is a word. The word is defined in the Oxford dictionary as follows:

This is funny, because in some ways it's actually a recursive definition. So, let's take a peek at the definition of "recursive", a word that was used in the definition for "recursion". Oxford has actually come up with a somewhat "computer-science" related definition:


So, I'll give you a sort of general definition: a recursive function is a function that calls itself. For example:

    

void doSomething() {   // doSomething is defined

    doSomething();     // the function doSomething calls itself

}

Now, the code above is actually a terrible representation of recursion, as it's entirely pointless, but I just wanted to give a straight forward example.

Of course, recursion stretches beyond just code. We even do it with acronyms. For example, "GNU" stands for "GNU's Not Unix" or "PHP" stands for "PHP Hypertext Preprocessor" - the acronym is part of the acronym.


A First Example

Perhaps the canonical example of recursion is that in the calculation of a You must login or register to view this content.. In mathematics, the symbol to represent a factorial is the exclamation point (!). For example, 4! is the factorial of 4. A factorial is the product of all positive integers less than or equal to n (n being the factorial). For example, 4! (the factorial of 4) is equal to 4 multiplied by 3 multiplied by 2 multiplied by 1 (though we don't often consider 1 when calculating a factorial). Therefore 4! is equal to 4 x 3 x 2 x 1 = 24.

We can mathematically define the factorial function as follows:
You must login or register to view this content.

Interestingly, we can also define the factorial function recursively. Here goes it:
You must login or register to view this content.

So, let's look at how this mathematical function could be implemented as a C++ function:

    

int f(int n) {

    return n <= 1 ? 1 : n * f(n - 1);

}

As you can see in the code above, we make a recursive call to the function f as long as n (the input value) is greater than 1. n <= 1 is actually what's known as the base case, or the point at which the function should stop the recursive function calls.

It might help to step through this. Let's imagine we call f(4) somewhere in the code, thus trying to get the value of 4! (the factorial of 4, which happens to be equal to 24).

On the first step, n is equal to 4. Since n is not less than or equal to 1, we call n * f(n - 1), or 4 * f(3).
On the second step, n is equal to 3 (as we just called f(3) from the first step). Since n is not less than or equal to 1, we call n * f(n - 1), or 3 * f(2).
On the third step, n is equal to 2 (as we just called f(2) from the last step). Since n is not less than or equal to 1, we call n * f(n - 1), or 2 * f(1).
On the fourth step, n is equal to 1 (as we just called f(1) from the last step). Since n is now equal to 1, the function returns 1.

How does that possibly work?

Don't forget about the initial call, f(4).

Since f(1) returns 1, f(2) is equal to 2 * 1.
Since f(2) returns 2, f(3) is equal to 3 * 2.
Since f(3) returns 6, f(4) is equal to 4 * 6.
And alas, f(4) returns 24 (and we happen to know that 4! is equal to 24, so all's good).

Now, it could help to see another example...


Example: Fibonacci Sequence

Have you heard of the You must login or register to view this content.? It's an integer sequence that looks something like this: 0, 1, 1, 2, 3, 5, 8, 13, 21...

To calculate the Fibonacci sequence, we start with two seed values, 0 and 1. Each number that follows is the sum of the previous two in the sequence.

The definition for the Fibonacci sequence is as follows:
You must login or register to view this content.
Naturally, we assume the seed values of:
You must login or register to view this content.

As you can see, the Fibonacci sequence is actually defined recursively. We can define the function for calculating Fibonacci to the nth element like so:
You must login or register to view this content.

So, let's look at how this is defined in C++:

    

int f(int n) {

    if (n == 0) return 0;

    else if (n == 1) return 1;

    else return fib(n - 1) + fib(n - 2);

}

Now please, bear in mind, this is only a preliminary glance at recursion. It's a very important concept in both mathematics and computer science, one that people have devoted their lives to studying (even languages, say Lisp).

I hope this helps some, if it still doesn't make sense, please feel free to let me know. If you can't make sense of the challenges, post one and let us walk you through it, so you can solve the rest.

Quick Edit/Note:
I don't actually have a C or C++ compiler on this computer. While all my code should work, I haven't actually tested it. What I do have is a Scheme interpreter, so here are definitively tested and working solutions:

    

(define fac

  (lambda (n)

    (if (= n 0) 1

        (* n (factorial (- n 1))))))



(define fib

    (lambda (n)

      (if (< n 2) n

          (+ (fib (- n 1)) (fib (- n 2))))))

Thank you to Wikipedia for the pictures of the equations, it was easier to copy and paste than having to generate and upload my own. As much as I love LaTeX, I hate it.

Thank you!

What you said right there:

Is probably the most important thing, especially when it comes to programming.

thanks a lot, i already understood recursion its just that the challenges were quite.....well challenging. so thanks anyways for the tremendous amount of effort you put into this post,may i ask what college did you go to and what company do you own? any why aren't you a mod in this section??

Believe it or not, I'm actually still a high school student. I do take my math and computer science courses at my local community college, and during the summer I attend the University of Washington's (the seventh highest ranked university for computer science in America, according to You must login or register to view this content.) summer quarter (open to non-matriculated students). I've also taken an online course from Berkeley as well as quite a few AP courses (primarily in mathematics and computer science).

I've been studying it on my own since I was around 8 (when I started with HTML), and real programming at around 10 to 12, so a lot of what I know is self taught.

As for companies, I don't own any nor do I work at any.

As for why I'm not a moderator, it's possible that I might qualify, but I have no desire to be a moderator right now.

And lastly, if you still need help with the challenges, you should post one that confuses you, and I, and others, will be happy to walk you through it.

that's cool, i started programming at like 13 but then i quit and now im 14 and im coming back,im taking college courses now but its not in computer science,(i wish). i hope i could get as good as you soon.

Gee whiz, man. You put an awful lot of effort into this and it's all mightily useful information. Props and respect.