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);
}