PowerPoint Presentation
*
Recursion is a repetitive process in which an algorithm calls itself.
Each recursive call must either
– solve a part of the problem
or
– reduce the size of the problem
*
Example: A Simple Guessing Game
The computer generates a random number between 1 and 20.
The user is given up to 5 tries to guess the exact number.
After each guess, the program displays a hint, such as
“Your guess is low!” or “… high!”, or
a “sorry” message followed by the random number, or
a “congratulation” message.
Data Structures: A Pseudocode Approach with C, Second Edition
*
algorithm guess( rand_num, tries )
This algorithm receives a random number between 1 and
20 and then prompts the user to enter his/her guess up to
5 times.
PRE: rand_num,
tries ( number of guesses ) POST: success / sorry / hint printed
RETURN: nothing
A Simple Guessing Game – Iterative Algorithm
Data Structures: A Pseudocode Approach with C, Second Edition
Data Structures: A Pseudocode Approach with C, Second Edition
*
A Simple Guessing Game – Iterative Algorithm
algorithm guess ( rand_num, tries )
guessed = FALSE
loop( tries > 0 AND NOT guessed )
read( num )
if( num is equal to rand_num )
guessed = TRUE
print_Congratulations()
else
if( tries is equal to 1 )
print_Sorry( rand_num )
else
if( num < rand_num )
print_Low()
else
print_High()
end if
end if
end if
tries = tries – 1
end loop
return
end guess
Data Structures: A Pseudocode Approach with C, Second Edition
Data Structures: A Pseudocode Approach with C, Second Edition
*
A Simple Guessing Game - Recursive Algorithm
algorithm guess ( rand_num, tries )
if( tries > 0 )
read( num )
if( num is equal to rand_num )
print_Congratulations()
else
if( tries is equal to 1 )
print_Sorry( rand_num )
else
if( num < rand_num )
print_Low()
else
print_High()
end if
guess( rand_num, tries – 1 )
end if
end if
end if
return
end guess
Data Structures: A Pseudocode Approach with C, Second Edition
*
Is the algorithm or data structures naturally suited to recursion?
Is the recursive solution shorter and more understandable?
Does the recursive solution run in acceptable time and space limits?
You should not use recursion if the answer to any of the following questions is no:
Data Structures: A Pseudocode Approach with C, Second Edition
*
Recursion and Structure Charts
main
funA
funB
main
funA
funA
???…
Data Structures: A Pseudocode Approach with C, Second Edition
Data Structures: A Pseudocode Approach with C, Second Edition
*
Recursion and Structure Charts
main
funA
funB
main
funA
Data Structures: A Pseudocode Approach with C, Second Edition