Lecture 23 - CS159 Recursive Tracing
Prof. Alvin Chao
Due this week:
OpenDSA Tracing
Handout
Given some recursive code:
- What is the return result?�- What is the maximum depth of the call stack?�- How many times was the recursive method called?
Recursive Tracing
Characteristics of tracing mechanism
• Visible representation of each call�• Tracking of arguments for each call�• Tracking of return value for each call
Use a circle for each dynamic call with arguments
Small computation inside if desired
Arrow for new call with solid line
Arrow for return with value and dotted line
Recursion Tracing
1. powerN
public static void main(String[] args) {
System.out.println("powerN(2, 3): " + powerN(2, 3));
}
public static int powerN(int base, int n) {
if (n == 0) {
return 1;
}
return base * powerN(base, n - 1);
}
- What is the return result? 8
- What is the maximum depth of the call stack of recursive calls? 4
- How many times was the recursive method called? 4
Main
2,3�2*?
2, 2�2*?
2,1�2*?
2,0
1
2
4
powerN
8
Example 1
public static void main(String[] args) {
System.out.println("bunnyEars(3): " + bunnyEars(3));
}
public static int bunnyEars(int bunnies) {
if (bunnies == 0) return 0;
return 2 + bunnyEars(bunnies - 1);
}
main
bunnyEars
0
2 + ?
2 + ?
2 + ?
1
2
3
6
4
0
2
6
4
4
Example 2
public static void main(String[] args) {
System.out.println("fibonacci(4): " + fibonacci(4));
}
public static int fibonacci(int n) {
if (n == 0)return 0;
if (n == 1)return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
main
fibonacci
1
?
?
?
2
3
4
3
2
1
1
3
4
9
0
0
1
1
1
?
2
1
0
0
1
+ ?
+ ?
+ ?
+ ?
Example 3
public static void main(String[] args) {
System.out.println(array6(nums, 0));
}
public static boolean array6(int[] nums, int index) {
if (nums.length == 0) return false;
if (index == nums.length - 1) return nums[index] == 6;� return (nums[index] == 6) || array6(nums, index + 1);
}
main
array6
nums, 3
false || ?
false || ?
false || ?
nums, 2
nums, 1
nums, 0
true
true
true
true
true
4
4
nums
3 | 1 | 7 |6
Visualizer/Tracing Recursion
add_all
Python problem for tracing in vercel:
def add_all(nums):
"""Add all the integers in the given list, recursively.
The list may contain ints and/or other lists containing ints/lists.
Args:
nums (list): A list of ints and/or other lists containing ints/lists.
Returns:
(int): The sum of all the integers in the given list.
"""
Java:
/**
* Add all the integers in the given array recursively.
*/
public static int add_all(int[] nums){
}
triangle
sum_digits
count8