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>
int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
}
return n * factorial(n - 1);
}
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).
First Recursive Call: factorial(4) is called.
Second Recursive Call: factorial(3) is called.
Third Recursive Call: factorial(2) is called.
Fourth Recursive Call: factorial(1) is called.
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>
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;
}
}
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
Initial Call: findLargest(arr, 5) is called.
First Recursive Call: findLargest(arr, 4) is called.
Second Recursive Call: findLargest(arr, 3) is called.
Third Recursive Call: findLargest(arr, 2) is called.
Fourth Recursive Call: findLargest(arr, 1) is called.
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;
char *cptr;
float *fptr;
Assigning Addresses to Pointers
Pointers are assigned the address of a variable using the address-of operator (&).
int var = 10;
int *ptr;
ptr = &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;
Here’s a complete example that demonstrates defining, assigning, and dereferencing pointers in C:
#include <stdio.h>
int main() {
int var = 10;
int *ptr;
ptr = &var;
printf("Address of var: %p\n", &var);
printf("Address stored in ptr: %p\n", ptr);
printf("Value of var: %d\n", var);
printf("Value pointed to by ptr: %d\n", *ptr);
*ptr = 20;
printf("New value of var: %d\n", var);
return 0;
}
Explanation
Defining a Pointer:
int *ptr;
This defines a pointer ptr that can hold the address of an integer variable.
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 &.
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.
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);
p++;
printf("%d\n", *p);
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;
int *ptr = &var;
int **pptr = &ptr;
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;
int *ptr = &var;
int **pptr = &ptr;
printf("Address of var: %p\n", &var);
printf("Value of var: %d\n", var);
printf("Address of ptr: %p\n", &ptr);
printf("Value stored in ptr (Address of var): %p\n", ptr);
printf("Value pointed to by ptr (Value of var): %d\n", *ptr);
printf("Address of pptr: %p\n", &pptr);
printf("Value stored in pptr (Address of ptr): %p\n", pptr);
printf("Value pointed to by pptr (Address of var): %p\n", *pptr);
printf("Value pointed to by the address stored in pptr (Value of var): %d\n", **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
Step 1: Create an Integer Variable var:
int var = 10;
Memory Address: 0x100
Value: 10
Step 2: Create a Pointer ptr to the Integer Variable:
int *ptr = &var;
Step 3: Create a Double Pointer pptr Pointing to the Pointer ptr:
int **pptr = &ptr;
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>
void allocateMemory(int **pptr) {
*pptr = (int *)malloc(sizeof(int));
**pptr = 100;
}
int main() {
int *ptr = NULL;
allocateMemory(&ptr);
if (ptr != NULL) {
printf("Value allocated: %d\n", *ptr);
free(ptr);
} else {
printf("Memory allocation failed\n");
}
return 0;
}
Explanation
Initial State:
Function Call:
Memory Allocation:
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>
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() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = NULL;
struct Node* tail = (struct Node*)malloc(sizeof(struct Node));
tail->data = 2;
tail->next = NULL;
head->next = tail;
printf("Initial linked list:\n");
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
struct Node** headPtr = &head;
insertAtHead(headPtr, 0);
printf("Updated linked list after inserting at head:\n");
temp = *headPtr;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
while (head != NULL) {
struct Node* temp = head;
head = head->next;
free(temp);
}
return 0;
}
Function to Insert a Node at the Head
void insertAtHead(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = *head;
*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
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;
Pointer to the Head Pointer:
struct Node** headPtr = &head;
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;
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() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = NULL;
struct Node* tail = (struct Node*)malloc(sizeof(struct Node));
tail->data = 2;
tail->next = NULL;
head->next = tail;
printf("Initial linked list:\n");
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
head = insertAtHead(head, 0);
printf("Updated linked list after inserting at head:\n");
temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
while (head != NULL) {
struct Node* temp = head;
head = head->next;
free(temp);
}
return 0;
}
Function to Insert a Node at the Head
struct Node* insertAtHead(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = 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
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;
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;
Return the new node as the new head:
return newNode;
Main Function Updates the Head:
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() {
int *ptr;
ptr = (int *)malloc(sizeof(int));
if (ptr == NULL) {
printf("Memory allocation failed\n");
return 1;
}
*ptr = 42;
printf("Value: %d\n", *ptr);
printf("Address of allocated memory: %p\n", (void *)ptr);
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
Code Segment:
- The compiled code of the program is loaded here.
Data Segment:
- Stores global and static variables.
Heap Segment:
- Dynamically allocated memory using
malloc is located here.
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
Declare a Pointer:
int *ptr;
Allocate Memory Dynamically:
ptr = (int *)malloc(sizeof(int));
Allocates memory on the heap.
Memory Address: 0x80001000
Value: 0x80001000 is stored in ptr.
Check Memory Allocation:
if (ptr == NULL) {
printf("Memory allocation failed\n");
return 1;
}
- Ensures
malloc was successful.
Assign a Value to Allocated Memory:
*ptr = 42;
Print the Value and Address:
printf("Value: %d\n", *ptr);
printf("Address of allocated memory: %p\n", (void *)ptr);
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.