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
ASSUMPTION: „ab [ENTER]” from keyboard
void main()
{ .....
RevOrder();
c ← „a”;
.....
RevOrder();
c ← „b”;
}
RevOrder();
c ← „\n”;
void RevOrder( void )
print c;
{
char c;
print c;
if ( (c=getchar()) != '\n' )
{
RevOrder();
printf( "%c", c);
}
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
ASSUMPTION: „abcd [ENTER]” from keyboard
a
printf
b
printf
c
printf
d
printf
\n
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
ASSUMPTION: „12345 [ENTER]” from keyboard n
12345
putchar
„5”
putchar
= putchar(‘0’ + (unsigned char) ( n % 10) i = n/10
= putchar(‘0’ + (unsigned char) ( n – 10* i) n=1234
putchar
„4”
print the reminder from division n by 10, i = n/10
i.e. the low significant digit of n
n=123
putchar
„3”
i = n/10
n=12
putchar
„2”
i = n/10
n=1
putchar
„1”
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 );
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
ASSUMPTION: „4 [ENTER]” from keyboard
n
long nfactorial( long n )
4
4*(3*2*1*1)
24
{
n-1
long x, y;
3
3*(2*1*1)
6
if( n == 0L ) return(1);
x = n-1;
n-1
y = nfactorial(x);
2
2*(1*1)
2
return(n*y);
}
n-1
long nfactorial( long n )
1
1*(1)
1
{
if( n == 0L ) return(1);
n-1
return( n*nfactorial(n-1) );
0
1
1
}
RECURSIVE METHODS (8) - program c3_5
BINARY SEARCH - looking for a given value in a table by its division into two parts
index
table of
TASK: find index ”i” of the table
i
divisors
for which: tab[ i ] == x
N-1
2.0
•
•
SOLUTION 1 (sequential):
•
i = 0;
while( ( x != tab[i] ) & (i < N-1) ) 15
1.5
x = 1.5
i++;
•
•
SOLUTION 2 (recursive):
•
int bsearch( int tab[ ], int x, int down, int up )
{ int centre;
5
0.5
4
0.4
centre = (down + up)/2;
3
if ( x == tab[ centre ] ) return( centre ); 0.3
if ( x < tab[ centre ] )
2
0.2
return( bsearch( tab, x, down, centre - 1 )
);
1
0.1
else
0
0.0
return( bsearch( tab, x, centre + 1, up ) );
}
RECURSIVE METHODS (9) - program c3_5
DIGRESSION: direct Analog-to-Digital (AD) converters U range
U x
U range
U range
Nr=7
A/C=111
K
0
R
∆ U
Nr=6
A/C=110
K
0
Nr=5
A/C=101
U
U
x
x
R
Nr=4
A/C=100
K
1
R
U 3
Nr=3
A/C=011
K
1
U
R
2
Nr=2
A/C=010
K
1
U 1
Nr=1
A/C=001
R
U 0
Nr=0
A/C=000
0
RECURSIVE METHODS (10) - program c3_5
DIGRESSION: Analog-to-Digital approximation converters: successive approximation (left) and bit-weighting (right)
U
0/1
x
C
U
0/1
x
K
U D/A
U counter
D/A
U REF
D/A
U REF
0
0
1
1
Stop
0
0
1
1
Stop
Logic
Counter/Generator
Start
U
Start
C/A
U
U
U
range
range
counter
3/4 Uz
Ux
Ux
1/2 Uz
1/4 Uz
counter state
0000
0001
0010
0011
0100
• • •
01
2
3
D/A bit number
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);
}