Friday, August 20, 2021

Playing With Code–Recursion

Recursion was never a big part of my toolbox but I am starting to appreciate it more recently. Regular readers know that I have been writing about and writing code for some older, simpler cryptography systems. For one of them I needed a list of letter in the alphabet without duplicating previous letters.

I needed to take a letter from the alphabet (I had a string of it) and see if it was in a list of used letters. If the letter was used already I wanted to check the next letter. It’s pretty straight forward if you can assume that not two letters in a row are used in the previous string. There is probably a decent iterative way to do this but I was coming up blank. Until it occurred to me that a recursive solution might be just what I needed.

I came up with the following code. It checks of the letter at location k in the alphabet list is in the string to check. If it has not been used it returns the index of the letter to use. If it has been use the same function is called again looking at the next letter index. This continues until we find an unused letter.

private int getNext(int k, string check)
{
     if (check.IndexOf(alpha.Substring(k, 1)) < 0)
         return k;
     else
         return getNext(k + 1, check);
}

I really like this solution because it emulates the way I think about the task. It’s also easy to understand. Recursion is not always hard and confusing. Sometimes it really makes things easier.

Program note: The nice people at Feedspot have compiled a Top 20 Computer Science Blogs list. Yes, I made the list but there are a lot of very good blogs on that list. They cover computer science more broadly and many will be worth a follow.

In cryptography news, the NSA Codebreaker Challenge 2021 is now open.

While you are here, I have been regularly updating my Tiny Book of Simple Cryptography. The current list includes:

Caesar Cipher
Vigenère cipher
One Time Pad
Polybius Square
PigPen Cipher
Columnar Transposition Cipher
Keyword Columnar Transposition Cipher
Random Block Transposition Cipher
Steganography
Bacon’s Cipher

1 comment:

Mike Zamansky said...

What people sometimes forget is that recursion also gives another way to look at a problem. In this example, you said thinking of the problem recursively led you to a solution where in this case thinking iteratively didn't. If for some reason you can't use the recursive solution in the final code, having it can lead to further explorations which could then lead to another solution.

More tools in the toolbox is a good thing.