Subject : COMP6047
ALGORITHM AND PROGRAMMING
Year : 2019
Function and Recursion
Learning Outcomes
At the end of this session, student will be able to:
• Using function and recursion in C using parameters (LO3)
COMP6047 - Algorithm and Programming 2
Sub Topics
Function and Recursion:
– Modular Programming
– Function Definition
– Function Prototype
– Identifier Scoping
– Passing Parameter
– Program Examples Using Function
– Recursion Definition
– Recursive Function
– Iterative vs. Recursive
– Program Examples Using Recursive
– Exercise
COMP6047 - Algorithm and Programming 3
Modular Programming
• Program is divided into modules
• Module in C programming language is implemented using
function
• Function is formed through grouping some statements to do a
particular job
• Module is needed when a certain block of statement frequently
used by other distinct code in a program
• Also called Sub-Program
COMP6047 - Algorithm and Programming 4
Modular Programming
• Advantages of using Modules:
1. Top-down design with sub goal, huge program divided
into smaller modules
2. Can be done by more than one developer/ programmer
3. Easier to debug, as logical flow is easy to follow and
easier to pin point errors
4. Modification can be done without affecting overall
codes
5. Easier to document
COMP6047 - Algorithm and Programming 5
Modular Programming
• C programming language implements modular programming
using function
• Example of dividing program into subprograms
Main Program
SubProgram SubProgram SubProgram
SubProgram SubProgram
COMP6047 - Algorithm and Programming 6
Modular Programming
• Best practice in module programming:
– High Fan-In, frequently used
– Low Fan-Out, more specific functionality/ small
number of job
– Self-Contained, self resource sufficient
COMP6047 - Algorithm and Programming 7
Library vs User-Defined Function
• Function in C divided in two types :
– Library function
– User-defined function
• Library function, is a standard function provided by C compiler.
Those function described in the header files (.h)
Example: strcpy() in string.h
sqrt() in math.h
printf() in stdio.h
• User-defined function is self defined functions
COMP6047 - Algorithm and Programming 8
Library vs User-Defined Function
Example:
Program using Standard Library Function : printf and sqrt
#include<stdio.h>
#include<math.h>
int main() {
int i;
for(i=0; i<6; i++)
printf(“%d %f”,i,sqrt(i));
return 0;
}
COMP6047 - Algorithm and Programming 9
Function Definition
Function Construction
return-value-type function-name( parameter-list )
{
statements;
}
return-value-type: data type of the value returned
• If not filled, then default data type will be used (default integer)
• If return-value-type is void then the function will not return
value
Parameter-list: list of value sent from the function initiator (user)
COMP6047 - Algorithm and Programming 10
Function Definition
• Example :
Formal parameter
Function
int maximum (int x, int y){
int max = x;
if ( y > max) max = y; Initiator/ Caller
return max
}
void main () {
int a,b;
printf("Input 2 even values : ");
scanf("%d %d", &a, &b);
printf("Largest value is : %d\n",maximum(a,b));
}
Actual parameter
COMP6047 - Algorithm and Programming 11
Function Prototype
Function in C usually written above the initiator/caller or
main program. Otherwise should use Function
Prototype
Function Prototype Objective:
• To ensure a function is known by the initiator/caller
• Compiler will validate the parameters
Syntax :
return-value-type function-name ( parameter-
list );
COMP6047 - Algorithm and Programming 12
Example 1:
Function Prototype
#include <stdio.h>
int maximum (int x, int y){
int max = x; No need for
if ( y > max) max = y; function
return max prototype as
}
the function
void main () { placed above
int a,b; initiator (main
printf("Input 2 even values : "); program)
scanf("%d %d", &a, &b);
printf("Largest value : %d\n",maximum(a,b));
}
COMP6047 - Algorithm and Programming 13
Function Prototype
Example 2:
#include<stdio.h> Function
Prototype
int maximum(int, int);
Function
void main () { prototype
int a,b;
needed as the
printf("Input 2 even values : ");
scanf("%d %d", &a, &b); function placed
printf("Largest value : %d\n",maximum(a,b)); below the
} initiator/caller
(Main program)
int maximum (int x, int y){
int max = x;
if ( y > max) max = y;
return max
}
COMP6047 - Algorithm and Programming 14
Function Prototype
Function Prototype can be written as follows:
int maximum (int a, int b);
Important:
parameters data type, number of parameters and its order
COMP6047 - Algorithm and Programming 15
Identifier Scoping
Identifier Scoping:
scope of identifier is reachable
Identifier Scoping:
• Local
• Global
COMP6047 - Algorithm and Programming 16
Identifier Scoping
Local Identifier
• Identifier declared in a function including the parameters
• Scope limited in the function
Global Identifier
• Identifier declared outside any function and placed on top of all
functions in a C program
• Reachable from any point in the program
• Global Identifier, can be re-declared in subprogram
• It is advisable not to use global variable for the following reasons:
– Error rate might increase as line of code increase.
– Difficult in debugging
– Exclusivity of data is low. All functions in the program can change
its value
COMP6047 - Algorithm and Programming 17
Identifier Scoping
int x;
function1(){
scope of variable x
-
}
int y;
function2(){
int z; scope of variable y
-
}
main(){
int
z; z and y scope only in main program
int y; z in main different from function2()
-
}
COMP6047 - Algorithm and Programming 18
Identifier Scoping
COMP6047 - Algorithm and Programming 19
Passing Parameter
If a module is not self sufficed then needed data/value
and its result passes in and out using parameter(s)
List of parameters is the interface of a module with other
modules
Passing Parameter
– By-Value, sent to other module is the value
– By Location/by reference, sent to other module
is the address
COMP6047 - Algorithm and Programming 20
Passing Parameter
Example: (Passing Parameter by Value)
#include <stdio.h>
void Line (char x ) { /* x is Formal Parameter*/
{
int i; / *i, x are Local Variable */
for (i = 1; i<=10; i++) printf(“%c”,x);
}
/*Main Program*/
void main()
{
char A = ’-’;
Line(A); /* A is Actual Parameter */
}
COMP6047 - Algorithm and Programming 21
Passing Parameter
Example: (Passing Parameter by Location)
#include <stdio.h>
void Calculate (int X, int Y, int *P, int *Q)
{
*P = X + Y;
*Q = X * Y;
}
void main()
{
int X, Y, P, Q; /*local variable*/
printf(“ X=”); scanf(“%d”,&X);
printf(“ Y=”); scanf(“%d”,&Y);
Calculate(X,Y,&P,&Q);
printf(”X + Y = %d\n”, P);
printf(”X * Y = %d\n”, Q);
}
COMP6047 - Algorithm and Programming 22
Passing Parameter: 1D Array
If an array used as function's parameter, then parameter passing
should be done by location
Example:
#include <stdio.h>
void print_array(int index, int *A) {
printf(“A[%d]=%d\n”,index,
A[index]);
}
void main() {
int A[ ]={1,6,2,8,12};
print_array(2, A);
}
In the example above, A in the main program is a constant pointer,
on the other hand, A inside print_array is variable pointer.
COMP6047 - Algorithm and Programming 23
Passing Parameter: 2D Array
The declaration can be:
void matriks(int a[10][10], int b, int
k)
or
void matriks(int a[][10], int b, int k)
But CANNOT be:
void matriks(int a[10][], int b, int k)
or
void matriks(int a[][], int b, int k)
COMP6047 - Algorithm and Programming 24
Passing Parameter: 2D Array
#include <stdio.h>
void print(int A[3][4])
{
int row,col;
for(row=0; row<3; row++){
for(col=0; col<4; col++)
printf("X[%d][%d]=%d",row,col,A[row][col]);
printf("\n");
}
}
int main()
{
int x[3][4]={{1,2,3,4},
{8,7,6,5},
{9,10,11,12}};
print(x);
return(0);
} COMP6047 - Algorithm and Programming 25
Passing Parameter
int main()
{ string as formal
char ss[20]="KASUR"; parameter :
rotate(ss); char[ ] or char *
printf("%s\n",ss);
getch();
return(0);
}
void rotate( char ss[ ] ) void rotate( char *ss )
{ {
int c,i,j; int c,i,j;
for(i=0, j=strlen(ss)-1; i<j; i++, j--) for(i=0, j=strlen(ss)-1; i<j; i++, j--)
{ {
c=ss[i]; c=ss[i];
ss[i]=ss[j]; ss[i]=ss[j];
ss[j]=c; ss[j]=c;
} }
} }
COMP6047 - Algorithm and Programming 26
Recursive Definition
• Recursive is a function call inside a certain function calling itself
• Recursive Function, suitable for recursive problem
• Example :
Factorial (n) or n! defined as follows :
n! = 1, for n = 0;
n! = n * (n-1)!, for n > 0
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1* 0!
0! = 1
Trace back : 4! = 1*2*3*4 = 24
COMP6047 - Algorithm and Programming 27
Recursive Definition
Example: (5 factorial)
5!
(5 * 4!)
(5 * (4 *3!))
(5 * (4 * (3 * 2!)))
(5 * (4 * (3 * (2 * 1!))))
(5 * (4 * (3 * (2 * (1 * 0!)))))
(5 * (4 * (3 * (2 * (1 * 1)))))
(5 * (4 * (3 * (2 * 1))))
(5 * (4 * (3 * 2)))
(5 * (4 * 6 ))
(5 * 24)
120
COMP6047 - Algorithm and Programming 28
Recursive Function
Recursive Function has two components:
– Base case:
return value(constant) without calling next recursive call.
– Reduction step:
sequence of input value converging to the base case.
Example: (Factorial function)
– Base case : n = 0
– Reduction step: f(n) = n * f(n-1)
COMP6047 - Algorithm and Programming 29
Iterative vs Recursive
Example: (Iterative vs Recursive)
• Factorial - Recursive
long factor (int n)
{
if(n==0) return (1);
else return(n * factor(n-1));
}
• Factorial - Iterative
long factor(int n) {
long i, fac = 1;
for(i=1; i<=n; i++) fac *= i;
return (fac);
}
COMP6047 - Algorithm and Programming 30
Recursive
Recursive Drawback
Although recursive code more concise it needs:
– More memory consumption – as stack memory is needed
– Takes longer time, should traverse through all recursive call
using stack
Recursive Best Practice
Generally, use recursive solution if:
– Difficult to solve iteratively.
– Efficiency using recursive has been reached
– Efficiency is less important in comparison with readability
– Memory efficiency and execution time are not the main concern
Consider carefully speed and efficiency using iterative approach,
rather than nice logical design using recursive
COMP6047 - Algorithm and Programming 31
Program Example Using Recursive
Fibonacci Number
sequence: 0, 1, 1, 2, 3, 5, 8, 13 ...
Relation between the number define recursively as follows:
Fib(N) = N if N = 0 or 1
Fib(N) = Fib(N-2) + Fib(N-1) if N >= 2
int Fib(int n) {
int f;
if(n==0) f = 0;
else if(n==1) f = 1;
else f = Fib(n-2) + Fib(n-1);
return f;
}
COMP6047 - Algorithm and Programming 32
Program Example Using Recursive
Fibonacci Number
Fibonacci illustration N=4
FIB (4)
FIB (3) FIB (2)
FIB (2) FIB (1) FIB (1) FIB (0)
FIB (1) FIB (0)
COMP6047 - Algorithm and Programming 33
Classic & Modern
(Function Parameter Declaration)
Classic Function Parameter Declaration
int function1(a)
int a; #include <stdio.h>
{
a++; int main()
return a; {
} int x;
x=function1(3);
int function2(b) printf("x=%d\n",x);
int b; x=function2(13);
{ printf("x=%d\n",x);
b = b * b; return(0);
return b; }
}
COMP6047 - Algorithm and Programming 34
Classic & Modern
(Function Parameter Declaration)
Modern Function Parameter Declaration
int function1(int a) #include <stdio.h>
{
a++; int main()
return a; {
} int x;
x=function1(3);
int function2(int b) printf("x=%d\n",x);
{ x=function2(13);
b = b * b; printf("x=%d\n",x);
return b; return(0);
} }
COMP6047 - Algorithm and Programming 35
Exercise
1. Create a program with the following functions:
– Function to input 10 numbers into an array
– Function to find max value in an array
– Function to find min value in an array
– Function to print out:
• those 10 numbers
• max and min value
COMP6047 - Algorithm and Programming 36
Exercise
Left Middle Right
2. Hanoi Tower
1
2
3
4
• Move n-plates from left pillar to the right pillar using the middle pillar.
At all time the smaller plate should be placed on top of larger plate.
• Recursive solution :
1. Move (n-1) top plates to the middle pillar
2. Move last plate to the last pillar (target).
3. Repeat 2 and 3 until finish
COMP6047 - Algorithm and Programming 37
Exercise
3. Repair the following code:
void swap(char A, char B )
{
char C ;
C = A; A = B, B = C;
}
void main()
{
char X, Y ;
X = ‘S’; Y = ‘D’;
swap (X, Y);
printf(“X = %c Y= %c”, X, Y);
}
COMP6047 - Algorithm and Programming 38
Exercise
#include <stdio.h>
4. void divide(float x, int y, float *z) {
if(y==0) return; void function
*z=x/y;
}
float div(float x, int y){
if(y!=0) return(x/y);
return value function
}
void main()
{
compare both return inside divide
float f,a=12.75; int b=5; and return inside div ?
divide(a,b,&f);
printf("%f divided by %d = %f\n",a,b,f);
b=3;
f=div(a,b);
printf("%f divided by %d = %f\n",a,b,f);
}
COMP6047 - Algorithm and Programming 39
Exercise
#include <stdio.h>
5. void divide(float x, int y, float *z) {
if(y==0) return;
*z=x/y;
}
float div(float x, int y){ a. Can divide function not use
if(y!=0) return(x/y); return, if so, how?
}
b. Can div function not using
void main()
{ keyword return ?
float f,a=12.75; int b=5;
divide(a,b,&f);
printf("%f divided by %d = %f\n",a,b,f);
b=3;
f=div(a,b);
printf("%f divided by %d = %f\n",a,b,f);
}
COMP6047 - Algorithm and Programming 40
Exercise
6. #include <stdio.h>
int main(){
int x,y;
for(x=1; x<=3; x++) {
int x=5;
printf("x=%d ",x++);
for(y=0; y<x; y++){
int x=20;
printf("x=%d ",x++);
}
printf("\n");
} Note the x variable scope.
return 0; Describe the output of the code!
}
COMP6047 - Algorithm and Programming 41
Summary
• Function is formed through grouping some statements to do a
particular job
• C programming language implements modular programming
using function
• Function in C divided in two types :
– Library function
– User-defined function
• Recursive is a function call inside a certain function calling itself
COMP6047 - Algorithm and Programming 42
References
• Paul Deitel & Harvey Deitel. (2016). C how to program : with an
introduction to C++. 08. Pearson Education. Hoboken. ISBN:
9780133976892. Chapter 5
• Functions in C: [Link]
COMP6047 - Algorithm and Programming 43
END
COMP6047 - Algorithm and Programming 44
