Scribd
Upload
19 views8 pages

C Programming Recursion, Structures & Unions

The document provides comprehensive exam notes on recursion, structures, and unions in C programming, detailing their definitions, advantages, disadvantages, and examples. It covers recursive functions, mathematical functions, and their implementations, as well as the use of structures and unions, including their syntax and memory allocation differences. Each section includes sample programs and outputs to illustrate concepts effectively.

Uploaded by

Sateesh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views8 pages

C Programming Recursion, Structures & Unions

The document provides comprehensive exam notes on recursion, structures, and unions in C programming, detailing their definitions, advantages, disadvantages, and examples. It covers recursive functions, mathematical functions, and their implementations, as well as the use of structures and unions, including their syntax and memory allocation differences. Each section includes sample programs and outputs to illustrate concepts effectively.

Uploaded by

Sateesh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

RECURSION, STRUCTURES & UNIONS – COMPLETE EXAM NOTES

Prepared for Students – Full Theory + Programs + Outputs

========================================================
UNIT 1 – RECURSION
========================================================

1. INTRODUCTION TO RECURSION
Recursion is a method in C programming where a function calls itself until a terminating condition
(base case) is reached.
Every recursive function has:
1) Base Case – stops recursion.
2) Recursive Case – calls the function again with modified parameters.
3) Stack Frames – Each recursive call is stored separately on stack memory.

Advantages:
• Reduces code complexity.
• Useful for tasks that have repetitive subproblems (tree traversal, factorial).

Disadvantages:
• Slower due to function call overhead.
• Risk of stack overflow.
• Iterative solutions are often more memory-efficient.

--------------------------------------------------------
2. NATURE OF RECURSION (DETAILED EXPLANATION)
--------------------------------------------------------
A recursive function must always include:
• A BASE CONDITION to avoid infinite recursion.
• A REDUCTION to move toward the base case.

General Template:
returnType function(parameters)
{
if(base_condition)
return value;
else
return (recursive_call);
}

Example – Factorial:
fact(5) = 5 × 4 × 3 × 2 × 1
Stack Diagram:
fact(5)
■ fact(4)
■ fact(3)
■ fact(2)
■ fact(1)
■ fact(0)

--------------------------------------------------------
3. TRACING A RECURSIVE FUNCTION
--------------------------------------------------------
Example:
int fact(int n)
{
if(n==0) return 1;
return n * fact(n-1);
}

Trace for fact(4):


Step 1: fact(4) → 4 * fact(3)
Step 2: fact(3) → 3 * fact(2)
Step 3: fact(2) → 2 * fact(1)
Step 4: fact(1) → 1 * fact(0)
Step 5: fact(0) = 1

Return Sequence:
fact(1)=1
fact(2)=2
fact(3)=6
fact(4)=24

--------------------------------------------------------
4. RECURSIVE MATHEMATICAL FUNCTIONS
--------------------------------------------------------

A) Factorial Function
Program:
int fact(int n)
{
if(n==0)
return 1;
return n * fact(n-1);
}

Output:
Factorial of 5 = 120

B) Fibonacci Series
Definition:
F(0)=0, F(1)=1
F(n)=F(n-1)+F(n-2)

Program:
int fib(int n)
{
if(n==0 || n==1)
return n;
return fib(n-1) + fib(n-2);
}

Output:
fib(6) = 8

C) Sum of Digits
Program:
int sum(int n)
{
if(n==0)
return 0;
return (n%10) + sum(n/10);
}

Output:
sum(1234)=10

D) GCD Using Recursion


gcd(a,b)=gcd(b,a%b)

Program:
int gcd(int a, int b)
{
if(b==0)
return a;
return gcd(b, a%b);
}

--------------------------------------------------------
5. RECURSION WITH ARRAYS
--------------------------------------------------------
A) Printing Array Elements

void printArr(int a[], int i, int n)


{
if(i==n) return;
printf("%d ", a[i]);
printArr(a, i+1, n);
}

Output:
10 20 30 40

B) Sum of Array Elements

int sumArr(int a[], int n)


{
if(n==0)
return 0;
return a[n-1] + sumArr(a, n-1);
}

--------------------------------------------------------
6. RECURSION WITH STRINGS
--------------------------------------------------------

A) Length of String
int strlenRec(char str[])
{
if(str[0]=='\0')
return 0;
return 1 + strlenRec(str+1);
}

Output:
Length of HELLO = 5

B) Reverse a String
void reverse(char str[], int index)
{
if(str[index]=='\0')
return;
reverse(str, index+1);
printf("%c", str[index]);
}

Output:
OLLEH

========================================================
UNIT 2 – STRUCTURES
========================================================

1. INTRODUCTION TO STRUCTURES
Structure is a user-defined datatype that groups multiple different datatypes into a single unit.

Syntax:
struct Student {
int roll;
char name[20];
float marks;
};

Memory Layout:
| roll (int) |
| name[20] |
| marks(float)|

--------------------------------------------------------
2. DECLARING AND INITIALIZING STRUCTURES
--------------------------------------------------------
struct Student s1 = {101, "Ravi", 88.5};

--------------------------------------------------------
3. ACCESSING STRUCTURE MEMBERS
--------------------------------------------------------
[Link] = 101;
strcpy([Link], "Ravi");
[Link] = 88.5;

--------------------------------------------------------
4. STRUCTURES AS FUNCTION ARGUMENTS
--------------------------------------------------------
A) Structure Passed by Value
void display(struct Student s)
{
printf("%d %s %.2f", [Link], [Link], [Link]);
}

Program:
struct Student s1={101,"Ravi",88.5};
display(s1);

Output:
101 Ravi 88.50

B) Structure Passed by Reference


void update(struct Student *s)
{
s->marks = 90.5;
}

--------------------------------------------------------
5. FUNCTIONS RETURNING STRUCTURES
--------------------------------------------------------

struct Student read()


{
struct Student s;
scanf("%d%s%f", &[Link];, [Link], &[Link];);
return s;
}

--------------------------------------------------------
6. NESTED STRUCTURES
--------------------------------------------------------
struct Date { int d,m,y; };
struct Student {
int roll;
struct Date dob;
};

--------------------------------------------------------
7. ARRAY OF STRUCTURES
--------------------------------------------------------
struct Student s[3];
Example:
s[0].roll = 101;
strcpy(s[0].name,"Ravi");

========================================================
UNIT 3 – UNIONS
========================================================

1. INTRODUCTION TO UNIONS
A union is similar to a structure but uses a single shared memory location for all members.

Syntax:
union Data {
int i;
float f;
char ch;
};

Memory:
Only largest datatype memory is allocated.

--------------------------------------------------------
2. PROGRAM USING UNION
--------------------------------------------------------
union Data d;

d.i=10; → prints 10
d.f=3.14; → overwrites memory
[Link]='A'; → overwrites memory

Output:
i = 10
f = 3.14
ch = A

--------------------------------------------------------
3. DIFFERENCE BETWEEN STRUCTURE & UNION
--------------------------------------------------------

Structure:
• Allocates memory for all members.
• Can store multiple values.

Union:
• Memory equals largest member only.
• Can hold only one value at a time.

Example:
struct { int a; float b; }; → size = sizeof(int)+sizeof(float)
union { int a; float b; }; → size = max(sizeof(int),sizeof(float))

========================================================
END OF COMPLETE NOTES
========================================================

Common questions

Powered by AI

Structures allow grouping multiple different datatypes into a single cohesive unit, enabling more flexible and readable code compared to arrays, which only store elements of the same datatype. Structures facilitate the organization of complex data such as databases and records, which require various data types under a single entity for easier access and manipulation. This advantage makes structures more suitable for applications like managing student records or complex configurations .

To trace the execution sequence of a recursive function like factorial, follow each function call: factorizing the number and calling the function again with a reduced number until reaching the base case. For instance, with factorial(4), the sequence is: fact(4) → 4 * fact(3), fact(3) → 3 * fact(2), fact(2) → 2 * fact(1), fact(1) → 1 * fact(0), and fact(0) = 1. This trace helps visualize recursive call depths and stack usage .

Not properly defining a base case in recursive functions can lead to infinite recursion, causing a program to run indefinitely and potentially crash with a stack overflow. This can be mitigated by ensuring a base case is correctly defined to terminate the recursion once a certain condition is met. Additionally, thorough testing and validation of recursive algorithms can help identify and rectify missing or incorrect base cases .

A recursive function must include a base case and a recursive case. The base case prevents infinite recursion by serving as a terminating condition. The recursive case progresses the computation by reducing the complexity, bringing the function closer to resolving the base case. Without these components, a recursive function would not complete successfully and could result in infinite recursion .

In recursion, stack frames are used to store information about the function's execution state at each recursive call. Each call to a recursive function results in a new stack frame being placed on the call stack, containing parameters, return addresses, and local variables. This is essential for tracking each function call and correctly returning results as the recursion unwinds. However, excessive stack usage can lead to stack overflow, making it a critical aspect of recursive function resource management .

Recursive functions can reduce code complexity and are suited for tasks with repetitive subproblems such as tree traversal and calculating factorials. However, they often have higher function call overhead, leading to slower performance compared to iterative solutions. Recursive functions risk stack overflow due to their use of stack memory for each call, making iterative solutions generally more memory-efficient .

Structures can represent nested data entities by allowing one structure to contain another as a member. This provides a robust way to model complex relationships, such as a `Student` structure containing a `Date` structure to represent a student's birth date. For example: `struct Date { int d, m, y; }; struct Student { int roll; struct Date dob; };` Here, `Student` has a nested `Date` for the student's date of birth, allowing comprehensive data modeling .

Recursive functions are often preferred for tree traversal due to their natural alignment with the tree's recursive structure. Each recursive call processes a node and its subtrees, breaking down the traversal of a tree into simpler, repeated subproblems. This method reduces code complexity and aligns well with recursive iteration patterns, like pre-order, in-order, and post-order traversals, that inherently mirror the recursive nature of calling nodes and their children .

The GCD (Greatest Common Divisor) function computes the greatest common divisor using recursion by repeatedly applying the Euclidean algorithm: gcd(a, b) = gcd(b, a % b). The function recursively calls itself with a and b swapped, and b replaced by a % b, until the base case where b equals zero is reached. At this point, a holds the greatest common divisor, which is returned by the function .

A union differs from a structure in that it allocates memory equal to its largest member, sharing the memory location among all its members. This means that a union can only store one of its member values at any given time, whereas a structure allocates separate memory for each member, allowing it to simultaneously hold multiple values. This memory characteristic makes unions more memory-efficient in scenarios where only one member is needed but limits its data storage capabilities compared to structures .

You might also like