Practice Quiz 04/04

Topic: Recursion in two ways

For all the questions, write down the precondition, postcondition, purpose and produce of the procedure. Identify the base case and the recursive step of your procedure. While you are solving the problem, you should not refer to the templates for help.
For the purpose of understanding, for what type of problems do we need to use recursion? When do you know you need/can use recursion to solve a problem? Besides recursion, is there a way to tackle the problems?

string-rotate

Write (string-rotate str num), which takes a string and an integer and rotates str forward by num places. For example, (string-rotate “I love CS” 3) should produce “ CSI love”.
Can you come up with a recursive solution and a non-recursive solution? (hint: string-append and substring)









If you use remainder or quotient procedures for this question, try to define them by yourself here:









What if the input is a list and a integer, and you need to rotate the list? (hint: cons)

list-reverse

Write (list-reverse lst), which takes a list and reverses it. For example, (list-reverse (list 1 3)) should produce '(3 1) Write this procedure using direct/basic recursion. (hint: append)










Write this procedure using tail recursion. (hint: cons)

Swap Elements in Pairs

Write a procedure (swap-pairs lst) which takes a list as a input, and swap every two adjacent nodes. For example, (swap-pairs (list 1 2 3 4)) will produce '(2 1 4 3); (swap-pairs (list 1 2 3 4 5)) will produce '(2 1 4 3 5). (hint: think about the input for the recursive step.)

Pascal Triangle

Pascal triangle is one of the most interesting number patterns. Newton’s bionomial coefficient could be derived from this triangle. A pascal triangle is showing here: observe the relationship between the horizontal layers and today we will just play around with this relationship.
Write a procedure (next-layer lst): Given a list of integers representing one layer in the “pascal” triangle, produce a list of integers representing the top layer. For example: (next-layer (list 1 3 3 1)) will produce '(1 4 6 4 1); (next-layer (list 2 2 7)) will produce '(2 4 9 7);









Extra fun: Assuming the input is valid, can you write (prev-list lst)? For example (prev-list (list 1 3 5 3)) will produce '(1 2 3).

power

Write a procedure (my-power x n), which takes a real number x and a integer n and produce the xⁿ. Remember that n can be a negative number. (hint: what is your base case here?)









Acknowledgement: Some of the questions are obtained from previous mentor sessions and leetcode.