LECTURE 8
Recursive functions and algorithms
Simple examples
Programs: c3_1.c ......, c3_6.c
Tomasz Zieliński
LECTURE 8
Recursive functions and algorithms
Simple examples
Programs: c3_1.c ......, c3_6.c
Tomasz Zieliński
RECURSIVE METHODS (1) -
program c3_1
======================================================================================================
Recursive function
is a function that inside is calling itself.
======================================================================================================
/* Example 3.1 – print in
reverse order
characters taken from the keyboard */
#include <stdio.h>
void RevOrder( void );
void main()
{
printf("\nWrite in line. Finish with <Enter>. \n\n");
RevOrder();
}
==========================
void RevOrder( void )
{
char c;
// read a character from the keyboard and store its
if ( (c=getchar() ) != '\n' )
// ASCII code into ”c”; if it is not end-of-line, then:
{
//
RevOrder();
// <== !!! call again the function ReverseOrder()
printf( "%c", c);
// display character ”c” on the screen
}
}
RECURSIVE METHODS (2) -
program c3_1
Print in reverse order characters taken from the keyboard
void main()
{ .....
RevOrder();
.....
}
void RevOrder( void )
{
char c;
if ( (c=getchar()) != '\n' )
{
RevOrder();
printf( "%c", c);
}
}
c
← „a”;
RevOrder();
print c;
c
← „b”;
RevOrder();
print c;
c
← „\n”;
ASSUMPTION: „ab [ENTER]” from keyboard
c is a local variable of each function call,
that has different value each time
RECURSIVE METHODS (3) -
program c3_1
Print in reverse order characters taken from the keyboard
Main program
a
printf
b
printf
c
printf
d
printf
\n
ASSUMPTION: „abcd [ENTER]” from keyboard
RECURSIVE METHODS (4) -
program c3_2
Change INTEGER to ASCII
/* Example 3.2 - print on the screen value of integer variable
*/
/* i.e. change binary INTEGER value
*/
/* to sequence of ASCII codes of its digits
*/
#include <stdio.h>
#include <math.h>
void int2asc( int n );
/* main program ------------------------------------------------------------------------- */
void main()
{
int x;
printf(" \n What integer value ? ");
scanf("%d", &x);
printf(" \n given = %d \n", x);
printf(" recursion = ");
int2asc( x );
printf("\n");
}
/* Recursive function --------------------------------------------------------------------------------------- */
void int2asc( int n )
{
int i;
//
if
negative
number,
if ( n < 0 ) { putchar('-'); n = -n; }
// then display „-” and negate the number n
if ( (i=n/10) != 0 )
int2asc( i );
// if „i”, i.e. integer part of „n/10”,
//
is
not
equal
zero,
then
call
again
//
but
with
argument
„i”
putchar(‘0’+n%10); //
this (reminder od division n by 10)
// putchar( '0' + (unsigned char) (n - 10 * i) );
// or this (the low significant digit)
}
RECURSIVE METHODS (5) -
program c3_2
Change INTEGER to ASCII
Main program
12345
putchar
n=1234
n=123
n=12
n=1
putchar
putchar
putchar
putchar
n
i = n/10
i = n/10
i = n/10
putchar
= putchar(‘0’ + (unsigned char) (n – 10*i)
„1”
„2”
„3”
„4”
„5”
i = n/10
ASSUMPTION: „12345 [ENTER]” from keyboard
print the reminder from division n by 10,
i.e. the low significant digit of n
= putchar(‘0’ + (unsigned char) (n % 10)
RECURSIVE METHODS (6) -
program c3_3
n! or
n-factorial
/* Example 3.3 – RECURSIVE METHODS – calculate n!
*/
/* n! = 1*2*3*...*(n-1)*n, np. 5! = 1*2*3*4*5
*/
#include <stdio.h>
long nfactorial( long n );
/* main program ------------------------------------------------------------------ */
void main()
{
long n, x, multiplic;
printf("\n I am calculating n! Please, give n ? [max 12] ");
scanf("%ld", &n);
/* Iterative method */
multiplic = 1;
for( x = n; x > 0; x--)
{ multiplic = multiplic * x; }
printf( "\n Iterative method --> n! = %ld \n", multiplic );
/* Recursive method */
multiplic =
nfactorial( n );
printf( "\n Recursive method --> n! = %ld \n", multiplic);
}
/* Recursive function ----------------------------------------------------------- */
long nfactorial( long n )
{
long x, y;
if( n == 0L ) return(1);
// L means long
x = n-1;
y =
nfactorial(x)
;
/*
recursive
call
*/
return(n*y);
}
long nfactorial( long n )
{
if( n == 0L ) return(1);
return(n*
nfactorial(n-1)
);
/* recursive call */
}
RECURSIVE METHODS (7) -
program c3_3
n! or
n-factorial
Main program
4
4*
(3*2*1*1)
n
3
3*(2*1*1)
2
2*(1*1)
1
1*(1)
0
1
24
6
2
1
1
n-1
n-1
n-1
n-1
ASSUMPTION: „4 [ENTER]” from keyboard
long
nfactorial
( long n )
{
long x, y;
if( n == 0L ) return(1);
x = n-1;
y =
nfactorial
(x);
return(n*y);
}
long
nfactorial
( long n )
{
if( n == 0L ) return(1);
return( n*
nfactorial
(n-1) );
}
RECURSIVE METHODS (8) -
program c3_5
BINARY SEARCH
- looking for a given value in a table
by its division into two parts
0.0
0.1
0.2
0.3
0.4
0.5
1.5
2.0
•
•
•
table of
divisors
•
•
•
0
1
2
3
4
5
15
N-1
index
i
x = 1.5
TASK: find index ”i” of the table
for which: tab[ i ] == x
SOLUTION 1 (sequential):
i = 0;
while( ( x != tab[i] ) & (i < N-1) )
i++;
SOLUTION 2 (recursive):
int bsearch( int tab[ ], int x, int down, int up )
{ int centre;
centre = (down + up)/2;
if ( x == tab[ centre ] ) return( centre );
if ( x < tab[ centre ] )
return(
bsearch( tab, x, down, centre - 1
)
);
else
return(
bsearch( tab, x, centre + 1, up )
);
}
RECURSIVE METHODS (9) -
program c3_5
DIGRESSION: direct Analog-to-Digital (AD) converters
U
range
K
R
R
R
R
R
R
U
x
K
K
K
K
1
1
1
0
0
U
range
U
x
U
range
Nr=0
A/C=000
U
x
0
∆
U
Nr=1
Nr=2
Nr=3
Nr=5
Nr=6
Nr=7
A/C=010
A/C=001
A/C=011
A/C=101
A/C=110
A/C=111
U
0
U
1
U
2
U
3
Nr=4
A/C=100
RECURSIVE METHODS (10) -
program c3_5
DIGRESSION: Analog-to-Digital approximation converters:
successive approximation (left) and bit-weighting (right)
U
x
K
0/1
Counter/Generator
D/A
1
1
0
0
Start
Stop
U
counter
U
counter
counter state
U
x
0000
0001
0010
0011
0100
• • •
U
REF
U
x
C
0/1
Logic
D/A
1
1
0
0
Stop
U
D/A
Start
U
C/A
D/A bit number
U
x
0
1
2
3
U
range
3/4U
z
1/2U
z
1/4U
z
U
range
U
REF
RECURSIVE METHODS (11) -
program c3_5
binary search method
/* Example 3.5 – RECURSIVE METHODS
–
„binary
search" */
/*
INPUT:
tab = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
*/
/*
x = integer number given from the keyboard
*/
/*
OUTPUT:
index of the “x” value in the table tab[]
*/
#include <stdio.h>
int binsearch( int tab[ ], int x, int down, int up );
void main() /* main program ------------------------------------------------------------------------ */
{
int tab[ 11 ] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10 };
int x, index, down, up;
printf("\n Give a number -x- to be searched ? ");
scanf("%d", &x);
down = 0; up = 10;
index =
binsearch( tab, x, down, up )
;
printf( "\n Index = %i \n", index);
}
/*
recursive
function -------------------------------------------------------------------- */
int binsearch( int tab[ ], int x, int down, int up )
{
int centre;
if ( down > up ) return(-1);
// -1 means lack of x in the file
centre = (down + up)/2;
if ( x == tab[ centre ] ) return( centre );
if ( x < tab[ centre ] )
return(
binsearch( tab, x, down, centre - 1
) );
else
return(
binsearch( tab, x, centre + 1, up )
);
}
/*
nonrecursive
function --------------------------------------------------------------- */
int
binsearchX
( int tab[], int x, int down, int up)
{
int centre;
while( down <= up )
{
centre = (down + up)/2;
if( x==tab[centre]) return(centre);
if ( x < tab[ centre ] )
up = centre - 1;
else
down = centre+1;
}
return(-1);
}