Python/recursion.py at master · eudaimonious/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
defiterPower(base, exp):
'''
 base: int or float.
 exp: int >= 0

 returns: int or float, base^exp
 '''
result=1
whileexp>0:
result*=base
exp-=1
returnresult

defrecurPower(base, exp):
'''
 base: int or float.
 exp: int >= 0

 returns: int or float, base^exp
 '''
ifexp==0:
return1
returnbase*recurPower(base, exp-1)

defrecurPowerNew(base, exp):
'''
 base: int or float.
 exp: int >= 0

 returns: int or float; base^exp
 '''
ifexp<=0:
return1
elifexp%2==0:
returnrecurPowerNew(base*base,exp/2)
elifexp%2!=0:
returnbase*recurPowerNew(base, exp-1)

defgcdIter(a, b):
'''
 a, b: positive integers

 returns: a positive integer, the greatest common divisor of a & b.
 '''
# Your code
ifa<=b:
smallerInteger=a
else:
smallerInteger=b
foriinrange(smallerInteger,0,-1):
ifi==1:
return1
elifa%i==0andb%i==0:
returni

defgcdRecur(a, b):
'''
 a, b: positive integers

 returns: a positive integer, the greatest common divisor of a & b.
 '''
# Your code here
ifb==0:
returna
else:
returngcdRecur(b,a%b)

deflenIter(aStr):
'''
 aStr: a string

 returns: int, the length of aStr
 '''
count=0
foriinaStr:
count+=1
returncount

deflenRecur(aStr):
'''
 aStr: a string

 returns: int, the length of aStr
 '''
ifaStr=="":
return0
return1+lenRecur(aStr[0:-1])

defisIn(char, aStr):
'''
 char: a single character
 aStr: an alphabetized string

 returns: True if char is in aStr; False otherwise
 '''
low=0
high=len(aStr)-1
middle= (high+low)/2
ifaStr=="" :
returnFalse
eliflen(aStr) ==1:
returnaStr==char
elifaStr[middle] ==char:
returnTrue
elifchar<aStr[middle]:
returnisIn(char, aStr[:middle-1])
else:
returnisIn(char, aStr[middle+1:])

defsemordnilap(str1, str2):
'''
 str1: a string
 str2: a string

 returns: True if str1 and str2 are semordnilap;
 False otherwise.
 '''
iflen(str1) !=len(str2):
returnFalse
ifstr1==""andstr2=="":
returnTrue
else:
returnstr1[0] ==str2[-1] andsemordnilap(str1[1:-1],str2[1:-1])