DSA: Basics of Recursion, Pointers, and Dynamic Allocation

Jyotiprakash MishraJyotiprakash Mishra
21 min read

Recursion in C

Recursion in C is a technique where a function calls itself in order to solve a problem. Each time the function calls itself, a new stack frame is created for that call, containing its own set of local variables. This continues until a base condition is met, at which point the function stops calling itself and the stack unwinds, resolving each call in reverse order.

Here's a simple recursive function to compute the factorial of a number:

#include <stdio.h>

// Function to calculate factorial using recursion
int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1; // Base case
    }
    return n * factorial(n - 1); // Recursive case
}

int main() {
    int num = 5;
    int result = factorial(num);
    printf("Factorial of %d is %d\n", num, result);
    return 0;
}

Factorial of 5 Using a Function Call Stack

To understand how the factorial of 5 is computed using recursion, let's visualize the function call stack.

Function Call Stack for factorial(5)

    Stack Frame
    -----------
    factorial(5)
    n = 5
    return 5 * factorial(4)
    -----------           5 * factorial(4)

    Stack Frame
    -----------
    factorial(4)
    n = 4
    return 4 * factorial(3)
    -----------           5 * 4 * factorial(3)

    Stack Frame
    -----------
    factorial(3)
    n = 3
    return 3 * factorial(2)
    -----------           5 * 4 * 3 * factorial(2)

    Stack Frame
    -----------
    factorial(2)
    n = 2
    return 2 * factorial(1)
    -----------           5 * 4 * 3 * 2 * factorial(1)

    Stack Frame
    -----------
    factorial(1)
    n = 1
    return 1 (base case)
    -----------           5 * 4 * 3 * 2 * 1 = 120

Explanation of Recursion and Local Variables

Initial Call: factorial(5) is called.

    • Local Variable: n = 5

      • The function checks if n is 0 or 1. Since it is not, it proceeds to the recursive call: return 5 * factorial(4).

  2. First Recursive Call: factorial(4) is called.

    • Local Variable: n = 4

    • Again, it checks if n is 0 or 1. Since it is not, it proceeds to the recursive call: return 4 * factorial(3).

  3. Second Recursive Call: factorial(3) is called.

    • Local Variable: n = 3

    • The function proceeds to the recursive call: return 3 * factorial(2).

  4. Third Recursive Call: factorial(2) is called.

    • Local Variable: n = 2

    • The function proceeds to the recursive call: return 2 * factorial(1).

  5. Fourth Recursive Call: factorial(1) is called.

    • Local Variable: n = 1

    • This time, the base case is met (since n is 1), and the function returns 1.

  6. Unwinding the Stack:

    • The return value of factorial(1) (which is 1) is passed to factorial(2).

    • factorial(2) returns 2 * 1 = 2.

    • The return value of factorial(2) (which is 2) is passed to factorial(3).

    • factorial(3) returns 3 * 2 = 6.

    • The return value of factorial(3) (which is 6) is passed to factorial(4).

    • factorial(4) returns 4 * 6 = 24.

    • The return value of factorial(4) (which is 24) is passed to factorial(5).

    • factorial(5) returns 5 * 24 = 120.

Each recursive call creates a new stack frame with its own copy of the local variable n. When the base case is met, the stack starts to unwind, resolving each recursive call and propagating the results back up the call stack until the initial call is resolved.

Recursive Code to Find the Largest and Smallest Elements in an Array

Here's a recursive function to find the largest and smallest elements in an array:

#include <stdio.h>
#include <limits.h>

// Function to find the largest element in the array using recursion
int findLargest(int arr[], int n) {
    if (n == 1) {
        return arr[0];
    }
    int max = findLargest(arr, n - 1);
    if (arr[n - 1] > max) {
        return arr[n - 1];
    } else {
        return max;
    }
}

// Function to find the smallest element in the array using recursion
int findSmallest(int arr[], int n) {
    if (n == 1) {
        return arr[0];
    }
    int min = findSmallest(arr, n - 1);
    if (arr[n - 1] < min) {
        return arr[n - 1];
    } else {
        return min;
    }
}

int main() {
    int arr[] = {34, 15, 88, 2, 23};
    int n = sizeof(arr) / sizeof(arr[0]);

    int largest = findLargest(arr, n);
    int smallest = findSmallest(arr, n);

    printf("Largest element: %d\n", largest);
    printf("Smallest element: %d\n", smallest);

    return 0;
}

Explanation of Recursion for an Array of Size 5

Consider the array arr[] = {34, 15, 88, 2, 23}. The array size n = 5.

Function Call Stack for findLargest(arr, 5)

    Stack Frame
    -----------
    findLargest(arr, 5)
    n = 5
    max = findLargest(arr, 4)
    return max (max(88, 23))
    -----------           88

    Stack Frame
    -----------
    findLargest(arr, 4)
    n = 4
    max = findLargest(arr, 3)
    return max (max(88, 2))
    -----------           88

    Stack Frame
    -----------
    findLargest(arr, 3)
    n = 3
    max = findLargest(arr, 2)
    return max (max(88, 88))
    -----------           88

    Stack Frame
    -----------
    findLargest(arr, 2)
    n = 2
    max = findLargest(arr, 1)
    return max (max(34, 15))
    -----------           34

    Stack Frame
    -----------
    findLargest(arr, 1)
    n = 1
    return arr[0]
    -----------           34

Function Call Stack for findSmallest(arr, 5)

    Stack Frame
    -----------
    findSmallest(arr, 5)
    n = 5
    min = findSmallest(arr, 4)
    return min (min(2, 23))
    -----------           2

    Stack Frame
    -----------
    findSmallest(arr, 4)
    n = 4
    min = findSmallest(arr, 3)
    return min (min(2, 2))
    -----------           2

    Stack Frame
    -----------
    findSmallest(arr, 3)
    n = 3
    min = findSmallest(arr, 2)
    return min (min(15, 88))
    -----------           15

    Stack Frame
    -----------
    findSmallest(arr, 2)
    n = 2
    min = findSmallest(arr, 1)
    return min (min(15, 34))
    -----------           15

    Stack Frame
    -----------
    findSmallest(arr, 1)
    n = 1
    return arr[0]
    -----------           34

Explanation of Recursion and Local Variables

  1. Initial Call: findLargest(arr, 5) is called.

    • Local Variable: n = 5

    • It makes a recursive call to findLargest(arr, 4).

  2. First Recursive Call: findLargest(arr, 4) is called.

    • Local Variable: n = 4

    • It makes a recursive call to findLargest(arr, 3).

  3. Second Recursive Call: findLargest(arr, 3) is called.

    • Local Variable: n = 3

    • It makes a recursive call to findLargest(arr, 2).

  4. Third Recursive Call: findLargest(arr, 2) is called.

    • Local Variable: n = 2

    • It makes a recursive call to findLargest(arr, 1).

  5. Fourth Recursive Call: findLargest(arr, 1) is called.

    • Local Variable: n = 1

    • This time, the base case is met, and the function returns arr[0] (which is 34).

  6. Unwinding the Stack:

    • The return value of findLargest(arr, 1) (34) is passed to findLargest(arr, 2).

    • findLargest(arr, 2) compares 34 and 15, returning the larger value, which is 34.

    • The return value of findLargest(arr, 2) (34) is passed to findLargest(arr, 3).

    • findLargest(arr, 3) compares 34 and 88, returning the larger value, which is 88.

    • The return value of findLargest(arr, 3) (88) is passed to findLargest(arr, 4).

    • findLargest(arr, 4) compares 88 and 2, returning the larger value, which is 88.

    • The return value of findLargest(arr, 4) (88) is passed to findLargest(arr, 5).

    • findLargest(arr, 5) compares 88 and 23, returning the larger value, which is 88.

The same logic applies to finding the smallest element, with the difference being the comparison condition (< instead of >). Each recursive call creates a new stack frame with its own copy of the local variable n, and the stack unwinds once the base case is met, resolving each recursive call in reverse order.

Pointers in C

Pointers are variables that store the memory address of another variable. They are a powerful feature in C that allow for efficient array manipulation, dynamic memory allocation, and the creation of complex data structures like linked lists.

Defining Pointers

To define a pointer, you specify the type of data the pointer will point to, followed by an asterisk (*) and the pointer's name.

int *ptr; // Pointer to an integer
char *cptr; // Pointer to a character
float *fptr; // Pointer to a float

Assigning Addresses to Pointers

Pointers are assigned the address of a variable using the address-of operator (&).

int var = 10;
int *ptr;
ptr = &var; // ptr now holds the address of var

Dereferencing Pointers

Dereferencing a pointer means accessing the value stored at the memory address the pointer points to. This is done using the dereference operator (*).

int var = 10;
int *ptr;
ptr = &var;
int value = *ptr; // value now holds 10, which is the value at the address ptr points to

Here’s a complete example that demonstrates defining, assigning, and dereferencing pointers in C:

#include <stdio.h>

int main() {
    int var = 10;  // Define an integer variable
    int *ptr;      // Define a pointer to an integer

    ptr = &var;    // Assign the address of var to ptr

    printf("Address of var: %p\n", &var); // Print address of var
    printf("Address stored in ptr: %p\n", ptr); // Print address stored in ptr
    printf("Value of var: %d\n", var); // Print value of var
    printf("Value pointed to by ptr: %d\n", *ptr); // Dereference ptr to get value of var

    *ptr = 20;     // Change the value of var using the pointer
    printf("New value of var: %d\n", var); // Print new value of var

    return 0;
}

Explanation

  1. Defining a Pointer:

     int *ptr;

    This defines a pointer ptr that can hold the address of an integer variable.

  2. Assigning an Address to the Pointer:

     ptr = &var;

    The address of the variable var is assigned to the pointer ptr using the address-of operator &.

  3. Dereferencing the Pointer:

     int value = *ptr;

    The value stored at the address ptr points to is accessed using the dereference operator *. This assigns the value of var (which is 10) to the variable value.

  4. Changing the Value Using the Pointer:

     *ptr = 20;

    This changes the value at the address ptr points to. Since ptr points to var, the value of var is now changed to 20.

Pointer Arithmetic

Pointers can be incremented or decremented, which moves the pointer to the next or previous memory location of the type it points to.

int arr[5] = {10, 20, 30, 40, 50};
int *p = arr;

printf("%d\n", *p);   // Output: 10
p++;                  // Move to the next integer
printf("%d\n", *p);   // Output: 20

Null Pointers

A null pointer is a pointer that is not assigned any address. It is defined using the macro NULL.

int *ptr = NULL;
if (ptr == NULL) {
    printf("Pointer is null\n");
}

Double Pointers in C

Concept of Double Pointers

A double pointer is a pointer that points to another pointer. It allows for an additional level of indirection.

int var = 10;     // integer variable
int *ptr = &var;  // single pointer pointing to the integer variable
int **pptr = &ptr; // double pointer pointing to the single pointer

Let's use an example to explain how double pointers work. We will show real addresses and values.

#include <stdio.h>

int main() {
    int var = 10;     // Step 1: Create an integer variable
    int *ptr = &var;  // Step 2: Create a pointer to the integer variable
    int **pptr = &ptr; // Step 3: Create a double pointer pointing to the pointer

    printf("Address of var: %p\n", &var); // Print the address of var
    printf("Value of var: %d\n", var); // Print the value of var

    printf("Address of ptr: %p\n", &ptr); // Print the address of ptr
    printf("Value stored in ptr (Address of var): %p\n", ptr); // Print the address stored in ptr
    printf("Value pointed to by ptr (Value of var): %d\n", *ptr); // Print the value pointed to by ptr

    printf("Address of pptr: %p\n", &pptr); // Print the address of pptr
    printf("Value stored in pptr (Address of ptr): %p\n", pptr); // Print the address stored in pptr
    printf("Value pointed to by pptr (Address of var): %p\n", *pptr); // Print the address pointed to by pptr
    printf("Value pointed to by the address stored in pptr (Value of var): %d\n", **pptr); // Print the value pointed to by the address stored in pptr

    return 0;
}

Assume the following memory addresses:

  • var: Address = 0x100, Value = 10

  • ptr: Address = 0x200, Value = 0x100 (address of var)

  • pptr: Address = 0x300, Value = 0x200 (address of ptr)

Memory Layout:

Address       Variable    Value
---------     --------    -----
0x100         var         10
0x200         ptr         0x100 (address of var)
0x300         pptr        0x200 (address of ptr)

ASCII Art Representation:

pptr -> Address: 0x300, Value: 0x200 (Address of ptr)
 |
 v
ptr  -> Address: 0x200, Value: 0x100 (Address of var)
  |
  v
var   -> Address: 0x100, Value: 10

Explanation of Double Pointers

  1. Step 1: Create an Integer Variable var:

     int var = 10;

    • Memory Address: 0x100

    • Value: 10

  2. Step 2: Create a Pointer ptr to the Integer Variable:

     int *ptr = &var;

    • Memory Address: 0x200

    • Value: 0x100 (Address of var)

  3. Step 3: Create a Double Pointer pptr Pointing to the Pointer ptr:

     int **pptr = &ptr;

    • Memory Address: 0x300

    • Value: 0x200 (Address of ptr)

  4. Accessing Values and Addresses:

    • Address of var: 0x100

    • Value of var: 10

    • Address of ptr: 0x200

    • Value stored in ptr (Address of var): 0x100

    • Value pointed to by ptr (Value of var): 10

    • Address of pptr: 0x300

    • Value stored in pptr (Address of ptr): 0x200

    • Value pointed to by pptr (Address of var): 0x100

    • Value pointed to by the address stored in pptr (Value of var): 10

Use Case: Modifying a Pointer in a Function

Double pointers are particularly useful when you need to modify the value of a pointer in a function.

#include <stdio.h>
#include <stdlib.h>

// Function to allocate memory and assign the address to the double pointer
void allocateMemory(int **pptr) {
    *pptr = (int *)malloc(sizeof(int));
    **pptr = 100; // Assign a value to the allocated memory
}

int main() {
    int *ptr = NULL;
    allocateMemory(&ptr);

    if (ptr != NULL) {
        printf("Value allocated: %d\n", *ptr);
        free(ptr); // Free the allocated memory
    } else {
        printf("Memory allocation failed\n");
    }

    return 0;
}

Explanation

  1. Initial State:

    • ptr is initially NULL.

  2. Function Call:

    • allocateMemory(&ptr) is called.

    • pptr in allocateMemory is a pointer to ptr.

  3. Memory Allocation:

    • *pptr points to the allocated memory.

    • **pptr assigns the value 100 to the allocated memory.

  4. Main Function:

    • After allocateMemory, ptr points to the newly allocated memory with the value 100.

    • The allocated memory is then freed.

Before allocateMemory(&ptr):
ptr  -> Address: 0x400, Value: NULL

Inside allocateMemory:
pptr -> Address: 0x500, Value: 0x400 (Address of ptr)
 |
 v
ptr  -> Address: 0x400, Value: 0x600 (Address of allocated memory)
                       |
                       v
Allocated Memory       -> Address: 0x600, Value: 100

After allocateMemory:
ptr  -> Address: 0x400, Value: 0x600 (Address of allocated memory)
                       |
                       v
Allocated Memory       -> Address: 0x600, Value: 100

Double Pointers: Linked List Node Insertion at Head

Node Definition

A node in a linked list typically contains data and a pointer to the next node.

#include <stdio.h>
#include <stdlib.h>

// Definition of a node in a linked list
struct Node {
    int data;
    struct Node* next;
};

Creating and Linking Nodes

We will create two nodes and link them, designating one as the head and the other as the tail.

int main() {
    // Step 1: Create the first node (head)
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = NULL;

    // Step 2: Create the second node (tail)
    struct Node* tail = (struct Node*)malloc(sizeof(struct Node));
    tail->data = 2;
    tail->next = NULL;

    // Step 3: Link the first node to the second node
    head->next = tail;

    // Print the initial list
    printf("Initial linked list:\n");
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");

    // Step 4: Pointer to the head pointer (Node **)
    struct Node** headPtr = &head;

    // Step 5: Call the function to insert a new node at the head
    insertAtHead(headPtr, 0);

    // Print the updated list
    printf("Updated linked list after inserting at head:\n");
    temp = *headPtr;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");

    // Free allocated memory
    while (head != NULL) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

Function to Insert a Node at the Head

// Function to insert a new node at the head of the list
void insertAtHead(struct Node** head, int data) {
    // Step 1: Allocate memory for the new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    // Step 2: Assign data to the new node
    newNode->data = data;

    // Step 3: Set the next of the new node to the current head
    newNode->next = *head;

    // Step 4: Update the head pointer to the new node
    *head = newNode;
}

Let's assume the following memory addresses:

  • head: Address = 0x100, Value = Address of first node

  • first node: Address = 0x200, Data = 1

  • tail: Address = 0x300, Data = 2

  • new node: Address = 0x400, Data = 0

Initial State

Memory Layout:

Address       Variable   Value
---------     --------   -----
0x100         head       0x200 (Address of first node)
0x200         first node 1
0x204         next       0x300 (Address of tail)
0x300         tail       2
0x304         next       NULL

head -> 0x200
        +-------+     +-------+
        |  1    | --> |  2    | --> NULL
        +-------+     +-------+
        0x200          0x300

After Inserting a Node at the Head

Memory Layout:

Address       Variable   Value
---------     --------   -----
0x100         head       0x400 (Address of new node)
0x200         first node 1
0x204         next       0x300 (Address of tail)
0x300         tail       2
0x304         next       NULL
0x400         new node   0
0x404         next       0x200 (Address of first node)

ASCII Art:

head -> 0x400
        +-------+     +-------+     +-------+
        |  0    | --> |  1    | --> |  2    | --> NULL
        +-------+     +-------+     +-------+
        0x400          0x200          0x300

Detailed Explanation

  1. Initial Setup:

    • Create the first node (head):

        struct Node* head = (struct Node*)malloc(sizeof(struct Node));
  head->data = 1;
  head->next = NULL;

      • Memory Address: 0x200

      • Data: 1

      • Next: NULL

    • Create the second node (tail):

        struct Node* tail = (struct Node*)malloc(sizeof(struct Node));
  tail->data = 2;
  tail->next = NULL;

      • Memory Address: 0x300

      • Data: 2

      • Next: NULL

    • Link the first node to the second node:

        head->next = tail;

  2. Pointer to the Head Pointer:

     struct Node** headPtr = &head;

  3. Inserting a New Node at the Head:

    • Allocate memory for the new node:

        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = 0;
  newNode->next = *head;

      • Memory Address: 0x400

      • Data: 0

      • Next: 0x200 (Address of the current head)

    • Update the head pointer to the new node:

        *head = newNode;

Updated Linked List

  • Head now points to the new node.

  • The new node points to the previous head node.

  • The previous head node points to the tail node.

Without Double Pointers:

Instead of using a Node** to pass the head pointer to the function, we can have the function return a new head pointer (Node*). The new head pointer can then be assigned to the head in the main function.

Creating and Linking Nodes

We will create two nodes and link them, designating one as the head and the other as the tail.

int main() {
    // Step 1: Create the first node (head)
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = NULL;

    // Step 2: Create the second node (tail)
    struct Node* tail = (struct Node*)malloc(sizeof(struct Node));
    tail->data = 2;
    tail->next = NULL;

    // Step 3: Link the first node to the second node
    head->next = tail;

    // Print the initial list
    printf("Initial linked list:\n");
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");

    // Step 4: Call the function to insert a new node at the head
    head = insertAtHead(head, 0);

    // Print the updated list
    printf("Updated linked list after inserting at head:\n");
    temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");

    // Free allocated memory
    while (head != NULL) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

Function to Insert a Node at the Head

// Function to insert a new node at the head of the list
struct Node* insertAtHead(struct Node* head, int data) {
    // Step 1: Allocate memory for the new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    // Step 2: Assign data to the new node
    newNode->data = data;

    // Step 3: Set the next of the new node to the current head
    newNode->next = head;

    // Step 4: Return the new node as the new head
    return newNode;
}

Let's assume the following memory addresses:

  • head: Address = 0x100, Value = Address of first node

  • first node: Address = 0x200, Data = 1

  • tail: Address = 0x300, Data = 2

  • new node: Address = 0x400, Data = 0

Initial State

Memory Layout:

Address       Variable   Value
---------     --------   -----
0x100         head       0x200 (Address of first node)
0x200         first node 1
0x204         next       0x300 (Address of tail)
0x300         tail       2
0x304         next       NULL

head -> 0x200
        +-------+     +-------+
        |  1    | --> |  2    | --> NULL
        +-------+     +-------+
        0x200          0x300

After Inserting a Node at the Head

Memory Layout:

Address       Variable   Value
---------     --------   -----
0x100         head       0x400 (Address of new node)
0x200         first node 1
0x204         next       0x300 (Address of tail)
0x300         tail       2
0x304         next       NULL
0x400         new node   0
0x404         next       0x200 (Address of first node)

ASCII Art:

head -> 0x400
        +-------+     +-------+     +-------+
        |  0    | --> |  1    | --> |  2    | --> NULL
        +-------+     +-------+     +-------+
        0x400          0x200          0x300

Detailed Explanation

  1. Initial Setup:

    • Create the first node (head):

        struct Node* head = (struct Node*)malloc(sizeof(struct Node));
  head->data = 1;
  head->next = NULL;

      • Memory Address: 0x200

      • Data: 1

      • Next: NULL

    • Create the second node (tail):

        struct Node* tail = (struct Node*)malloc(sizeof(struct Node));
  tail->data = 2;
  tail->next = NULL;

      • Memory Address: 0x300

      • Data: 2

      • Next: NULL

    • Link the first node to the second node:

        head->next = tail;

  2. Inserting a New Node at the Head:

    • Allocate memory for the new node:

        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = 0;
  newNode->next = head;

      • Memory Address: 0x400

      • Data: 0

      • Next: 0x200 (Address of the current head)

    • Return the new node as the new head:

        return newNode;

  3. Main Function Updates the Head:

    • Assign the returned new node as the new head:

        head = insertAtHead(head, 0);

Updated Linked List

  • Head now points to the new node.

  • The new node points to the previous head node.

  • The previous head node points to the tail node.

This process demonstrates how to insert a new node at the head of a linked list using a Node* function that returns the new head, providing flexibility and control over the data structure.

Dynamic Memory in C

Dynamic memory in C refers to memory that is allocated during runtime using functions from the standard library, such as malloc, calloc, realloc, and free. This memory is managed on the heap, allowing for flexible and efficient use of memory resources.

Here's a simple program that demonstrates dynamic memory allocation using malloc:

#include <stdio.h>
#include <stdlib.h>

int main() {
    // Step 1: Declare a pointer
    int *ptr;

    // Step 2: Allocate memory dynamically
    ptr = (int *)malloc(sizeof(int));

    // Step 3: Check if the memory allocation was successful
    if (ptr == NULL) {
        printf("Memory allocation failed\n");
        return 1;
    }

    // Step 4: Assign a value to the allocated memory
    *ptr = 42;

    // Step 5: Print the value and the address
    printf("Value: %d\n", *ptr);
    printf("Address of allocated memory: %p\n", (void *)ptr);

    // Step 6: Free the allocated memory
    free(ptr);

    return 0;
}

Process Memory Map Explanation

The memory map of a process typically includes the following segments:

  • Code Segment: Contains the executable code.

  • Data Segment: Contains global and static variables.

  • Heap Segment: Used for dynamic memory allocation.

  • Stack Segment: Used for function call frames, local variables, and pointers.

Assume the following hypothetical memory addresses for illustration purposes:

  • Code Segment: Starts at 0x400000

  • Data Segment: Starts at 0x600000

  • Heap Segment: Starts at 0x800000

  • Stack Segment: Starts at 0xFFFC0000 and grows downwards

Process Memory Map with Dynamic Memory Allocation

  1. Code Segment:

    • The compiled code of the program is loaded here.

  2. Data Segment:

    • Stores global and static variables.

  3. Heap Segment:

    • Dynamically allocated memory using malloc is located here.

  4. Stack Segment:

    • Stores function call frames and local variables.

Memory Layout Example with Addresses and Values

Let's assume the following addresses and values for our example:

  • ptr (in main stack frame): Address = 0xFFFC0010

  • Allocated memory (in heap): Address = 0x80001000, Value = 42

Initial State (Before malloc)

Memory Map:

Address          Segment         Variable/Value
-------------    -----------     -----------------
0x400000         Code            Program Code
0x600000         Data            Global/Static Variables
0x800000         Heap            <Empty>
0xFFFC0000       Stack           main()
                                +------------------+
                                | Return Address   |
                                |------------------|
                                | Other Local Vars |
                                |------------------|
                                | ptr              | --> Initially uninitialized
                                +------------------+

After malloc

Memory Map:

Address          Segment         Variable/Value
-------------    -----------     -----------------
0x400000         Code            Program Code
0x600000         Data            Global/Static Variables
0x80001000       Heap            Value = 42
0xFFFC0000       Stack           main()
                                +------------------+
                                | Return Address   |
                                |------------------|
                                | Other Local Vars |
                                |------------------|
0xFFFC0010       ptr             0x80001000 (Address of allocated memory)
                                +------------------+

After Assignment

Memory Map:

Address          Segment         Variable/Value
-------------    -----------     -----------------
0x400000         Code            Program Code
0x600000         Data            Global/Static Variables
0x80001000       Heap            Value = 42
0xFFFC0000       Stack           main()
                                +------------------+
                                | Return Address   |
                                |------------------|
                                | Other Local Vars |
                                |------------------|
0xFFFC0010       ptr             0x80001000 (Address of allocated memory)
                                +------------------+

Detailed Explanation

  1. Declare a Pointer:

     int *ptr;

    • Memory Address: 0xFFFC0010 (stack frame of main)

    • Value: Uninitialized

  2. Allocate Memory Dynamically:

     ptr = (int *)malloc(sizeof(int));

    • Allocates memory on the heap.

    • Memory Address: 0x80001000

    • Value: 0x80001000 is stored in ptr.

  3. Check Memory Allocation:

     if (ptr == NULL) {
     printf("Memory allocation failed\n");
     return 1;
 }
    • Ensures malloc was successful.

  4. Assign a Value to Allocated Memory:

     *ptr = 42;

    • Memory Address: 0x80001000

    • Value: 42

  5. Print the Value and Address:

     printf("Value: %d\n", *ptr);
 printf("Address of allocated memory: %p\n", (void *)ptr);

    • Output:

        Value: 42
  Address of allocated memory: 0x80001000

  6. Free the Allocated Memory:

     free(ptr);
    • Releases the memory allocated on the heap.

The pointer ptr resides in the stack frame of the main function, but it points to a memory location in the heap. This separation of pointer and allocated memory locations is crucial for understanding how dynamic memory management works in C. This approach provides flexibility in managing memory, especially for dynamic data structures and variable-sized data.

33
Subscribe to my newsletter

Read articles from Jyotiprakash Mishra directly inside your inbox. Subscribe to the newsletter, and don't miss out.

DSAdata structuresdynamic memory allocationpointersdouble pointerRecursion

Written by

Jyotiprakash Mishra
Jyotiprakash Mishra

I am Jyotiprakash, a deeply driven computer systems engineer, software developer, teacher, and philosopher. With a decade of professional experience, I have contributed to various cutting-edge software products in network security, mobile apps, and healthcare software at renowned companies like Oracle, Yahoo, and Epic. My academic journey has taken me to prestigious institutions such as the University of Wisconsin-Madison and BITS Pilani in India, where I consistently ranked among the top of my class. At my core, I am a computer enthusiast with a profound interest in understanding the intricacies of computer programming. My skills are not limited to application programming in Java; I have also delved deeply into computer hardware, learning about various architectures, low-level assembly programming, Linux kernel implementation, and writing device drivers. The contributions of Linus Torvalds, Ken Thompson, and Dennis Ritchie—who revolutionized the computer industry—inspire me. I believe that real contributions to computer science are made by mastering all levels of abstraction and understanding systems inside out. In addition to my professional pursuits, I am passionate about teaching and sharing knowledge. I have spent two years as a teaching assistant at UW Madison, where I taught complex concepts in operating systems, computer graphics, and data structures to both graduate and undergraduate students. Currently, I am an assistant professor at KIIT, Bhubaneswar, where I continue to teach computer science to undergraduate and graduate students. I am also working on writing a few free books on systems programming, as I believe in freely sharing knowledge to empower others.