You cannot submit for this problem because the homework's deadline is due.

Problem: Scientists have predicted an upcoming earthquake. You live in an square area full of buildings. The scientists say that how the earthquake destroys buildings will follow the following algorithm:

1. Equally divide the square into 4 smaller squares, and the right-upper part will all be destroyed.
2. For each of the remaining 3 smaller squares, also divide them into 4 smaller squares, and the right-upper part will be destroyed
3. Repeat until the square can no longer be divided

You need to write a program to calculate which buildings will be destroyed in order to save your own life.

Requirement: You will use simple recursion to solve this exercise. Recursion is to call the function itself inside the function body, as if the function has already been implemented. See Takeaway for some hints.

Input Format: An integer n (1 <= n <= 10) that stands for a 2^n by 2^n square.

# sample
3

Output Format: A 2^n by 2^n square , where 0 indicates destroyed, 1 indicates safe.

# sample
1 0 0 0 0 0 0 0 
1 1 0 0 0 0 0 0 
1 0 1 0 0 0 0 0 
1 1 1 1 0 0 0 0 
1 0 0 0 1 0 0 0 
1 1 0 0 1 1 0 0 
1 0 1 0 1 0 1 0 
1 1 1 1 1 1 1 1 

Takeaway: We used simple recursion in this exercise. Many people think recursion is the first difficult concept when learning programming. However if you are familiar with the concept of procedural abstraction and specification comment, you can understand recursion easily by imagining the function as a black box with properly defined behavior, and calling the function inside itself is like using that black box in advance.

Tags: #abstraction #specification #recursion