Please solve this question. This question is related to recursion and induction. Thank you so much!

Defining a function recursively can be quite tricky when you are not used to it. To get started you might as well make use of the fact that you know what such a definition needs to look like. Assume we intend to define a function f: ListsN - + S that behaves in a particular way. Then we know we need to have two cases: Base case f. f[]=? Step case f. f(s: 1) =??? fl. It should be easy to read off from your description of f how to define it in the base case. For the step case you may require a bit of creativity. How does knowing fl help us to calculate f(s : 1)? Note that you are allowed to use operations from the target set of f, here S. If you can answer that question you should be able to give a correct definition. Then check your definition using an example. Another useful operation is determining the length of a list. You are asked to define this operator yourself in the following exercise, but assume for the remainder of this section that there is a function len: Listss + N which, given a list, returns the number of elements in the list. CExercise 115. This exercise concerns the length function described in the preceding paragraph. (a) Give a definition of this len function. (b) Use your definition to calculate len(3, 2, 1) step by step. (c) Give the code for the corresponding function for objects of type List. (d) Show that for all lists 1 and l' over a set S we have len(I # 1') = lenl + len l'. Justify each step. Defining a function recursively can be quite tricky when you are not used to it. To get started you might as well make use of the fact that you know what such a definition needs to look like. Assume we intend to define a function f: ListsN - + S that behaves in a particular way. Then we know we need to have two cases: Base case f. f[]=? Step case f. f(s: 1) =??? fl. It should be easy to read off from your description of f how to define it in the base case. For the step case you may require a bit of creativity. How does knowing fl help us to calculate f(s : 1)? Note that you are allowed to use operations from the target set of f, here S. If you can answer that question you should be able to give a correct definition. Then check your definition using an example. Another useful operation is determining the length of a list. You are asked to define this operator yourself in the following exercise, but assume for the remainder of this section that there is a function len: Listss + N which, given a list, returns the number of elements in the list. CExercise 115. This exercise concerns the length function described in the preceding paragraph. (a) Give a definition of this len function. (b) Use your definition to calculate len(3, 2, 1) step by step. (c) Give the code for the corresponding function for objects of type List. (d) Show that for all lists 1 and l' over a set S we have len(I # 1') = lenl + len l'. Justify each step