# A.9: Recursion

# Part 1Bu08t
98 99o8****
## Question 1
Given n of 1 or more, return the factorial of n, wO9hich is n * (n-1) * (n-2) ... 1.

Compute the resultP0 recursively (without loops).

def factorial(n):
    if n == 1:
        return 1
    else: 
        return n * factorial(n - 1)
    
    # return n < 3 ? n : n * factorial(n - 1)

## Question 2
We have a number of bunnies and each bunny has two big floppy ears.
We want to compute the total number of ears across all the bunnies recursively (without loops or multiplication).

def bunnyEars(bunnies):
    if bunnies == 0:
        return 0
    else:
        return 2 + bunnyEars(bunnies - 1)
    
    # return bunnies == 0 ? 0 : 2 + bunnyEars(bunnies - 1)
        

## Question 3

The fibonacci sequence is a famous bit of mathematics, and it happens
to have a recursive definition. The first two values in the sequence are 0 and 1 (essentially 2 base cases). Each subsequent value is the sum of the previous two values, so the whole sequence is:
0, 1, 1, 2, 3, 5, 8, 13, 21 and so on.

Define a recursive fibonacci(n) method that returns the nth fibonacci number, with n=0 representing the start of the sequence.

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

## Question 4

We have bunnies standing in a line, numbered 1, 2, ...
The odd bunnies (1, 3, ..) have the normal 2 ears.
The even bunnies (2, 4, ..) we'll say have 3 ears, because they each have a raised foot.

Recursively return the number of "ears" in the bunny line 1, 2, ... n (without loops or multiplication).

def bunnyEars2(bunnies):
    if bunnies == 0:
        return 0
    elif (bunnies % 2 == 1):
        return 2 + bunnyEars2(bunnies - 1)
    else:
        return 3 + bunnyEars2(bunnies - 1)

## Question 5
We have triangle made of blocks. The topmost row has 1 block, the
next row down has 2 blocks, the next row has 3 blocks, and so on.
Compute recursively (no loops or multiplication) the total number of
blocks in such a triangle with the given number of rows.

def triangle(rows):
    return rows == 0 ? 0 : rows + triangle(rows - 1)

## Question 6

Given a non-negative int n, return the sum of its digits recursively (no loops).

Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (//) by 10 removes the rightmost digit (126 / 10 is 12).

sumDigits(126) = 1 + 2 + 6 = 9
sumDigits(126) = 6 + sumDigits(12) = + 6 + 2 + sumDigits(1)
sumDigits(n < 10) = n

def sumDigits(n):
    return n == 0 
        ? 0 
        : (n % 10) + sumDigits(n // 10)

## Question 7
Given a non-negative int n, return the count of the occurrences of 7 as a digit, so for example 717 yields 2. (no loops).

Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (//) by 10 removes the rightmost digit (126 // 10 is 12).

count7(0) =
count7(717) = (1 if lsd is 7 else 0) + count7(71)
base case: count 7(0) = 0

count7(....7) = 1 + count(....)

def count7(n):
    if n == 0:
        return 0
    else:
        lsd = n % 10
        if lsd == 7:
            return 1 + count7(n // 10)
        else:
            return count7(n // 10)

## Question 8
Given a non-negative int n, compute recursively (no loops) the count of the occurrences of 8 as a digit, except that an 8 with another 8 immediately to its left counts double, so 8818 yields 4.

Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (//) by 10 removes the rightmost digit (126 // 10 is 12).
88818 =

def count8(n):
    if n == 0:
        return 0
    elif n % 100 == 88:
        return 2 + count8(n // 10)
    elif n % 10 == 8:
        return 1 + count8(n // 10)

## Question 9

Given base and n that are both 1 or more, compute recursively (no loops) the value of base to the n power, so powerN(3, 2) is 9 (3 squared).

powerN(base, 0) = 0 = x^0 = 1
powerN(base, n) = base * powerN(base, n - 1)

def powerN(base, n):
    if n == 0:
        return 1
    else:
        return base * powerN(base, n-1)

## Question 10
Given a string, compute recursively (no loops) the number of lowercase 'x' chars in the string.

def countX(str):
    if len(str) == 0:
        return 0
    else:
        if str[-1] == 'x':
            return 1 + countX(str[:-1])
        else:
            return countX(str[:-1])

## Question 11
Given a string, compute recursively (no loops) the number of times lowercase "hi" appears in the string.

ahiddd

def countHi(str):
    if len(str) == 1:
        return 0
    elif str[0:2] == 'hi':
        return 1 + countHi(str[2:])
    else:
        return countHi(str[1:])

But it's
# Part 2**0**
But 9
## Question 12
Given a string, compute recursively (no loops) a new string where all the lowercase 'x' chars have been changed to 'y' chars.

def changeXY(str):
    if len(str) == 0:
        return ''
    elif str[0] == 'x':
        return 'y' + changeXY(str[1:])
    else:
        return str[0] + changeXY(str[1:])

## Question 13
Given a string, compute recursively (no loops) a new string where all appearances of "pi" have been replaced by "3.14".

ap ie
a changePi(pie)

base case:
length str < 2 => input
case 1: starts with pi => "3.14" + changePi(str[2:])
case 2: does not start with pi => str[0] + changePi(str[1:])

def changePi(str):
    if len(str) < 2:
        return str
    elif str[:2] == 'pi':
        return '3.14' + changePi(str[2:])
    else:
        return str[0] + changePi(str[1:])

## Question 14
Given a string, compute recursively a new string where all the 'x' chars have been removed.
if length of string == 0
return empty string
if string first character == X
return (string - first character) + noX(string[1:])
if string first character != x
return string first noX(string[1:])

noX("xabc")
= noX("abc")
= "a" + noX("bc")
= "a" + "b" + noX("c")
= "a" + "b" + "c" + noX("")
= "a" + "b" + "c" + ""
= "abc"

def noX(str):
    if len(str) == 0:
        return ''
    elif str[0] == 'x':
        return noX(string[1:])
    else:
        return str[0] + noX(string[1:])

## Question 15
Given an array of ints, compute recursively if the array contains a 6. We'll use the convention of considering only the part of the array that begins at the given index. In this way, a recursive call can pass index+1 to move down the array. The initial call will pass in index as 0.

base case: index == len(nums) return false
if nums[index] == 6 return true
else return array6(nums, index+1)

def array6(nums, index):
    if index == len(nums):
        return False
    elif nums[index] == 6:
        return True
    else:
        return array6(nums, index+1)

array6([1,2,3,4,5,6,7,8,9,10], 0) # returns True

## Question 16
Given an array of ints, compute recursively the number of times that the value 11 appears in the array. We'll use the convention of considering only the part of the array that begins at the given index. In this way, a recursive call can pass index+1 to move down the array. The initial call will pass in index as 0.

def array11(nums, index):
    if len(nums) == index:
        return 0
    elif nums[index] == 11:
        return 1 + array11(nums, index + 1)
    else:
        return array11(nums, index + 1)

## Question 17
Given an array of ints, compute recursively if the array contains somewhere a value followed in the array by that value times 10.

We'll use the convention of considering only the part of the array that begins at the given index. In this way, a recursive call can pass index+1 to move down the array. The initial call will pass in index as 0.

base case: index == len(nums) -> return false
nums(index + 1) == nums(index) * 10 --> return true
nums(index + 1) != nums(index) * 10 --> return array220(nums, index + 1 )

def array220(nums, index):
    if index == len(nums):
        return False
    elif nums[index + 1] == nums[index] * 10:
        return True
    else:
        return array220(nums, index + 1)
    

## Question 18
Given a string, compute recursively a new string where all the adjacent chars are now separated by a "*".

"abc" => "a*b*c"
base case: "s" => "s"
recursive: allStar(str) => str[0] + * + allStar(str[1:])

def allStar(str):
    if len(str) <= 1:
        return str
    else:
        return str[0] + "*" + allStar(str[1:]) 

## Question 19
Given a string, compute recursively a new string where identical chars that are adjacent in the original string are separated from each other by a "*"
bb -> b*b ebb -> eb*b
e.g. b*b, eb*b

base case: b => b
recursive: str[1] == str[0] => str[0]+'*'+ str[1]
else: str[0]+ fx(str[1:])

pairStar("bbb")
= b*b + pairStar("bb")
= b*b + b*b
= b*bb*b

b*b *b

def pairStar(str):
    if len(str) <= 1:
        return str
    elif str[0] == str[1]:
        return str[0] + '*' + pairStar(str[1:])
    else: 
        return str[0]+ pairStar(str[1:])

## Quesiton 20
Given a string, compute recursively a new string where all the lowercase 'x' chars have been moved to the end of the string.
zxc-> zcx
base case: len(str) == 1 return str
case 1: str[0] == 'x' return endX(str[1:])+ 'x'
return str[0] + endX(str[1:])

def endX(str):
    if len(str) == 1:
        return str
    elif str[0] == 'x':
        return endX(str[1:]) + 'x'
    else:
        return str[0] + endX(str[1:])
    

## Question 21
We'll say that a "pair" in a string is two instances of a char separated by a char. So "AxA" the A's make a pair. Pair's can overlap, so "AxAxA" contains 3 pairs -- 2 for A and 1 for x. Recursively compute the number of pairs in the given string.

'BXXB'
'BxBxBxB'3- B 2-x
bxbxb -> 1 + fx("xbxb") = 1 + 1 = 2

bxb --> str[0]==[str2]--> +1 --> fx(str[1:])
xbx --> str[0]==str[2] --> +1

base case: len(str)<3: return 0
recursive case: str[0]

def countPairs(str):
    if len(str) < 3:
        return 0 
    elif str[0] == str[2]:
        return 1 + countPairs(str[1:])
    else: 
        return countPairs(str[1:])

## Part 3

## Quesiton 22
Count recursively the total number of "abc" and "aba" substrings that appear in the given string.

abcabadabc
ababc
base - string less than 3 chars > return 0
case - look at first 3 chars
-> if = abc or aba > return 1 + countAbc(str[1:])
-> if not > return countAbc(str[1:])

def countAbc(str):
    if len(str) < 3:
        return 0
    
    elif str[0:3] == "aba" or str[0:3] == "abc":
        return 1 + countAbc(str[2:])
    else:
        return countAbc(str[1:])

    # x if expr else y
    
    
def countAbc(str):
    if len(str) < 3:
        return 0
    else:
        first_three = str[:3]
        return first_three == "abc" or first_three == "aba"
            ? 1 + countAbc(str[2:])
            : countAbc(str[1:])

## Quesiton 23
Given a string, compute recursively (no loops) the number of "11" substrings in the string. The "11" substrings should not overlap.

111 -> 1
1111 -> 2
1 -> 0

01111 -> 0

base case: str is less than 2 ->
recursive case:
first two = 11 -> 1 + count11(remaining str excluding first two)
first two != 11 -> count11(remaining str excluding first one)

def count11(str):
    if str < 2:
        return 0
    elif str[:2] == '11':
        return 1 + count11(str[2:])
    else:
        return count11(str[1:])

## Quesiton 24
Given a string, return recursively a "cleaned" string where adjacent chars that are the same have been reduced to a single char. So "yyzzza" yields "yza".

aaaaabbcddd -> abcd
abbaaddbbb -> abadb

base case: length of str 0 then return ''
case 1: next character is the same as current return fx(str[1:])
case 2: if its not then return str[0] + fx(str[1:])

def stringClean(str):
    if len(str) == 0:
        return ''
    elif str[0] == str[1]:
        return stringClean(str[1:])
    else:
        return str[0] + stringClean(str[1:])

## Quesiton 25
Given a string, compute recursively the number of times lowercase "hi" appears in the string, however do not count "hi" that have an 'x' immedately before them.
hihihi- 3 times
xhixhi- 0
hixhixhihi- 2 times

base case: number of charac <2 -->return 0
1st case: first charac is x then followed by 2nd and third charac (hi)- xhi --> cut xhi then recurse on remaining string
2nd case: then check 2nd and third --> whether hi--> 1+ recurse on remaining string -hi

def countHi2(str):
    if len(str) < 2:
        return 0 
    elif str[:3] == 'xhi':
        return countHi2(str[3:])
    elif str[:2] == 'hi':
        return 1 + countHi2(str[2:])
    else: 
        return countHi2(str[1:])

## Quesiton 26
Given a string that contains a single pair of parenthesis, compute recursively a new string made of only of the parenthesis and their contents, so "xyz(abc)123" yields "(abc)".

abc(ab)a -> (ab)

(ziudhvjksnd)

base case : str[0] == '(' and str[-1] == ')' return str
case 1: if str[0] != '(' return parenBit(str[1:])
case 2: if str[-1] !=')' return parenBit([:-1])

def parenBit(str):
    if str[0] == '(' and str[-1] == ')':
        return str
    elif str[0] != '(':
        return parenBit(str[1:])
    elif str[-1] !=')':
        return parenBit(str[:-1])

## Quesiton 27
Given a string, return True if it is a nesting of zero or more pairs of parenthesis, like "(())" or "((()))". Suggestion: check the first and last chars, and then recur on what's inside them.

examples:
"" -> True no parenthesis
() -> True
(()) -> True

)( -> False
a( -> False
a) -> False
a() -> False
()() -> False

base case if there are str is ""

case 1: check str[0] = '(' AND str[-1] = ')'
recurse Function( str[1:-1])
case 2: check str[0] != '(' AND str[-1] != ')'
return False

def nestParen(str):
    if str == '':
        return True
    elif str[0] == '(' and str[-1] == ')':
        return nestParen(str[1:-1])
    else:
        return False

## Quesiton 28
Given a string and a non-empty substring sub, compute recursively the number of times that sub appears in the string, without the sub strings overlapping.

base: len(target) < len(sub) -> 0
'SUB...' -> 1 + fn(...)
'...SUB' -> fn(target[1:])

def strCount(strr, sub):
    len_sub = len(sub)
    if len(strr) < len_sub:
        return 0
    elif strr[:len_sub] == sub:
        return 1 + strCount(strr[len_sub:])
    else:
        return strCount(strr[1:])

## Quesiton 29
Given a string and a non-empty substring sub, compute recursively if at least n copies of sub appear in the string somewere, possibly with overlapping. n will be non-negative.

base case n == 0 : True

def strCopies(str, sub, n):
    if n == 0:
        return True
    
    len_sub = len(sub)
    
    if len(str) < len_sub:
        return False
    elif str[:len_sub] == sub:
        return strCount(str[len_sub:], sub, n - 1)
    else:
        return strCount(str[1:], sub, n)

## Quesiton 30
Given a string and a non-empty substring sub, compute recursively the largest substring which starts and ends with sub and return its length.
sub= abc
str = abcdddabcdddddddabc
strDist(abcdddabcdddddddabc, abc) -> len(abcdddabcdddddddabc)
str

dabcqweabcq
abcqweabcqqqqqqq
abcqweabc

abc = 0
"" = 0

base case: starts with abc and ends with abc => return length of str

if current does not start with abc
strDist(str[1:], sub)

else if current does start with abc
strDist(str[:-1], sub)

base case: if length of str < length of sub * 2 return 0
if starting str(length of substring == sub and ending str(length of susbstring == sub) return length of string
...
if starting string == sub recurse (slice from end of str)
if ending string == sub recurse (slice from front of str)
else slice first str

def strDist(str, sub):
    if len(str) < len(sub) * 2:
        return 0
    if str[:len(sub)] == sub and str[-len(sub):] == sub:
        return len(str)
    if str[:len(sub)] != sub:
        return strDist(str[1:])
    if str[-len(sub:)] != sub:
        return strDist(str[:-1])
    
    
def strDist(str, sub):
    if len(str) < len(sub) * 2:
        return 0
    elif str.startswith(sub) and str.endswith(sub):
        return len(str)
    elif not str.startswith(sub):
        return strDist(str[1:], sub)
    else:
        return strDist(str[:-1], sub)

xxxabcyyyabczzz, abc
xxabcyyyabczzz
xabcyyyabczzz
abcyyyabczzz
abcyyyabczz
abcyyyabcz
abcyyyabc

xxxabcyyyabczzz
xxabcyyyabczz
xabcyyyabcz
abcyyyabcBut 0 8 08 I 9But 97Po