geek_code - 1 year ago 139

Python Question

I tried generating gray codes in *Python*. This code works correctly. The issue is that I am initialising the base case (

`n=1,[0,1]`

`main`

`gray_code`

`def gray_code(g,n):`

k=len(g)

if n<=0:

return

else:

for i in range (k-1,-1,-1):

char='1'+g[i]

g.append(char)

for i in range (k-1,-1,-1):

g[i]='0'+g[i]

gray_code(g,n-1)

def main():

n=int(raw_input())

g=['0','1']

gray_code(g,n-1)

if n>=1:

for i in range (len(g)):

print g[i],

main()

Is the recurrence relation of this algorithm

`T(n)=T(n-1)+n`

Answer Source

```
def gray_code(n):
def gray_code_recurse (g,n):
k=len(g)
if n<=0:
return
else:
for i in range (k-1,-1,-1):
char='1'+g[i]
g.append(char)
for i in range (k-1,-1,-1):
g[i]='0'+g[i]
gray_code_recurse (g,n-1)
g=['0','1']
gray_code_recurse(g,n-1)
return g
def main():
n=int(raw_input())
g = gray_code (n)
if n>=1:
for i in range (len(g)):
print g[i],
main()
```