Function
A function is a named, reusable block of statements that performs a specific task.
A function is an independent program unit written separatley from main program to perform a specific opertation or task.
Functions divide a program into smaller, manageable and reusable modules.
Basic Structure of a Function
return_type function_name(parameter_list)
{
// Function Body
statements;
return value;
}
Example
int add(int a, int b)
{
int sum;
sum = a + b;
return sum;
}
Here:
int-Type of value returned by function
Function Name-add (Name used to call the function)
Parameters- int a, int b (Values received by the function)
Function Header
int add(int a, int b)
Function declaration line containing name, return type and parameters
Function Body-Statements executed by the function
{ ... }
Return Statement-Sends result back to caller
return sum;
Function Declaration / Prototype
A function declaration tells the compiler about the function before it is used.
Syntax
return_type function_name(parameter_list);
Example
int add(int a, int b);
This is called the function prototype or declaration.
2. Function Header
The function header is the first line of the function definition. It specifies the return type, function name and parameters.
int add(int a, int b)
It consists of:
int add (int a, int b)
↑ ↑ ↑
Return Function Parameters
Type Name
3. Function Body
The function body contains the statements that perform the actual operation.
{
int sum;
sum = a + b;
return sum;
}
Therefore:
int add(int a, int b) // Function Header
{
int sum; // Function Body
sum = a + b;
return sum;
}
4. Function Definition
A function definition contains the complete implementation of a function, including its header and body.
int add(int a, int b)
{
int sum;
sum = a + b;
return sum;
}
Function Definition = Function Header + Function Body
5. Passing Values to Functions
Values can be passed to a function through arguments.
int result;
result = add(10, 20);
Here:
10 → a
20 → b
The values 10 and 20 are called arguments or actual parameters.
The parameters a and b in the function definition are called formal parameters.
int add(int a, int b)
6. Call by Value
In call by value, a copy of the actual value is passed to the function.
Any change made to the parameter inside the function does not change the original variable.
Example
#include <stdio.h>
void change(int x)
{
x = 100;
}
int main()
{
int a = 10;
change(a);
printf("%d", a);
return 0;
}
Output 10. Although x becomes 100, the original a remains 10.
Representation
main()
|
| a = 10
↓
change(a)
|
| copy of a
↓
x = 10
|
| x = 100
↓
Original a = 10
Function Header
void change(int x);
Here x is passed by value.
7. Call by Reference in C
Strictly speaking, C does not provide true call-by-reference as a language feature. C achieves reference-like behavior by passing the address of a variable using a pointer.
Example
#include <stdio.h>
void change(int *x)
{
*x = 100;
}
int main()
{
int a = 10;
change(&a);
printf("%d", a);
return 0;
}
Output
100
Here:
change(&a);
passes the address of a.
Inside the function:
*x = 100;
changes the value stored at that address.
Representation
main()
a = 10
|
| &a
↓
change(int *x)
|
| x points to a
↓
*x = 100
|
↓
a = 100
8. Call by Value vs Reference-Like Passing
Feature. Call by Value Reference-like Passing in C
Mechanism Value is copied Address is passed
Parameter int x int *x
Function call change(a) change(&a)
Original value changed? No Yes
Uses pointer? No Yes
Example void change(int x) void change(int *x)
9. Example: Swap Using Call by Value
void swap(int a, int b)
{
int temp;
temp = a;
a = b;
b = temp;
}
Call:
swap(x, y);
The original x and y will not be swapped because copies are passed.
10. Swap Using Reference-Like Passing
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
Call:
swap(&x, &y);
Now the original values of x and y are swapped.
Key Concept
CALL BY VALUE
variable → value → function
↓
copy
REFERENCE-LIKE PASSING IN C
variable → address → pointer → original variable
Application in Data Structures
This concept is especially important in data structures:
void push(Stack *s, int value);
void enqueue(Queue *q, int value);
void insertBeginning(Node **head, int value);
The pointer allows the function to modify the original data structure, while individual values such as int value are normally passed by value.
1. Recursive Problem
A recursive problem is a problem whose solution can be defined in terms of smaller instances of the same problem.
A recursive problem generally contains two essential parts:
Base Case – the condition that stops recursion.
Recursive Case – the part where the function calls itself with a smaller or simpler input.
Example: Factorial
Mathematically:
n! = n × (n − 1)!
0! = 1
For example:
5! = 5 × 4!
= 5 × 4 × 3!
= 5 × 4 × 3 × 2!
= 5 × 4 × 3 × 2 × 1!
= 120
2. Recursion
Recursion is a programming technique in which a function calls itself, directly or indirectly, to solve a smaller instance of the same problem.
General Structure in C
return_type function(parameters)
{
if (base_condition)
return base_value;
return function(smaller_problem);
}
Example: Factorial in C
int factorial(int n)
{
if (n == 0)
return 1; // Base case
return n * factorial(n - 1); // Recursive case
}
Function call:
int result = factorial(5);
3. Recursion as a Technique to Solve Recursive Problems
The general approach is:
Identify the Problem
↓
Identify the Base Case
↓
Identify the Smaller Problem
↓
Write the Recursive Call
↓
Combine the Result
↓
Check Termination
Example: Sum of First n Natural Numbers
Problem: Sum(n) = 1 + 2 + 3 + ... + n
Recursive definition: Sum(n) = n + Sum(n − 1)
Base Case: Sum(0) = 0
C implementation:
int sum(int n)
{
if (n == 0)
return 0;
return n + sum(n - 1);
}
For: sum(5); Execution conceptually becomes:
sum(5)
↓
5 + sum(4)
↓
4 + sum(3)
↓
3 + sum(2)
↓
2 + sum(1)
↓
1 + sum(0)
↓
0
Result:
5 + 4 + 3 + 2 + 1 = 15
4. Types of Recursion
Recursion can be classified according to how recursive calls are made and where they occur.
RECURSION
│
┌──────────────┴──────────────┐
│ │
Based on Calling Pattern Based on Position
│ │
┌─────┼─────┐ ┌─────┴─────┐
│ │ │ │ │
Direct Indirect Mutual Tail Non-Tail
5. Direct Recursion
Direct recursion occurs when a function calls itself directly.
Example
void fun(int n)
{
if (n > 0)
{
printf("%d ", n);
fun(n - 1);
}
}
Here:
fun() → fun() → fun() → fun()
The function directly calls itself.
Examples
Factorial
Fibonacci
Sum of numbers
Tree traversal
Binary search
6. Indirect Recursion
Indirect recursion occurs when one function calls another function, which eventually calls the first function.
Example:
void A(int n)
{
if (n > 0)
B(n - 1);
}
void B(int n)
{
if (n > 0)
A(n - 1);
}
Calling sequence:
A()
↓
B()
↓
A()
↓
B()
Neither function necessarily calls itself directly, but recursion occurs through another function.
7. Mutual Recursion
Mutual recursion is a form of indirect recursion in which two or more functions depend on each other recursively.
Example
int even(int n)
{
if (n == 0)
return 1;
return odd(n - 1);
}
int odd(int n)
{
if (n == 0)
return 0;
return even(n - 1);
}
Calling:
even(4);
produces:
even(4)
↓
odd(3)
↓
even(2)
↓
odd(1)
↓
even(0)
Note : Mutual recursion is a specific type of indirect recursion.
8. Tail Recursion
Tail recursion occurs when the recursive call is the last operation performed by the function.
There is no pending operation after the recursive call returns.
Example
void printNumbers(int n)
{
if (n == 0)
return;
printf("%d ", n);
printNumbers(n - 1);
}
The recursive call:
printNumbers(n - 1);
is the last operation.
Therefore, it is tail recursion.
Another Example
int factorial(int n, int result)
{
if (n == 0)
return result;
return factorial(n - 1, result * n);
}
Call:
factorial(5, 1);
9. Non-Tail Recursion
Non-tail recursion occurs when the recursive call is not the last operation. Some operation remains to be performed after the recursive call returns.
Example
int factorial(int n)
{
if (n == 0)
return 1;
return n * factorial(n - 1);
}
Here:
factorial(n - 1)
↓
returns result
↓
multiply by n
The multiplication happens after the recursive call returns.
Therefore, it is non-tail recursion.
10. Tail vs Non-Tail Recursion
Feature Tail Recursion Non-Tail Recursion
Recursive call Last operation Not necessarily last operation
Pending operation after call No Yes
Example fun(n-1); n * fun(n-1);
Example application Printing/counting Factorial, tree calculations
Stack optimization Can be optimized in some languages/compilers Generally requires pending stack frames
C example return fun(n-1); return n + fun(n-1);
11. Summary of Types
Direct Recursion -Function calls itself directly. A() → A()
Indirect Recursion- Function calls another function that eventually calls it A() → B() → A()
Mutual Recursion-Two or more functions recursively call each other A() ↔ B()
Tail Recursion- Recursive call is the final operation return A(n-1);
Non-Tail Recursion- Some operation remains after recursive call -return n * A(n-1);
Key Concept
Recursive Problem
↓
Divide into Smaller Same-Type Problem
↓
Define Base Case
↓
Recursive Call
↓
Solve Smaller Problem
↓
Combine Results
↓
Final Solution
Important: Every recursive solution must have a termination condition (base case). Without an appropriate base case or progress toward it, recursion can continue indefinitely and may cause stack overflow.