Recursion on strings - back to beginning of string?

Question

Given that in recursion you're using a divide-and-conquer method to break down problems into smaller pieces, how would you be able to read data from beginning of the problem, at the end of problem?

Example: I have a an encrypt() function that replaces characters in a string with characters 3 indices to the right:

A in string "ABCDEF" becomes D for example

So far I did it recursively up to the point where it stops when 3 indices to the right are undefined, but this leaves the last bit of the string the same as the original.

Example: "ABCDEF" becomes "DEFDEF"

Is there a way that I can pass the beginning of the string to the innermost functions during the recursive calls in an efficient way?

This is my code currently:

def shift_cipher_noloop(plain):

    encrypted = ""

    if(plain == ""):
        encrypted = ""

    else:
        if(len(plain) > 3):            
            temp_sub = plain[3]          
            encrypted = encrypted + temp_sub
            encrypted = encrypted + shift_cipher_noloop(plain[1:])

        else:
            temp_sub = plain[0] 
            encrypted = encrypted + temp_sub
            encrypted = encrypted + shift_cipher_noloop(plain[1:])

    return encrypted

x = "ABCDEFGHIJK"

y = shift_cipher_noloop(x)

print(y)

pretty simple and clear I guess, the point is to avoid the use of the for loop — William Yang
– William Yang, Commented Nov 23, 2012 at 11:54
AHH i see what I could do, but then it involves using a third parameter, grab the first 3 chars then pass it on function by function, but that's not exactly what I want. — William Yang
– William Yang, Commented Nov 23, 2012 at 11:56
lol i know what I could do but it's going to be ugly - all sorts of ways — William Yang
– William Yang, Commented Nov 23, 2012 at 12:00

Rohit Jain · Accepted Answer · 2012-11-23 12:34:49Z

2

May be this does not exactly solves your problem, but you may have to mould it a little bit to make it fit. As I see somewhere you want Recursion. I have just shown how you can move to the beginning, when you reach the end of the string.

Take the modulus of i + 3 with the length of string to move to the beginning automatically: -

>>> my_str = "ABCDEF"
>>> length = len(my_str)

>>> for i in range(length):
        print my_str[(i + 3) % length],


D E F A B C

So, when i = 3, i + 3 = 6, and 6 % 6 = 0 -> back to the first character

If you want to use Recursion, here's your modified program: -

def shift_cipher_noloop(plain, i):

    if(plain == ""):
        return ""

    else:
        # Iterate with your string, moving first character to last on each iteration
        if len(plain) > 3 and i > 0: 
            return shift_cipher_noloop(plain[1:] + plain[0], i - 1)

        else:
            # else Will be executed when either len <= 3, or `i <= 0`.
            # when (i <= 0) is true, you have created a new string, 
            # with each character shifted by `original i` indices. 
            # So, just return it.

            return plain


x = "ABCDEF"
index_to_shift = 3
y = shift_cipher_noloop(x, len(x) - index_to_shift)

print(y)

OUTPUT : -

DEFABC

I added one more parameter to your method, which I use to take the appropriate index. And also, I'm passing the complete string to the method each time moving the first character to the end.

Also, if the len(plain) <= 3, you can simply return the string.

edited Nov 23, 2012 at 12:34

answered Nov 23, 2012 at 11:40

Rohit Jain

214k45 gold badges419 silver badges534 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

William Yang Over a year ago

def shift_cipher_noloop(plain): encrypted = "" if(plain == ""): encrypted = "" else: if(len(plain) > 3): temp_sub = plain[3] encrypted = encrypted + temp_sub encrypted = encrypted + shift_cipher_noloop(plain[1:]) else: temp_sub = plain[0] encrypted = encrypted + temp_sub encrypted = encrypted + shift_cipher_noloop(plain[1:]) return encrypted x = "ABCDEFGHIJK" y = shift_cipher_noloop(x) print(y)

Rohit Jain Over a year ago

@WilliamYang.. I added a modified versin of your code. Check it out whether you can understand it or not?

William Yang Over a year ago

Can it be done with ONLY 1 param? that's the most elegant way I think, because the user may not supply i as an argument

Rohit Jain Over a year ago

@WilliamYang.. Umm. let me see.

Rohit Jain Over a year ago

@WilliamYang.. You have to pass one argument extra anyhow. How do you decide that the value is 3? You can also need to take every 4th character instead of 3rd?

|

Martin Hallén · Accepted Answer · 2012-11-23 11:48:06Z

1

If you don't have to use recursion, then I would use simple string methods.

def encrypt(text):
  return text[3:] + text[:3]

I also like Rohit Jain's answer a lot

answered Nov 23, 2012 at 11:48

Martin Hallén

1,5621 gold badge12 silver badges27 bronze badges

2 Comments

phant0m Over a year ago

The question is not about how to end up with the correct result, rather it is about how to solve this recursively.

Alfe Over a year ago

You also could have said, "simply do print "DEFABC"" to get the correct output ;-)

Alfe · Accepted Answer · 2012-11-23 13:12:57Z

1

In general there is the option of passing an additional parameter into the recursive function which is passed unchanged down into the deeper nests of the recursion. You also can use inner functions which always can access the parameters of the outer ones:

def shift_cipher_noloop(original):
  def encrypt_recursion(plain):
    encrypted = ""
    if plain == "":
      encrypted = ""
    elif len(plain) > 3:
      encrypted += plain[3]
      encrypted += encrypt_recursion(plain[1:])
    else:
      encrypted += original[3-len(plain)]
      encrypted += encrypt_recursion(plain[1:])
    return encrypted
  return encrypt_recursion(original)

shift_cipher_noloop('abcdefghijklop')
'defghijklopabc'

answered Nov 23, 2012 at 13:12

Alfe

60.2k21 gold badges117 silver badges172 bronze badges

Collectives™ on Stack Overflow

Recursion on strings - back to beginning of string?

3 Answers 3

8 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

8 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related