Recursive And Inline Functions

Discussion in 'C++' started by usmanmalik, Jan 25, 2014.

  1. usmanmalik

    usmanmalik New Member

    Joined:
    Dec 28, 2013
    Messages:
    19
    Likes Received:
    14
    Trophy Points:
    0
    In this article we are going to explain some of the most fundamental but often neglected concepts of C++ programming language. These concepts are extremely interesting and if employed well, can solve complex mathematical problems. So, without wasting any more time, let us jump to the first concept i.e. recursion in C++.

    Recursion



    Recursion is not confined to C++; instead it is a general programming concept. In simplest words, recursion can be defined as the process of mechanism by which a function calls itself is called recursion. It seems weird; why a function would call itself. It is often regarded as a bug in some systems. But at the same time, if handled aptly, recursion can be integrated into your code and complex functionality could be achieved through it.

    It is much easier to explain recursion with the help of some example rather than writing long pieces of content over it. We will start with one of the most famous example program that is used to explain recursion. First we will show you how to write a factorial program without recursion to give you an idea what the program does. After that, we will write a similar factorial program that uses recursion to calculate factorial of a number. Have a look at the first example where we will calculate factorial of.

    Example1 (Factorial without recursion)

    Code:
    #include <iostream>
    #include <string>
    using namespace std;
    
    int main()
    {
    	int num;
    	int fact=1;
    	cout<<"Enter the number to calculate factorial:";
    	cin>>num;
    
    	for(int i=num; i>0; i--)
    	{
    		fact = fact * i;
    	}
    	cout<<"The factorial of the number is:"<<fact;
    }
    
    The code in example one quite straight-forward; you ask the user to enter the number. The number is stored in the variable. We inserted a loop into a code that will run number of times equal to the number of which tutorial has to be found. Note, we have initialized the variable ‘i’ with the number of which we want to find factorial and then have decremented this variable ‘i’ to 1. You know that when we find a factorial of the program we simply have to multiply the number with every number down to one. For example, if you have to find the tutorial of number 5, you will have to calculate something like:

    5 x 4 x 3 x 2 x 1 = 120

    Inside the loop we have done exactly this. We have initialized the fact variable with integer 1. Now when user enters 5, it is stored in the variable num. Inside loop, ‘i’ will be initialized with num and on the first iteration

    fact = 1 x 5 // because fact contains 1 and ‘i’ contains 5.
    fact now contains 5.

    In the second iteration
    fact = 5 x 4 // because fact contains 5 and ‘i’ contains 4.
    fact now contains 20.

    In the third iteration
    fact = 20 x 3 // because fact contains 20 and ‘i’ contains 3.
    fact now contains 60.

    In the fourth iteration
    fact = 60 x 2 // because fact contains 60 and ‘i’ contains 2.
    fact now contains 120.

    In the fifth iteration
    fact = 120 x 1 // because fact contains 120 and ‘i’ contains 1.
    fact now contains 120.

    So, this is how we calculated the factorial of a program using for loop. The loop will have 5 iterations and we will get our desired factorial result. The output of the code in Example1 will be as follows:

    Output1

    [​IMG]

    Now, we will write a code which will use recursive function in order to calculate the factorial of a program. Have a look at the code in Example2. Try to comprehend what is happening there and I will explain it in the following section.

    Example2
    Code:
    #include <iostream>
    #include <string>
    using namespace std;
    
    int factorial(int num) {
    	int temp;
    
    	if(num == 1) 
    	return 1;
    	else
    	temp = num * factorial(num - 1);
    	return temp;
    }
    
    void main(void) {
    	int num;
    	int fact;
    	cout<<"Enter a positive integer to calculate factorial:";
    	cin>>num;
    
    	if (num < 0)
    		cout << "Please Enter a positive integer.\n";
    	else
    		cout<<"The factorial of the number is:"<< factorial(num) << endl;	
    }
    
    In example2, we have defined a recursive function named factorial. The main function is almost similar to one in Exampl1 one with the exception that here we have called the factorial function and passed it a parameter named num which we obtained from the user and. We have to calculate factorial of this num.

    Now, come inside the factorial function, it returns an integer. We have declared a temporary variable of type integer here. In the beginning we have written that if number passed is equal to 1, simply return 1. Else, comes the most important line of the code around which the whole topic revolves
    Code:
    temp = num * factorial(num - 1);
    You can see that in the above line, inside the factorial function, the same factorial function is being called itself. Try to dry run this code.

    When the first recursion occurs
    temp = 5 * 4 // because here num is 5 and factorial(num-1) will return 4
    However, apart from returning 4, it will again call itself.

    When the 2nd recursion occurs
    temp = 5 * 4 * 3 // because here num is 4 and factorial(num-1) will return 3
    However, apart from returning 3, it will again call itself.
    Note, the previously return values from the recursion will stay there, as 5 in case of second recursion.

    When the 3rd recursion occurs
    temp = 5 * 4 * 3 * 2// because here num is 3 and factorial(num-1) will return 2
    However, apart from returning 2, it will again call itself.

    When the 4th recursion occurs
    temp = 5 * 4 * 3 * 2 * 1// because here num is 2 and factorial(num-1) will return 1

    However, apart from returning 2, it will again call itself.

    After the 4th recursive call, the recursion will stop because we have inserted a condition that if passed parameter is one, the function will return 1 and it will not call itself again. So, in the fourth recursion, 1 was returned from the function and recursion stopped. Now, come back to the first call. Values have not been return to the calling main function yet. Instead when a recursive call occurs, the function call registers and variables are placed on the stack. Recursive functions are kind of nested functions where with each recursive call a function is nested inside it. The depth of these nested functions will be equal to the degree of recursion. For example the depth of nested function was four

    Therefore after recursion ends, processing will occur from the 4th recursion and firstly, 1 will be multiplied with two, then the result will be multiplied by 3 then the result 6 will be multiplied by 4, then the result 24 will be multiplied by 5 and finally the result 120 will be stored in the variable temp which will then be returned to the main function.

    A very important concept worth paying attention is that you have to place a termination condition inside a recursive function, otherwise it will keep on calling itself forever which will result in memory shortage and ultimately your program will crash. Also, you want your recursive function to return some value; therefore it has to terminate at one point. This is done by some termination logic. In Example2, we wrote a termination logic where when passed parameter was one, the function did not called itself; instead it returned the value one, resulting in the termination of the recursion. If you execute Example2 and check the result; its output will be identical to one in Example1 but in this case we have performed the same functionality through recursion. Following will be the output of Example2

    Output2

    [​IMG]

    Inline Functions



    We said in the last section and in some previous articles related to function that function execution is a very technical process. When a call to function is made, several complex functionalities can be performed. Firstly, the memory address of the code calling function has to be stored somewhere. This includes storing CPU registers, program instructions and variable and arguments on some place in memory. Next, a call is made to the function and function arguments, code and local variables are stored on the stack. The function code is executed. Variable, arguments and code of the called function is removed from the memory and some value is returned to the calling function. Next, the previously saved program counter, CPU register, variable and code of the calling function is retrieved from the memory and execution of the calling function is again started from where it was stopped when the new function was called. The memory has to also store the return variable from the called function, somewhere.

    You can see that lots of complex functions are being performed when a call is being made to a function. There is a way to streamline this complex process which is particularly useful for small sized functions. We can achieve this by declaring a function inline. When a function is declared, the complex memory storage and retrieval process is eliminated. In simplest words, by declaring a function inline, we actually ask the compilers that whenever call to this function is made, instead of storing memory spaces and putting function variable on the stack, simply embed the code of this function inside the calling function. Now when this function will be called, internally the code of the inline function will be copied inside the calling function and no memory address storage and retrieval process will be involved. This concept has been explained in Example3.

    Example3
    Code:
    #include <iostream>
    #include <string>
    using namespace std;
    
    inline void funinline(int num) {
    	cout <<"The number entered passed is:"<<num;
    }
    void main(void) {
    	int num;
    
    	cout<<"Enter a number:";
    	cin>>num;
    
    	funinline(num);
    }
    
    In order to declare a function inline, one simply has to prefix the function declaration with keyword inline. It is actually a request the compiler that please there is no need to perform complex memory operations and context switching. Deal this piece of code as part of the calling function.

    In Example3, we have simply obtained a number from the user and then called an inline function funinline(int num) and have passed parameter to this function. The function in turn, displayed the value.

    A very important concept worth mentioning here is that DO NOT try to make large functions with complex code, inline. Because in that case, the cost of embedding the code into calling function becomes greater than complex memory functions being performed. Therefore, if have small functions with limited capabilities, you should make them inline whereas if you have large complex functions keep them as they are.

    Note: If you belong to C programming background, the functionalities being provided by inline keyword are similar to those of #define macros in c programming language. But, inline keyword is type-safe and easier to implement and read.

    A potential drawback of making a function inline is that it comes at the cost of organization and structuring of the code. Our intent is to make the code as much organized and structured as we can therefore we use classes and function. But inline functions negate basic theme of object oriented programming when they are embedded inside the calling function code.

    A good and proportionate choice is to use a mixture of both inline and non-inline functions. This way we can maximize the code performance whilst still maintaining the organization of the code.

    In this article we explained two of the most interested and useful C++ concepts: Recursion and inline function. Recursion refers to process where a function calls itself we explained this concept with the help of factorial example where we calculated the factorial of number with and without recursion. Then we moved to the inline function and explained it in detail. I would encourage you to further explore these concepts, try to write some other useful codes using recursion and also check the performance of your code using inline function. In case if you find any difficulty, leave a reply and I will get back to you.
     
    Last edited by a moderator: Jan 21, 2017
    shabbir likes this.

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice