This question is designed to emphasize and reward the use of relationships in designing recursive func- tions. It's straight-forward if you look at it from a certain point of view, but insidiousty difficult if you insist that staring at a computer is a good way to solve problems. The function that answers this problem can be written in 5-8 Lines of Python code (not counting the doc-string interface). The entire problem is figuring out what the relationships are. And the code is absolutety trivial once you have the relationship right You will know you have the relationships right because they make sense as relationships, not as Python code. A small part of your grade for this question is the actual code, but much more weight is given to whether or not you can explain the relationship that the function makes use of. The problem starts with a room. The room willalways be rectangular(asquare is a special kind of rectangle, so they're allowed), but we will vary the dimensions. The room will be subdivided into an integer number of squares of equal size. Think of the squae as tiles: In general, the room will be a tiles wide, and b tiles long. Furthermore, a and bare integers, and always positive la > 0and b>0. Mario is in the room, trying to get from one corner of the room to the other. He will always start on the tile in the lotver left corner of the room, and he will always have to get to the tile in the top right corner of the room. Mario's movement is constrained by the rule that he cannot movediagonally from one tile to another Mario can onty move to an adjacent tile on the same row, or on the same column, but not diagonally.And of course, Mario cannot step outside the room. Mario wants to follow a path that is as short as possible, counting tiles as distance. A path is a sequence of tiles that Mario can move to. The shortest path has a +b 1 tiles on it, including the starting tile and the ending tile. Furthermore, and this is where the fun begins, there are possibly several paths that are all equally short with the same number of tiles. These paths all share the same property: on a shortest path, Mario can take a step to an adjacent tile, and he can only move up one tile (up, or 'north), or to the right one tile (right, or 'east). If Mario moves (south), or left (west), he cannot be on a shortest path. In the diagram below, we show a 3 x 4 room, and two valid shortest paths that Mario could take. The question is, in a room of a x b tiles, how many different shortest paths could he take (obeying his movement constraints, above)? We want to count paths that are different, and we want to count all the paths. Some paths have a number of tiles in common. For example, two paths can start the same way but then at some tile, they split Likewise, two paths that start separately might join up and end the same way (see the red an blue paths above). These would all be separate paths. The only reason to give these (a) (5 points) Design and implement a recursive function called narioCount) that is given a and b (the size of the room, in tiles), and returns the total number of shortest paths Mario could take to get from the bottom left to the top right of the room b) (3 points) Use your recursive function to calculate the number of paths for each of the following cases: 3x3 4x4 10 x 12 This can be done in your script submit the output of these examples with the answers to the following (c) (5 points) For each base case in your function, briefly explain (a sentence or twol what the base case represents, and why the answer which should be simple) is correct It's okay if your function has several base cases, or only one. (d) (5 points) For each recursive case in your function, briefly explain (2-5 sentences should do) how the problem size is made smaller, and how you build up the solution using the answer from a smaller problem size. It's okay if your function has several recursive cases, or only one. Here are some hints When youre That's fine, as youre trying to look for patterns, and for small values of a and b. But your recursive function should not try to build any paths counting them is much simpler than finding them all Use the recursion template. This question is designed to emphasize and reward the use of relationships in designing recursive func- tions. It's straight-forward if you look at it from a certain point of view, but insidiousty difficult if you insist that staring at a computer is a good way to solve problems. The function that answers this problem can be written in 5-8 Lines of Python code (not counting the doc-string interface). The entire problem is figuring out what the relationships are. And the code is absolutety trivial once you have the relationship right You will know you have the relationships right because they make sense as relationships, not as Python code. A small part of your grade for this question is the actual code, but much more weight is given to whether or not you can explain the relationship that the function makes use of. The problem starts with a room. The room willalways be rectangular(asquare is a special kind of rectangle, so they're allowed), but we will vary the dimensions. The room will be subdivided into an integer number of squares of equal size. Think of the squae as tiles: In general, the room will be a tiles wide, and b tiles long. Furthermore, a and bare integers, and always positive la > 0and b>0. Mario is in the room, trying to get from one corner of the room to the other. He will always start on the tile in the lotver left corner of the room, and he will always have to get to the tile in the top right corner of the room. Mario's movement is constrained by the rule that he cannot movediagonally from one tile to another Mario can onty move to an adjacent tile on the same row, or on the same column, but not diagonally.And of course, Mario cannot step outside the room. Mario wants to follow a path that is as short as possible, counting tiles as distance. A path is a sequence of tiles that Mario can move to. The shortest path has a +b 1 tiles on it, including the starting tile and the ending tile. Furthermore, and this is where the fun begins, there are possibly several paths that are all equally short with the same number of tiles. These paths all share the same property: on a shortest path, Mario can take a step to an adjacent tile, and he can only move up one tile (up, or 'north), or to the right one tile (right, or 'east). If Mario moves (south), or left (west), he cannot be on a shortest path. In the diagram below, we show a 3 x 4 room, and two valid shortest paths that Mario could take. The question is, in a room of a x b tiles, how many different shortest paths could he take (obeying his movement constraints, above)? We want to count paths that are different, and we want to count all the paths. Some paths have a number of tiles in common. For example, two paths can start the same way but then at some tile, they split Likewise, two paths that start separately might join up and end the same way (see the red an blue paths above). These would all be separate paths. The only reason to give these (a) (5 points) Design and implement a recursive function called narioCount) that is given a and b (the size of the room, in tiles), and returns the total number of shortest paths Mario could take to get from the bottom left to the top right of the room b) (3 points) Use your recursive function to calculate the number of paths for each of the following cases: 3x3 4x4 10 x 12 This can be done in your script submit the output of these examples with the answers to the following (c) (5 points) For each base case in your function, briefly explain (a sentence or twol what the base case represents, and why the answer which should be simple) is correct It's okay if your function has several base cases, or only one. (d) (5 points) For each recursive case in your function, briefly explain (2-5 sentences should do) how the problem size is made smaller, and how you build up the solution using the answer from a smaller problem size. It's okay if your function has several recursive cases, or only one. Here are some hints When youre That's fine, as youre trying to look for patterns, and for small values of a and b. But your recursive function should not try to build any paths counting them is much simpler than finding them all Use the recursion template