Recursion in C++

In this article I will talk about recursion, an advanced mechanic used in C++,
and how it may be used in programming.

Things you should know

Before you continue reading this article, in order to fully understand the concepts
I present, you must have a basic understanding of C/C++ mathematical operators,
functions and how to use them, and program control loops(for, while, do while).

What is recursion?

So, what exactly is recursion? Recursion is a concept similar to looping, only it is used
in functions; it’s a function that calls on itself until a condition is met, or you may
just want it to loop it forever.
Consider this function:

CODE :


This little snippet shows one of the most basic recursive loops. As you see, the function
is first declared as a regular int function. Then the body of the function returns itself,
it's own value to where ever it was called in your program.

Now it's time to look at a much longer, and possibly more used method of recursion.
Consider this function:
CODE :


Let's take this apart slowly.
First, suppose the value of integer count is 5,
since the 5 is not equal to 0, then control is branched to
the else statement, where the current value of count is displayed,
which is still 5.
Now the next line(not the one that outputs the new line) is one of the most important
lines in the function. The function returns itself passed with it's own argument minus 1,
the program then has to go and loop through the function again, this time with its argument
equal to 4. When control reaches that same line, the program executes again through the function,
with argument passed as 3. Thus execution continues until the argument is equal to 0.


The Stack

I believe now would be a good time to take a break and process this information in you heads a little bit.

***
Okay, now that we're back, this seems like an excellent time to present a concept called "The Stack".
The stack is the level of program execution through a recursive function. In the above mentioned function,
the stack would execute through the function once with value 5. It would then loop through the function again,
with value 4, because of

CODE :


With it's argument now equal to 4, the stack continues with 3, then 2, then 1, stops at 0, returns 0, then goes
back and returns 1, 2, 3, 4, and 5.
The stack is basically the memory portion of your program where it stores, function arguments, return adresses,
and local variables. Keep in mind that using recursion in your programs uses a lot of memory.


Recursion and loops

Loops, are iterated through again and again until a certain condition is met, if one is provided.
Recusrion is a function calling itself, producing a similar effect.
If that is so, then why use recursion? Isn't looping much more simpler? There are several advanteges to using both.

Loops like the for loop, the while loop, are easier to use, to understand,
and you can do a lot in a single loop. One big difference between loops and
recusrsive functionsis the size of memory both involve. The loop is smaller in
memory size because it is a program control statement, and must be smaller for convinience.
But the recursive function has the stack running up and down, in and out, so it must take
up a large portion of your program. Since a recursive loop is a function, one of the many
parts to the whole program, it is more flexible than an iterative loop.


While both have their upsides and downsides, recursive functions are extreamly useful to
programming and the programmers. Recusion is a powerful tool to implement in software.
I hope this little tutorial has helped you all understand recursion better.

Mortecai4