PowerPoint Presentation
Data Structures: A Pseudocode Approach with C, Second Edition
*
Data Structures: A Pseudocode Approach with C, Second Edition
Data Structures: A Pseudocode Approach with C, Second Edition
*
Data Structures: A Pseudocode Approach with C, Second Edition
Data Structures: A Pseudocode Approach with C, Second Edition
*
Data Structures: A Pseudocode Approach with C, Second Edition
Data Structures: A Pseudocode Approach with C, Second Edition
*
(Continued)
Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
Fib(0)
0
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
Fib(0)
0
Fib(1)
1
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
Fib(0)
0
Fib(1)
1
Fib(2)
1
+
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
Fib(3)
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
Fib(1)
1
Fib(3)
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
+
Fib(3)
Fib(2)
Fib(1)
1
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
+
Fib(3)
Fib(2)
Fib(0)
0
Fib(1)
1
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
+
Fib(3)
2
Fib(0)
0
Fib(1)
1
Fib(2)
1
+
Fib(1)
1
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
Fib(4)
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
Fib(4)
+
Fib(0)
0
Fib(1)
1
Fib(2)
1
+
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
Fib(3)
2
Fib(0)
0
Fib(1)
1
Fib(2)
1
+
Fib(1)
1
Fib(0)
0
Fib(1)
1
Fib(2)
1
+
Fib(4)
3
+
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
Fib(5)
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
Fib(5)
Fib(3)
2
Fib(1)
1
Fib(2)
1
Fib(0)
1
Fib(1)
1
+
+
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
Fib(4)
3
Fib(2)
1
Fib(0)
1
Fib(1)
1
+
Fib(3)
2
Fib(1)
1
Fib(2)
1
Fib(0)
1
Fib(1)
1
+
+
+
Fib(5)
5
Fib(3)
2
Fib(1)
1
Fib(2)
1
Fib(0)
1
Fib(1)
1
+
+
+
0 1 1 2 3 5 8 13 21 34 55 89
0 1 2 3 4 5 6 7 8 9 10 11
*
algorithm fib ( n )
if( n EQUAL 0 or n EQUAL 1)
return n
return fib( n – 1 ) + fib( n – 2 )
end fib
n >= 0
*
main
fib
*
main
fib
*
fib
fib
fib
main
*
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:
*
Fib(2)
1
Fib(4)
3
Fib(0)
1
+
Fib(0)
1
+
+
+
Fib(5)
5
Fib(3)
2
Fib(1)
1
Fib(2)
1
Fib(0)
1
Fib(1)
1
+
+
+
Fib(1)
1
Fib(1)
1
Fib(1)
1
Fib(2)
1
Fib(3)
2
*
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
*
Data Structures: A Pseudocode Approach with C, Second Edition
Data Structures: A Pseudocode Approach with C, Second Edition
*
Data Structures: A Pseudocode Approach with C, Second Edition