All the below should be solved recursively, with no loops, unless otherwise noted.

----------------------------------
Integer part of logarithm. 
Given b > 0 and an a positive real number x, 
write a function that returns the integer part of log_b(x)
(_b denotes in base b). Obviously you cannot use log, round, floor,
or any other math function than comparisons and + - * /.

For example, log(8.0,3) should return 1, log(9,3) should return 2,
and log(9.5,3) should return 2 too.

Hint: Exploit the relation between the logs of x and x/b. 

----------

Interleaving. Given two strings compute its interleaving.
The interleaving of "abc" and "xyz" is "axbycz". The interleaving
of "ab" and "xyz" is "axbyz". The interleaving of "abc" and "xy"
is "axbyc".

Write a function interleaving(x,y) that returns the interleaving
of x and y. Work until you have one version that runs in time
O(len(x)+len(y))

------------------------
Permutation. A permutation on a set I is bijective function from I to I.
If P is a permutation, P^i(x) denotes the result of applying P i times, 
starting from x, so P(P(... P(P(x)))...)), where P appears P times.
P^0(x) is of course x itself.

When I is the interval [0..n-1], we can present P as the list
[P(0),P(1),...,P(n-1)]. 

1. Write a function iterate(P,x,i) that given permutation P presented
this way, index i, and value x, returns P^i(x). For example, 
for P=[3,5,2,4,0,1], i = 3, and x = 4, it should return 
P(P(P(4))) = P(P(0)) = P(3) = 4.

It should run in time O(i).

2. A permutation is a cycle if, starting from any x, the only
way to get back to x applying P repeatedly is going through 
all the elements of the permutation. For example, the permutation
above is not a cycle because we go from 4 to 4 in only 3 steps,
and in fact from 2 to 2 in 1 step. Write a function is_cycle(P)
that tells whether or not P is a cycle. 

Hint. It is difficult to program is_cycle recursively directly.
Use an auxiliary recursive function that given x says how many steps you
need in P to get back to x, then use it to give is_cycle.

It should run in time O(len(P)).

------------------------
Replacement in strings.

Let c1, c2, c3 be characters. 
We say that "we replace c1 with c2 conditionally to c3"
in a string s if every occurrence of c1 in s is replaced 
with a c2, provided it is followed by a c3. 

Write a function creplace(s,c1,c2,c3) that returns
the result of replacing c1 with c2 conditionally to c3 in s. 

For example, creplace("rabadan","a","x","d") is "rabxdan".
creplace("rabadaba","a","x","b") is "rxbadaxa",
and creplace("aaa","a","x","a") is "xxa".

The function cannot contain any loops and use no
method of string other than accessing positions and sublists
(lst[....], lst[...:...]), and len(.).

-------------------
Computing integer division and mod from basics.

Suppose that you are given a faulty python interpreter 
where the integer division // , modulus % and divmod
do not work. 

You want to write your own function divmod(a,b)
that returns the tuple (x,y) where x == a//b and y == a % b.

1. write a version using a loop that repeatedly subtracts b from a
2. inspired from that, write a recursion version that does the same.
3. Now let us do it faster. Observe that if a is even, then

a // b == 2* ((a//2) // b)

and give a recursive version using this fact. 

Be careful with the base cases. 

You cannot use floats and operations on floats, and stuff such
as logarithms and exponentials. Integers only.

But divisions and modulus by 2, x//2, and x%2 are allowed;
the python compiler can implement these correctly.

-------------------------------------------
-------------------------------------------
Solutions: 
*** pay attention to the reasining that leads to the solution
*** even more than to the coding in Python

----------------------
Integer part of logarithm. 

If you recall the definition of log, we have y = log_b(x)
if b^y = x.

Therefore, if y = log_b(x), then we have y-1 = log_b(x/b).
Also, log(b,b) = 1, so for x < b, the integer part of log(x,b) is 0.

def log(x,b):
    if x < b:
	   return 0
	else:
	   return 1 + log(x/b,b)

----------------------

Interleaving. To get the recursion, observe that 
the interleaving of x and y is 

- y if x is empty
- x if y is empty
- otherwise, as both x and y are non-empty, they both have a first
  character. Then the interleaving of x and y is the first character
  of x, followed by the first character of y, followed by
  the interleaving of the rest of x and y after removing their
  first characters. 
  
def interleaving(x,y):
    if x == "":
       return y
    elif y == "":
       return x
    else:
       s = x[0]+y[0]
       s += interleaving(x[1:],y[1:])
       return s

Analysis exercise:
Assume s1 += s2 runs in linear time in len(s1)+len(s2) (as it seems to be),
and recall that extracting s[1:] take linear time in len(s).
Given this, argue that for strings x and y of equal length n, 
interleaving(x,y) runs in time O(n^2).

Improvement exercise:
Write a version that runs in linear time, O(len(x)+len(y)),
by adding an index that avoids the copying 

--------
Permutations:

iterate(P,x,i):
   let us try to induct on i, the number of steps
   if i==0, then it's easy: the place we go from x by applying P 0 times is x
   else if i>0, we take a first step and go to P(i). Then we need to take i-1 steps,
   but starting at P(i), and that is the result

def iterate(P,x,i):
    if i == 0:
        return x
    else:
        return iterate(P,P[x],i-1)

It is possible to do it another way: Here we first take 1 step,
then let the recursion do the next i-1 steps.
But we can take the first i-1 steps recursively, see where we land,
then take the extra step. The following is an equally good solution:

def iterate(P,x,i):
    if i == 0:
	    return x
	else:
	    y = iterate(P,x,i-1)
	    return P[y]
	   
For is_cycle, one needs to realize that if 
the walk starting at *some* x takes you through all the elements 
of P, then it doesn't matter which x you start with. That is,
this is true for some x if and only if it is true for all x

So: For simplicity, let us start at 0. We know 
that P is a cycle if, starting and 0 and applying P repeatedly,
we get back to 0 only after having visited len(P) elements.
Assuming P is a permutation, we know for sure that we get back to 0
in at most len(P) steps.

def is_cycle(P):
    return time_to_reach_zero(P,0) == len(P)
	
time_to_reach(P,x) tells how many applications of P we need
to get to 0 starting from x. Well, that is 0 if we are in 0
and, otherwise, 1 more than we need to get from P(x) to 0.

def time_to_reach_zero(P,x):
    if x == 0:
	    return 0
	else:
	    return 1 + time_to_reach_zero(P,P[x])

There is a potential danger in this approach: what if 
we enter an infinite loop: Suppose that P takes us this way:

0 --> 4 --> 7 --> 5 --> 7 --> 5 --> 7 --> 5 --> 7 --> ... 

and so on and so on, so that it never ends. 
Think about it before looking at the next lines. 

THINK THINK THINK BEFORE PROCEEDING DOWNWARD

The above cannot happen if P is really a permutation,
because we must have P(4)=7 and P(5)=7, so P is not bijective.

Change time_to_reach_zero and is cycle so that is_cycle returns
False when P is not a permutation as well (being a permutation
is a necesary condition to be a cycle).

------------
replacement in strings.

Something similar to this should work:

def creplace(s,c1,c2,c3):
    if len(s) < 2:
       return s
    elif s[0] == c1 and s[1] == c3:
        return c2.append(creplace(s[1:],c1,c2,c3)
    else 
        return c1.append(creplace(s[1:],c2,c2,c3)
----------------
Computing integer division and mod from basics.

First version with loop:

def divmod(a,b):
    c = a
    x = 0
    while c >= b:
        x = x+1
        c = c-b
    return (x,a-b*c)

Recursive version, basically mimicking the loop:

def divmod(a,b)
    if (a < b):
        return (0,a)
    else:
        (x,y) = divmod(a-b,b)
        return (x+1,y)

Now with the shortcut of dividing by 2:

def divmod(a,b)
    if (a < b):
        return (0,a)
    elif a % 2 == 1:
        (x,y) = divmod(a-b,b)
    else:
        (x,y) = divmod(a//2,b)
        return (2*x,a - (2*x)*b)