Computer Science 04

Divide and Conquer is the idea of taking a difficult problem and breaking them into simpler pieces. These smaller problems must have two properties:
1) The smaller problems are easier to solve than the original ones.
2) The solutions to these problems can easily can be combined to solve this big problem.

The technique of Recursion allows Divide and Conquer to be applied to problems. In Computer Science, it is:
1) A way of describing / defining problems
2) A way of designing solutions

A Recursive problem has typically two parts:
1) Base Case - It describes a direct answer.
2) Recursive (Inductive) Case - Reduce the problem to a simpler version of the same problem through some simpler operations.

Here are some problems:
1) Calculate bⁿ resursively
-We first start by defining that bn is b*b*b*b*b...*b n times.
-We can then reduce the problem to b*b^n-1

We can now say:
bⁿ = b.b^n-1 if n!=0
bⁿ = 1 if n==0

We can create a recursive method like this:

def recursivePow(number,exponent)
    if exponent==0
        return 1
    else
        return number*recursivePow(number,exponent-1) 

We implemented the above statements into code form. Of course, this method only works with positive values of n.

We can also use it to look at the Towers of Hanoi problem.
There is a Temple in Hanoi, and in it there are 3 tall towers. There are 64 golden discs of descending sizes. The rules are like this:
1) You can only move one disc at a time
2) A larger disc cannot cover up a smaller disc

The recursive solution is this:
1) Suppose that you have three stacks. A starting stack, an ending stack, and a spare stack.
2) The solution is to move a stack of n-1 from the starting stack to the spare stack. Then move the last piece to the ending stack. Then move everything from the spare stack to the ending stack.
3) If the stack is of size 1, just move it to the ending stack.

In code, we have:

def hanoi(n, stackFrom, stackTo, stackSpare):
    if n==1:
        print("Move from",stackFrom,"to",stackTo)
    else:
        hanoi(n-1,stackFrom,stackSpare,stackTo)
        hanoi(1,stackFrom,stackTo,stackSpare)
        hanoi(n-1,stackSpare,stackTo,stackFrom)

hanoi(5, "Starting", "Ending", "Spare")

You can test this using:
Tower of Hanoi

Next, here's another problem. Suppose that we are looking for a palindrome. A palindrome is a sentence that reads the same from both sides: "able was I ere I saw elba". To approach a palindrome, here's how we do it:
1) Check if the first and last characters are the same
2) If they are, remove one character and check again till there are no more characters left.
3) If it satisfies all the way, then it's a palindrome.

The Basecases are:
1) If string is length 1, it is a palindrome
2) If string is length 0, it is a palindrome

The Recursive case is:
1) If first and last character is the same, continue checking

Implemented in code, it would be:

def formatSentence(sentence):
    sentence=sentence.lower()
    ans=''
    for c in sentence:
        if c in {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}:
            ans+=c
    return ans

def recursivePalindrome(sentence):
    if len(sentence)<=1:
        return True
    elif sentence[0]==sentence[len(sentence)-1]:
        return recursivePalindrome(sentence[1:len(sentence)-1])
    else:
        return False
print(recursivePalindrome(formatSentence("Able was I ere I saw Elba")))
print(recursivePalindrome(formatSentence("Are we not drawn onward, we few, drawn onward to new era")))<\code>

As we can see, we can solve problems by breaking it down into simpler problems.

Here's another problem we can look at:
1) Suppose that a pair of rabbits can mate within 1 month
2) A pair of rabbits will be born after gestation period of 1 month
3) The pair is a male and a female
4) How many female rabbits will there be at the end of a year?

We can look at the problem in a timeline:

Month	Female
0	1
1	1
2	2
3	3
4	5
5	8
6	13
7	21

We can now derive the function:
1) f(n)=f(n-1)+f(n-2)

Here are the Base cases:
1) If month is 0, return 1
2) If month is 1, return 1

Here are the Recursive cases:
1) Otherwise, return f(n-1)+f(n-2)

We can now create the code for generating the Fibonacci number:

def fibonacci(n):
    if n<=1:
        return 1
    else:
        return fibonacci(n-1)+fibonacci(n-2)

print(fibonacci(30))

Fibonacci numbers appear in nature all the time. The number of petal on most flowers is almost always a Fibonacci number.

Here is a hair-raising read:
Fibonacci in Nature

You can actually find the golden ratio using:
lim(x->inf) fibonacci(n):fibonacci(n-1)