Question

#2 The Jacobsthal sequence is defined by J(1)=J(2)=1 and J(n)=J(n-1)+2J(n-2).  Use recursion to write a function that takes in a positive integer n and returns the nth Jacobsthal number.

>>> J(8)
85
>>> J(9)
171


#3 Use recursion to write a function that takes in a positive integer n and returns all n digit numbers containing only odd digits.

>>> f(1)
[1, 3, 5, 7, 9]
>>> f(2)
[11, 13, 15, 17, 19, 31, 33, 35, 37, 39, 51, 53, 55, 57, 59, 71, 73, 75, 77, 79, 91, 93, 95, 97, 99]
]
>>> f(3)
[111, 113, 115, 117, 119, 131, 133, 135, 137, 139, 151, 153, 155, 157, 159, 171, 173, 175, 177, 179, 191, 193, 195, 197, 199, 311, 313, 315, 317, 319, 331, 333, 335, 337, 339, 351, 353, 355, 357, 359, 371, 373, 375, 377, 379, 391, 393, 395, 397, 399, 511, 513, 515, 517, 519, 531, 533, 535, 537, 539, 551, 553, 555, 557, 559, 571, 573, 575, 577, 579, 591, 593, 595, 597, 599, 711, 713, 715, 717, 719, 731, 733, 735, 737, 739, 751, 753, 755, 757, 759, 771, 773, 775, 777, 779, 791, 793, 795, 797, 799, 911, 913, 915, 917, 919, 931, 933, 935, 937, 939, 951, 953, 955, 957, 959, 971, 973, 975, 977, 979, 991, 993, 995, 997, 999]


#5 Use recursion to write a function that takes in a positive integer n and returns all strings of zeros and ones of length n that do NOT have two consecutive ones.

>>>f(2)
['00','01','10']
>>>f(3)
['000','001','010','100','101']


#6 The Recaman sequence R(n) is defined to be 0 if n is 0.  For n>0 we define R(n) to be a(n-1)-n if a(n-1)-n is BOTH positive and not equal to R(0),R(1), ..., R(n-1).  Otherwise we define R(n) to be a(n-1)+n.  Use recursion to write a program to compute R(n).

>>> R(5)
7
>>> R(3)
6


#7 The Somos sequence is defined by S(n) = 1 if n is 1,2,3 or 4.  Otherwise it equals (S(n-1)S(n-3)+S(n-2)S(n-2))/S(n-4). Use recursion to write a program to compute S(n).

>>> [S(i) for i in range(1,10)]
[1, 1, 1, 1, 2, 3, 7, 23, 59]

Answer 1

The following are the codes for above questions.

#code for problem 2 and 3
def J(n):
  if n==1 or n==2:
    return 1
  return J(n-1)+2*J(n-2) #recursion
#J(9)

def odd_digits(n): #print odd digits
  l=[]
  for i in range(pow(10,n)):
    if i%2!=0: #if number is odd
      l.append(i)
  return l

print(J(9))
print(odd_digits(2))

#code for problem 5
l=[]  #declare an empty list to store the binary strings
def binaryStrings(n,s,k): 
  global l
  if k==n: 
    l.append(''.join(s[:n]))  #terminate the string and append to list
    return 
  if s[k-1]=='1': #if the character before the last character in s is 1, then we put 0 at last (because we dont need 1 to be consecutive)
    s[k] = '0'
    binaryStrings(n,s,k+1) 
        
  if (s[k-1]=='0'): #if the character before the last character in s is 0, then we put both 0 and 1 at last
    s[k] = '0'
    binaryStrings(n,s,k+1) 
    s[k]='1'
    binaryStrings(n,s,k+1) 
                

def display(n): #function to generate all the binary strings with 0 and 1, with no 1 should be consecutive
  if n<=0:
   return

  s=[0]*n #store all strings

  s[0]='0' #store binary strings start with 0
  binaryStrings(n,s,1) 

  s[0]='1' #store binary strings start with 1
  binaryStrings(n,s,1)
  print(l) #print the binary strings

display(3) #call the display function to store strings in global list l

#code for problem 6 and 7
def R(n):
  global l
  if n==0:
    return 0
  elif R(n-1)-n>0:
    return R(n-1)-n #recursion
  else:
    return R(n-1)+n #recursion
#R(5)

def S(n):
  if n in [1,2,3,4]:
    return 1
  else:
    return (S(n-1)*S(n-3)+S(n-2)*S(n-2))//S(n-4)  #recursion

print(R(5))  #print Recaman sequence R(n) output
print([S(i) for i in range(1,10)]) #print the output for S(n)

I am also attaching the output and code screenshots for your reference. It will help you to cross check if any indendation errors.

Output and code Screenshots:

#Please dont forget to upvote if you find the solution helpful. Feel free to ask doubts if any, in the comments section. Thank you.