View source for Functions and recursion

This lesson will have to do with using functions and recursion to improve readability and efficiency of your code. This lesson assumes you have a general grasp of C++ syntax. Other than that, I will explain everything as well as I can.
{{?}}
==Functions==
Simply put a function is a segment of code that is isolated from the main code segment. A function is ''called'' from a section of code. When the function's code has been executed, it ''returns'' to the calling code. The general form of a function is:

:{|
|-
|''return_type'' '''''function_name''''' ([''arg1_type'' ''arg1_name'', ...]) { ''code'' }
|}

Here is an example of a function:

<pre>int addTwoInts(int arg1, int arg2) 
{
   int sum = arg1 + arg2;
   return sum;
}</pre>

* The '''<tt>int<tt>''' at the beginning is the return type of the function.
* '''<tt>addTwoInts<tt>''' is the function's identifier. It will be what is used to call the function.
* '''<tt>int arg1<tt>''' and '''<tt>int arg2<tt>''' are called parameters. They are defined in the form <tt><type> <identifier><tt>. These will be explained later.
* The code for the function is enclosed in a set of curly brackets '''<tt>{ }<tt>'''.
* Every function with a return type other than <tt>void<tt> must have a '''<tt>return<tt>''' statement. This is the data that the function will be sending back to the calling code.

Many conventions exist governing the form of functions in C++. Generally, whatever form is most readable to you is the one you should use. For example, some coders will leave the opening <tt>{<tt> on the same line as the function definition while others will give it its own line. Also, some coders would name the above function <tt>add_two_ints<tt>. This is mostly personal preference.

===The <tt>main<tt> Function===
The <tt>main<tt> function is a special function. Every C++ program must contain a function named "main". It serves as the entry point for the program. The computer will start running the code from the beginning of the main function.
There are two main types of <tt>main<tt> functions; one with and one without parameters. Below are examples of both:
<pre>
/* Without Parameters */
int main()
{
   ...
}
</pre>
<pre>
/* With Parameters */
int main(int argc, char * const argv[])
{
   ...
}
</pre>
The reason for having the parameter option for the main function is to allow input from the command line. When you use the <tt>main<tt> function with parameters, it saves every group of characters (separated by a space) after the program name as elements in an array named <tt>argv<tt>. The array datatype may be beyond you at the moment, but don't fret. In time you will learn of it.
Here is an example of a command line statement with a program that uses a <tt>main<tt> function that accepts arguments.
<pre>
C:\> program.exe text 234
</pre>
This command would pass the following information to the <tt>main<tt> function:
*argc = 3
*argv = <tt>{program.exe, text, 234}<tt>
:* Note that the '234' is a string, not an integer value

Since the <tt>main<tt> function has the return type of <tt>int<tt>, the programmer must always have a return statement in the code. The number that is returned is used to inform the calling program what the result of the program's execution was. Returning 0 signals that there were no problems.

===Prototypes===
Before we discuss calling the functions, we must talk about ''prototypes''. Programs written in C++ are executed in logical order from the top down. A statement can only use things that are declared in code that has already been executed. This may not always be above them in the code ''literally'', but it usually will be. By convention, the <tt>main<tt> function is always the first function listed. To allow <tt>main<tt> to call functions that are declared after it in code, we use prototypes; a line of code that tells the computer the function exists, but it will be declared later. 

The prototype is much the same as the definition, but without parameter names.
Example:
<pre>
/*Definiton*/
int fctn2(int num1, int num2)
{ ... }

/*Prototype*/
int fctn2(int, int);
</pre>

This idea will be illustrated in the following section.

===Calling===
''Calling'' refers to how a function is used from code.

Example:
<pre>
#include <iostream>
using namespace std;

void fctn1();
int fctn2(int, int);

int main()
{
   int sum;
   
   fctn1();
   sum = fctn2(2,3);

   return 0;
}

void fctn1()
{
   cout << "This is function 1!" << endl;
}

int fctn2(int num1, int num2)
{
   //the value 2 has been passed as num1
   //the value 3 has been passed as num2

   return num1 + num2;
}
</pre>
There are many things to note in this example. First is the use of the two prototypes that precede the <tt>main<tt> function. They allow <tt>main<tt> to use <tt>fctn1<tt> and <tt>fctn2<tt> even though they aren't defined until after <tt>main<tt>. 

Next, notice that to call <tt>fctn1<tt> all we had to do was enter <tt>fctn1();<tt>. Since it doesn't require any arguments and it has a <tt>void<tt> return value, this is very simple. For <tt>fctn2<tt> however, we see that it not only requires two arguments, but also returns an integer as well. To pass data to a function, you simply list the data in the order it is called for by the function definition. To catch the returned data, we use the assignment operator '=' and assign the returned value to a variable <tt>sum<tt>.

Another thing to note is that functions with a <tt>void<tt> return type, as <tt>fctn1<tt>, do not require a return statement as they do not return anything.

===Parameters===
Parameters are how data is passed between functions through the call of the function. Above we learned that you list the data you want to pass to a function in the call between  the <tt>( )<tt>. The order of the list is determined by the function definition. The first parameter in the list will be assigned to the variable listed first in the function definition. Also, in most cases, you must have the correct number and type of data being passed to the function or you will receive an error when you try to compile your program.

For example:
<pre>
int main
{
   fctn(num1, 12);
}

void fctn(int arg1, int arg2)
{ ... }

</pre> 
This would pass the contents of the variable <tt>num1<tt> to <tt>arg1<tt> in the function. Then the integer value '12' would be passed to <tt>arg2<tt>. 

====Passing Methods====
By default, values are passed to a function through a method called '''''pass by value'''''. This means that the value of the variable is passed, not the variable itself. This would be like giving a person a copy of your driver's license. They can read all of your information and they can change whatever they want on their copy, but the original is not altered in any way. 

If desired, a value can be passed through a method called '''''pass by reference''''' where the function is actually given the address of the variable, allowing it direct access to the information. This is done by placing a '&' after the data type in the function definition (this must also be present in any prototype). So, if we were to want to pass num1 using pass by reference, we would say:

<pre>fctn(num1, 23);</pre> as before in the <tt>main<tt> function, but in the definition, we would say <pre>void fctn(int& arg1, int arg2)</pre>

Following is a guide as to when one should use pass by reference to alter data, and when one should just use a return statement:

{| class="wikitable" style="text-align:center"
|-
!# values altered !! Return !! Pass by value !! Pass by reference
|- 
| 0  || N || Y || N
|- 
| 1  || Y || Y || N
|- 
| 2+ || N || N || Y
|}

You can mix between the use of pass by value and pass by reference from parameter to parameter, but it is not good programming practice to mix the use of pass by reference and returning.

====Default Parameters====
It's possible to assign default values to parameters that are omitted from the function call. The default values are usually defined in the function prototype like this example:
<pre>
int addTwoInts(int = 4, int = 5);
</pre>
In this case, if the parameters aren't provided, they will be assigned 4 and 5 respectively. So, for example, if you had the call
<pre>
temp = addTwoInts();

temp = addTwoInts(33);
</pre>
Neither of these calls would raise an error. In the first one, both values would be set to their defaults. In the second example, the first argument would be passed 33 while the second argument would still be defaulted to 5. You cannot default the second one without defaulting the first one as well.

===Scope===
Scope refers to the level of access an object has. A function can access only global variables and those that are passed to it through arguments. Also, any variables declared inside a function are only available to that function.
For example, an integer declared in <tt>main<tt> will not be available to any other function unless it is passed as an argument. Vis versa, an integer declared in a function will not be available to the <tt>main<tt> function.

==Recursion==
''Recursion'' is a method of function calling in which a function calls itself during execution. Let's start by showing an example and then discussing it.

<pre>
int factorial(int n)
{
   if(n == 1 || n == 0)
   {
      return 1;
   }
   else
   {
      return n*factorial(n-1);
   }
}
</pre>
This is a classic application of recursion. This function calculates the factorial of a number. As you probably know the factorial of n, written n!, is the product of every number from 1 to n. So we can say that 4! = 4&times;3&times;2&times;1. Let's step through what happens in our function when we call <tt>num = factorial(4)<tt>.

*<tt>factorial(4)<tt> is called
:*Since n=4, we take the <tt>else<tt> path. We return 4&times;<tt>factorial(n-1)<tt>
:*<tt>factorial(3)<tt> is called
::*Since n=3, we take the <tt>else<tt> path. We return 3&times;<tt>factorial(n-1)<tt>
::*<tt>factorial(2)<tt> is called
:::*Since n=2, we take the <tt>else<tt> path. We return 2&times;<tt>factorial(n-1)<tt>
:::*<tt>factorial(1)<tt> is called
::::*Since n=1, we take the first path and finally return 1 to the previous function
:::*<tt>factorial(1)<tt> returns 1 so <tt>factorial(2)<tt> can return 2&times;1...2
::*<tt>factorial(2)<tt> returns 2 so <tt>factorial(3)<tt> can return 3&times;2...6
:*<tt>factorial(3)<tt> returns 6 so <tt>factorial(4)<tt> can return 4&times;6...24

Many times, a recursive solution to a problem is very easy to program. The drawback of using recursion is that there is a lot of overhead. Every time a function is called, it is placed in memory. Since you don't exit the <tt>factorial<tt> function until n reaches 1, n functions will reside in memory. This isn't a problem for the simple factorial(4), but other functions can lead to serious memory requirements.

==Where To Go Next==
{{Cpp_Lessons}}

[[Category:Programming]]
[[Category:C++]]