Recursion

Q. What is recursion and why we use it?

Ans. As the name suggest recursion is to call something or do something again and again.

In programming language if a function invokes itself or in lay man language a function call itself. Then this programming paradigm is called recursion.

Recursion is very useful in some situations.  Like: finding the factorial.

But every coin has two faces. So Recursion also has some cons.

Ex:

int find_fact(int k){

       if(k==0 || k==1)

             return 1;

       else 

             return  k* finf_fact(k-1);

}

In this function we call find_fact again till we reach the termination condition which is k==1.

Before writing any recursive function we should think of what will be its terminating condition. Our calls to the same function should converge to termination point . It should not deviate away from the termination point otherwise it may go in to infinite loop.

Ex. 

if in above example I write k+1 instead of k-1 and if user send 2 as input to function then this will never going to be terminated. Because it is going away from the termination point. Recursive call should be converging to the termination point.

Any recursive function or program can be written without recursion but not other way around.

In recursive function in built stack of computer is used. It keeps all the information of the call at which line function is invoked. It puts that function frame to the top of the stack and then function returns it reach to the last address where it left the function and start evaluating again.

But as the number of calls increases the stack size increases. So for large number of inputs there might be segmentation fault due to stack overflow. So avoid the writing functions using recursion . Try to write it without recursion and use your stack so you know what is the size of the stack. Whether it is overflowing or not.

To find the complexity of the recursive function we write the recursive equation and try to solve it using Master's theorem or tree method or induction any of these or any other method.

Ex. the recursive equation of the above function is

               

T(n) = T(n-1) + C;                       

C is here some constant it may be zero or anything. It depends on the function. Here No loops in the function only just a condition and a multiplication expression so C's value here is turn to be 1.

By solving this you can get the complexity. I am leaving this is an easy exercise to do on your own.

Array vs Link List

Q. What is the difference between array and linked list and when to use them?

Ans : Both are data structures. Data structures are used to store and processed data in some order in efficient way.

Arrays are static data structure. Static means we have to define the size of the array while initializing the arrays. Later on we can not modify the size of arrays.

Ex:   int array[10];

Here array is an array of 10 integers. We can not increase the size of the array at run time. But we can access any element of the array randomly. We do not have to traverse the whole array.

Ex:  array[1]=1;


Instead link list is a dynamic data structure. We do not have to define the size of the link list at the time of initialization. We can increase the size dynamically at run time. We implement the link list by using pointers and pointers can be allocated memory easily at running time.

In link list we can not access any element randomly we have to traverse the all the elements which are before the target element. So complexity of accessing element in link list are much more than the array.

Difference in the complexity of Searching and Sorting varies with the algorithms used to do the mentioned tasks. Generally we use the array when we know the size of the input otherwise we go for the link list.

Write a function

Q. How to write a function and why we need them?

Ans. First of all why we need function.

Suppose we have to write a programme for L.C.M. (least common multiple) for two integers . We wrote the programme without using function and someone now ask to write the same programme for more than two integers. But now we cannot use the same programme for it. But If we would have written that programme in a function then we could have used that function for extension.

If we have to find the l.c.m. twice in the same programme then we have to write the code twice if we are not making a function of the l.c.m.

There are more advantages.

1. We don't have to rewrite the code again and again. (Code length is reduced)

2. We can use those function in other programmes but if do not write in functions we can not re use them. (Extendability)

3. Easy to read and understand. (User and programmer friendly)

How to write functions?

Functions always have their prototype. Means what is the function's name and what function take as argument and what does function return etc.. I will explain it in the next part.

Prototype:(function declaration)

Return_type function_name ( function's arguments);

Ex.  int add(int val1, int val2);

In this prototype function's return type is int means function will return a integer. Function name is add and it takes two argument val1 and val2. It is just a prototype. Function will also have a body. In which we define what function really does?

(function definition)

Ex.

 int add(int val1, int val2){             //function body starts

      int result= val1+val2;

      return result;

}

Function's body is written between the paranthesis. Here we define a temporarily variable which is not necessary. We add the two values and return the result through return keyword.

We could have written it this way also.

int add(int val1,int val2){

       return val1+val2;

}

This is also correct. It automatically allocate a temporarily variable and calculate the result and then return the result.

Prototype is not necessary if you define function before it is used. But now in new gcc compiler (2014) there is no need to write prototype or declaration . You can directly define function anywhere in the programme. Remember it is true only for the latest gnu gcc compiler.

Trap in operating system

Q. What is trap and an example of trap which we use in daily life?

Ans. Trap is a type of interrupt which is used to communicate with processor. It can be hardware or software either. Generally it is a hardware interrupt with manual access. 

Main thing is that the priority of Trap is always higher than the any kind of other interrupt . If once a trap is occurred processor will execute the instruction corresponding to that trap in any kind of situation.

Ex: The example of a trap which we use in our daily life is the power button in laptops. In whatever condition if we push that button it shutdown the pc.

Macros

Q. Why we use macros?
Ans. First of all What is macros?

Macros are used to define something before the execution starts and its values are never changed during the execution.

Ex:  in c/c++

#define max_size 100
#ifndef
#include<something.h>
#end if

Imagine the scenario you write a program where you assume the size of the input to 1000 at max and u use every where 1000 . Then some one asked you to modify that program for 10000 elements then you have to go to all places where you write that 1000 and replaced it by 10000 instead of that we can use macros we define variable in starting outside the main function and use that variable in our function if some one asked to change the size we change only that variable and the changes at all the places are taken care of automatically.

Macros are predefine variables or function. Compiler replaces all the macros in its pre processing with its corresponding values in the entire program.

Argument to main function in C/C++

Q. What is the use of passing argument to main function?
Ans.
      First of all we can define main function in three different format in c/c++.
      int main(int argc,char * argv[]);
      int main(void);
      int main();

Instead of int return type we can have any other pre defined data type as return type of main function.

We start with the first prototype, here main function excepts two arguments one is of type int and other is of type array of pointers. First of all these arguments are used for passing the input together when we start executing the program. We don't have to pass the first argument it automatically counts how many argument we have passed while executing the program and that will be stored in argc.

Second argument argv[] is array of character pointers which stores the inputs which we have sent with execution. for ex. argv[0] will have first argument and argv[1] will have second argument .

In the second prototype it does not except any argument if we passes a argument the compiler will give an error.

Third one is similar to the second one but the difference is that in third one we can pass as many argument we want it will not give an error but in the second one it will give an error while we pass an argument to main function using terminal (linux users).

Two main function in java

Q. The question is that can we have two main functions in java?

Ans. Yes, We can have two main function in java but the function's prototype should be different.

 For example we can have two functions like-
public static void main(string[] args);

and second one may be

public static void main(int a);


The reason for this is that when compiler/interpreter starts executing it starts with finding a function whose prototype is similar to the first one i have written have which takes argument as a array of string objects. It does not consider the second main function because it has different argument then the one which is needed. So we can have two main functions with two different arguments and one of them should be similar to the first one.

Header files

The question always comes to our mind is why we include header files?

Ans:  The answer is simple The function which we use can be define separately in .h files. .h is the extension of header files which contains the prototype of the function and also may contain the definition but for reason of abstraction we prefer to write prototype and definition in different file prototype in .h but not necessary can be written with some other extension also.

Then we write the definition to .c file compile those files make their object files and include header file to our main file and put both .h and .c file to the same folder then use the functions written in that header file. Some header files are already in-built which we can directly use like #include<stdio.h> it is a standard input output file which we can use for printf and scanf functions etc.

The advantage is our source code file's size is less. And if we want to give someone which functions are available we can give the header .h file only. No need to give .c file we can give object file so he/she will not need to understand how the implementation is happening.

Increment operator in c

Are you ready for some serious brain storming?
Here it goes my first post.

1. What would be the output of this program while running with the gnu gcc compiler?


#include<stdio.h>

int main(int argc, char * argv[]){

      int z=2;
      int y=2;
   
      z=z++;
      y=++y;
      printf("%d  %d",z,y);
 return 0;
}

Please Before proceed to answer just think for a minute.
Think ::::


This Space is left intentionally.









Although this is undefined behavior due to absence of sequence point. I will define sequence point in my future posts. But here I am presenting one of the reasons of getting this output.




Answer is  : 2 3

Reason is : For understanding the reason behind this we have to understand the execution sequence of instruction z=z++;

For evaluation of a expression compiler generates a temporary variable and evalute the expression and store the value in the temporary variable which in the given expression is 2 because postfix operator executes after the expression is evaluated. So till now the temporay variable has value 2 

and now z becomes three due to posfix operator. And then the temporary variables value is assigned to the variable which is on the left side of the = operator which here is z itself so value 2 is assigned to z again.

Finally the value of z becomes 2.

Similarly for the value of y first expression is evaluated and in this pre increment is also evaluated so value of y becomes 3 and the value of temporary variable is also becomes 3 and now this temporary variable's value is assigned to y.
Finally the value of y becomes 3.