Some recursion problems to practice Programming and Algorithms 2 Degree in Bioinformatics Fall 2018 ********************* READ THIS FIRST These problems should be solved recursively. For all those that are not marked "multiple recursion", there may be iterative solutions using loops, but we want the recursive version. In many it may be impossible to solve the problem recursively right away from the definition. You may need to invent an auxiliary function (which is the recursive one) then solve the stated problem by (non-recursively) calling this auxiliary function. (If you feel you need practice with loops, sure, try giving iterative solutions as well.) For those marked "multiple recursion", linear recursion or a purely iterative solution is hard, so .... well, use multiple recursion. Usually we ask for functions that return results, not that print a result to the console. Do not for example print "is a prime!" or "is not a prime", but return True or False. Also, for problems on strings, try to solve them without converting them to strings first and working for strings. That is, in a way, cheating, because you are using implicitly the algorithm to turn the integer to a string and then accessing its digits. Most of these problems are in www.jutge.org --> Learning to Program course --> course, so you can even test your solutions. ****************** Double factorial. The double factorial of n is defined as n!! = n × (n - 2) × (n - 4) × ... For example, 9!! = 9 × 7 × 5 × 3 × 1 = 945 and 8!! = 8 × 6 × 4 × 2 = 384. By definition, 0!! = 1!! = 1. Write a recursive function to compute the double factorial of a non-negative integer. *********************** Increasing integer An integer is increasing if every digit is smaller than or equal to the one after it, if it exists. For example, 123378, 7, and 0 are increasing, but 125433 is not. Write a function is_increasing(n) that says whether integer n is increasing. ************************ Multiples of three Write a function that returns True if integer n is a multiple of 3, and False otherwise. Use the well-known fact that n is a multiple of 3 if and only if the sum of its digits is also a multiple of 3. For example, 654 is a multiple of 3 because 6+4+5=15 is also a multiple of 3. Hint: use an auxiliary function to compute the sum of the digits of n. And perhaps another ************************ Reducing an integer You compute the reduction of an integer by adding its digits, then adding the digits of the result, then adding the digits of the result, until you get to a single digit number. For example, if we reduce 15669 we first get 1+5+6+6+9 = 27, then 2+7 = 9, so the reduction is 9. The reduction of 2 is 2, and the reduction of 0 is 0. Write a function that returns the reduction of a natural number. ************************* Expressing integers in bases Write a function that, given a natural number n and a base b between 2 and 9, returns a string representing n in base b. For example inbase(14,2) returns "1110", and inbase(681,7) returns "1662" (because 681=1*7^3+6*7^2+6*7+2*7^0). Here you are allowed to convert n to a string ONLY if n < b. You can concatenate strings once they are created. *************************** Three consecutive equal digits Write a function that, given n, tells True or False depending on whether n has three consecutive equal digits. For example, it should return True on 2111, 3334, 21113, 211132, and 211115666, but False on 8, 88, 1234, and 8848. *********************** Local maxima (this problem is not in www.jutge.org, as far as I know) Given a list of numbers L, return the list of numbers that are local maxima, that is, that are larger than both its left and right neighbors. The first element and the last element of the list are also considered local maxima. For example, the list of local maxima of [-1,3,9,2,1,5,2,6,3] is [-1,9,5,6,3]. Hint: build an auxiliary function that has an index as parameter, besides L. ************************* Decoding a list (this problem is not in www.jutge.org, as far as I know) We have invented a strange way of scrambling a list. Given a list like the following: [(0,"a"),(0,"b"),(2,"c"),(1,"d"),(1,"e"),(3,"f")] we decode it as follows: - You start with the empty list. - You process the list left to right. - A pair (i,x) inserts element x at the ith position in the list constructed before. For example, in the list above we first create ["a"], then insert "b" in the 0-th position, so we get ["b","a"], then we insert "c" in position 2, so we get ["b","a","c"]. Then we insert "d", "e", "f" in their positions, and get at the end ["b","e","d","f","a","c"] Write a function decode(L) that decodes the list L in this way. If there is an impossible operation (like, the first element is (2,"a")), the function returns False. The solution that you will give is probably quadratic in time. Observation: Ricard has not tried hard to find a subquadratic solution, like O(n) or O(n log n). There may be one, or it may be impossible. Tell him if you find one. ************************* This exercise is not about recursion. In fact, it is not an exercise but a preparation for the next one. It provides you a way to get input word by word, much as you have cin << in C++, because in python is line by line. Have a look at the following class: class WordReader(): # creates a word reader that will later provide the words in s def __init__(self,s): self.thelist = s.split() self.idx = 0 # repeated calls to next will give back the words in s, one after the other def next(self): if self.words_left(): x = self.thelist[self.idx] self.idx = self.idx + 1 return x # if no words left, None will be returned # True if there is still some word not returned by next() def words_left(self): return self.idx < len(self.thelist) Then you can read a whole line and apply process(w) to each of its words w in this way: wp = WordReader(input()) # reads one line into wp while wp.words_left(): w = wp.next() process(w) Try it with some simple process(w) function that simply prints back w. ************************* Evaluating expressions in prefix notation (this problem is in www.jutge.org, but due to input/output incompabitility it is not clear you can submit your solution in python) This requires multiple recursion. A prefixed expression is a way of writing arithmetic expressions with +, -, *, / where every operator precedes its two operands. It has the advantage that no parenthesis are requited. For example, the prefixed expression * + 3 4 - 5 2 represents what we normally write as (3+4)*(5-2) and evaluates to 7*3=21. And the prefixed expression - 1.5 - 1.8 + 2 * 2 1 is what we would normally write as 1.5 - (1.8 - (2 + 2*1))). Make sure you understand this. And it evaluates to 1.5 - (1.8 - 4) = 3.7. Finally, the expression we write normally as 1 - 2 + 4 is written in pefixed form as + - 1 2 4 More in general, a prefixed expression is - a number - or a sequence of the form OP E1 E2 where OP is an operand, and E1 and E2 are also prefixed expressions. Write a function that takes a string and returns the result of evaluating it as a prefixed expression. The function will read a string from the keyboard into a WordReader and evaluate that line, so its header will be: def eval(wp): x = wp.next() ... if's, recursive calls to eval, and other stuff... Test your function with a loop like this: while True: wp = WordReader(input()) print(eval(wp)) ******************** Towers of Hanoi This requires multiple recursion. The towers of Hanoi is a well known puzzle. There are three poles A, B, C and a set of disks with a hole in between, of different sizes. Initially, they are all placed as a stack in A, in increasing order (largest at the bottom, smallest at the top). Poles B and C are initially empty. The goal is to move them to pole C, leaving them in the same order, in a finite number of moves, and respecting the following rules: - At each step you can only move one disk. - A movement consists of taking the disk at the top the stack in any of the three poles, and taking it to the top of the stack in another pole. - You can never place a disk on another one that is smaller. If you think about it, these rules imply that any stack at any pole at any moment will also be increasingly ordeed, largest at the bottom, smallest at the top. Watch these videos. - For n=4, https://www.youtube.com/watch?v=aGlt2G-DC8c - For n=6, https://www.youtube.com/watch?v=DF7mq2knmjk (advice: speed it up) - For n = 8: https://www.youtube.com/watch?v=pe3G-xiXIVQ Write a function that, given n, prints on screen the movements required for moving the initial stack of n disks from A to C. More in general, write a function Hanoi(n,i,j,k) that moves the top n disks in pole i to pole j using k as auxiliary The initial call could be for example Hanoi(4,"A","C","B") to move the top 4 disks now in pole A to pole C For example, for n=1 it should print A => C For n = 2 it should print A => B A => C B => C For n = 3, it should print A => C A => B C => B A => C B => A B => C A => C In general, solving the problem for n will require 2^n-1 moves. The general way (which you need to program) is to consider the task of moving m disks from pole i to pole j (assuming pole i contains m or more disks) is: 1- move the top m-1 disks from i to k, recursively (where k != i, j). 2- move one disk from i to j 3- move the top m-1 disks from k to j. In the video above for n=8, the middle point of the main call occurs at 2:37, when the darkest disk is moved from A to C; all the moves before were to move the 7 disks on top of it to B. The middle point of the first recursive call occurs at 1:28, when the 2nd largest disk is moved from A to B. The middle point of the second recursive call is 3:40, and so on. (Note: I don't think the guy is doing recursion in his head; there are other algorithms to express the same solution, based on binary codes and so on, which are easier on the human mind to execute, but harder to prove correct).