#004 DS&A - Structures and Recursion
Tags: datastructures, algorithms
Published: 2020-08-27 10:34:45

# Introduction

Nothing to say more than hello 👋,
In Case your wondering who is this man in the banner it's the Khwarizmi the inventor of algorithms concept.
Make sure to follow because I will start more advanced series in future.

## Structures

### Introduction to structures

We use arrays when we have elements of same type. We use structures when we have elements of different types like name and age one is integer and other is string.

we define structure like this

```c
struct
{
    int i;
    char c;
} x, y , z;

x.i = 10;
x.c = 'a';
```

now each of `x , y and z` will have `i` and `c` for them self.

we can have structure inside structure

```c
struct {
    struct {
        ...
    }
}
```

we can use a tag with `struct`

```C
//this called blueprint and no memory allocated
struct ex 
{
    int i;
    char c;
};
struct ex1
{
    struct ex a;
    struct ex b;
};

// here space will be allocated
struct ex x = {5,'a'};
struct ex1 t;
t.a.i = 10;
t.a.c = 'a';
```

### examples

**example 1**

```c
struct node
{
    int i;
    int j;
}

struct node a,*p; 
// a is struct of type node
// p is a pointer which point to struct node
p = &a;
// *p.i this is wrong because compiler will treat it like *(p.i) 
(*p).i = 10;
p->i = 10;
```

accessing it using pointer is commonly used because if it's created using `malloc` it will not have a name , so programmers introduced a new operator `->` 

**example 2**

```c
struct node
{
    int i;
    int *c;
};
struct node a[2] , *p;
int b[2] = {30 , 40};
p = &a[0];
a[0].i = 10;
a[1].i = 20;
a[0].c = b;
```

![image-20200827102423504](https://i.loli.net/2020/08/27/qFzEeHUBnXj6yT5.png)

that we have till now orange arrow mean pointing to

```c
// assume we are resetting every thing after each line
// x = i++ , will take x = i , then after it assign it i will be i+1
++p -> i; // (++(p->i)) , a[0].i will be 11
x=(++p)->i; // p will point to a[1] then x = 20
x=(p++)->i; // x = 10 , then p will point to a[1]
x=*p->c; // *(p->c) , x = 30
x=*p->c++; //  (*((p->c)++)) , x = 30 then c will change it's pointing
x=(*p->c)++; // (*(p->c))++ , x = 30 after that b[0] = 31 
x=*p++->c; // (*( (p++) -> c)) , x = 30
```

### self referential structures

```c
struct ex
{
    int i;
    struct ex *link;
}
struct ex abc;
```

those are used in trees and linked list.

> you need to make sure before using an pointer that you are already created it or you will get segmentation error

### malloc

global variables will be allocated in stack before your program run.

dynamically allocated will be creating in memory.

![image-20200827110120761](https://i.loli.net/2020/08/27/dQGIH9lMvrPmx2k.png)

the stack will grow and allocated most of the space or heap will , or they will both occupy same size. We can ask for a space in the heap and use them.

The Operation system will decide the size of the process.

in Unix `sblk(n)` will give you pointer of n bytes from the operation system inside the heap and use it.

in C we have `malloc()` will ask from the operation system to that system call what ever the system is.

for efficiencies you can call system directly. 

```c
void* malloc(int);
```

this will create an empty memory and it will return the pointer of it.

```c
int* p = (int*) malloc(2); // 2 bytes
*p = 100;
```

if we hard coded like this it may work on our system but other systems have 4 bytes to integer so it will fail.

```c
int *p = (int*)malloc(sizeof(int)); // it will replace with system size of int
free(p);
```

it will take 4 bytes to the first available space that it will found in heap , if not it will go to operation system to create one.

```c
struct node
{
    int i;
    struct node *l;
};
struct node *p = (struct node*) malloc(sizeof(struct node));
// this how we create a structure
// we can access it using p->i
```

## Recursion

```pseudocode
A(n)
{
    if(n>0)//1
    {//2
        printf("%d" , n-1);//3
        A(n-1);//4
    }//5
}

main() {
 A(3)
 ...// line i
}
//output : 2 1 0
```

![image-20200827130902875](https://i.loli.net/2020/08/27/eqD3ySMdacfO8It.png)

then when it return it will start to delete the stacks

![image-20200827131022721](https://i.loli.net/2020/08/27/sGpSlo3Xn6HRCbf.png)

required stacks are `A(n) = n+1 = O(n)`

time complexity `T(n)=c+T(n-1)`

![image-20200827131646449](https://i.loli.net/2020/08/27/q9j8a5k6zJvsXuM.png)

this is another method if the program is small to represent the stack.

```pseudocode
A(n)
{
	if(n>0)
	{
		pf(n);
		A(n-1);
		pf(n);
	}
}
// output : 3 2 1 1 2 3
```

`T(n) = c+T(n-1)`

![image-20200827132256039](https://i.loli.net/2020/08/27/pIK1b2WNtVCGlcd.png)

```pseudocode
A(n)
{
	if(n>0)
	{
		A(n-1);
		pf(n);
		A(n-1);
	}
}
// output : 1 2 1
```

![image-20200827132648769](https://i.loli.net/2020/08/27/O2suZpNbYWRgDKv.png)

only 3 stacks are required here , because we don't repeat A(n) if it's already calculated.