Description

GitHub Classroom

Lab 7 – Recursion
MS-Paint
Do you know this symbol in paint/photoshop?

When we bring the bucket to a pixel and click, the color of the region of that pixel is replaced with a new selected color.

Instead of a 2D image, we will start in 1D
index 0 1 2 3 4 5 6 7 8 9 10 11
Our 1D image
1
User new color!
Goal
1. The user select a “new color” (red)
2. The user clicks on one pixel  pixel index x=4
3. We look at the value of the selected pixel  old color 4
4. All the adjacent green pixels have to be replace with the new color
0 0 0 1 1 1 1 1 2 2 1 4
After our filling!
You will have to implement this strategy in a recursive manner in a single function:
colorFill1D(lst, x, new_color, old_color)
This function will take the following arguments

lstThe list of pixel you want to process
x The position of the current pixel
?
?
new_colorThe new color you will use to replace the old one old_colorThe old color you would like to replace
How do we solve this problem recursively?
1
4
new_colorindex 0 1 2 3 4 5 6 7 8 9 10 11 list
old_color

Tips
• While implementing the function, think about the base cases needed to stop the recursion! (when facing base case  return)
• Ensure you understand how the recursion works, especially when the function calls itself for neighboring elements.
• One possible base case might be when the index is outside of the list

Task2: implement 2D bucket tool
Can we apply the same process in 2D?
0 0 0 4 4 1 4 4 2 3
1 1 0 4 4 1 4 4 3 3
0 0 0 4 1 1 4 4 3 3
0 0 0 4 1 1 1 1 3 2
0 2 0 4 4 1 4 4 2 2
2 2 2 4 1 1 4 4 2 2
0 0 2 4 4 1 4 4 2 2
Task2: implement 2D bucket tool
You will apply the very same strategy but considering 4 neighbors
x,y+1
x-1,y x,y x+1,y
x,y-1
Implement the 2D function in:
colorFill2D(matrix, x, y, new_color, old_color)