how can i generate this series of sequence using recursion?

Question

the question goes like this We define sequences Sn ​as follows.

S1 ​is a sequence of length 1 containing a single 1. Sn(n is an integer greater than or equal to 2) is a sequence obtained by concatenating Sn−1​ ,n,Sn−1 ​in this order.

For example, S 2 ​ and S 3 ​ is defined as follows.

S 2 ​ is a concatenation of S1 ​ , 2, and S1 ​ , in this order, so it is 1,2,1. S3 ​ is a concatenation of S2 ​ , 3, and S2 ​ , in this order, so it is 1,2,1,3,1,2,1. Given N, print the entire sequence S N ​ .

i want to create a string function and decrease it value using functions like stoi and genrate the sequence recursively and print the output

Answer 1

The problem description you got already provided the recurrence relation and the base case:

• Base case: ₁ = 1​
• Recurrence: ​ = ₋₁​, , ₋₁

And this is really it. You can formulate this in pseudo code like this, but it really is just a different syntax to express the same thing:

function S(n):
    if n == 1 then:  ' Base case
        output(1)
    else:            ' Recursion
        S(n-1)
        output(n)
        S(n-1)
    end if

I would actually shift the base case to ₀ and define it as "nothing". Then the pseudo code becomes:

function S(n):
    if n > 0 then:
        S(n-1)
        output(n)
        S(n-1)
    end if

In an actual implementation in a programming language, you would replace output with whichever construct is appropriate. Like in Python you could go for a generator:

def generate_S(n):
    if n > 0:
        yield from generate_S(n-1)
        yield n
        yield from generate_S(n-1)

print(*generate_S(3))

This outputs:

1 2 1 3 1 2 1