## Recursive definition of a String

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Larson, Moderators General, Prelates

### Recursive definition of a String

Hey all,

Today I had a test for my Algorithms and Data Structures course and one questions has been bugging the hell out of me. I tried talking to the lecturer after and I still wasn't able to understand what he was asking or what he was expecting in the answer. I have since googled the problem to no avail. When I attempted to question my friends on Facebook, I got answers such as "I have legs." which reminded me most of my FB friends are idiots.

Which leads me to here. I hoping one of you guys will be able to shed some light on the problem, which is as follows.

Given that a string is a concatenation of characters, the following is an (incomplete) recursive definition of a string:
"Concatenation of a string and a character is a string."
a) What is missing?
b) Write the complete definition.

I "think" I have determined that the base case is missing. But why that is or how I write it in the definition, I'm lost.
DantesInferno

Posts: 5
Joined: Tue Jan 18, 2011 11:13 pm UTC

### Re: Recursive definition of a String

I'd say you need to be able to have an empty string so you can concatenate the first character.

diabolo

Posts: 71
Joined: Fri Aug 08, 2008 4:17 pm UTC
Location: france

### Re: Recursive definition of a String

You are correct that the missing detail is the base case. As written, the definition is completely self-referential and impossible to use to determine whether anything is a string or not. diabolo is correct that the required base case is the empty string.
douglasm

Posts: 492
Joined: Mon Apr 21, 2008 4:53 am UTC

### Re: Recursive definition of a String

Are they looking for the definition add to the existing sentence or to add another sentence as well?

If the latter, you'll want to expand the following to cover all combinations:

"Concatenation of a string and a string is a string."
"Concatenation of a string and a character is a string."
"Concatenation of a string and an empty string is a string."

freakish777

Posts: 328
Joined: Wed Jul 13, 2011 2:14 pm UTC

### Re: Recursive definition of a String

Spoiler:
DantesInferno wrote:Hey all,

Today I had a test for my Algorithms and Data Structures course and one questions has been bugging the hell out of me. I tried talking to the lecturer after and I still wasn't able to understand what he was asking or what he was expecting in the answer. I have since googled the problem to no avail. When I attempted to question my friends on Facebook, I got answers such as "I have legs." which reminded me most of my FB friends are idiots.

Which leads me to here. I hoping one of you guys will be able to shed some light on the problem, which is as follows.

Given that a string is a concatenation of characters, the following is an (incomplete) recursive definition of a string:
"Concatenation of a string and a character is a string."
a) What is missing?
b) Write the complete definition.

I "think" I have determined that the base case is missing. But why that is or how I write it in the definition, I'm lost.

The empty string is a string. Concatenation of a string and a character is a string.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk

Posts: 10038
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Recursive definition of a String

Make that "a sequence of zero characters is a string". And then the recursive part.
Hey, like coding? Perhaps you should check out the red spider project.
Feel free to call me Julian. J+ is just an abbreviation.

Jplus

Posts: 1091
Joined: Wed Apr 21, 2010 12:29 pm UTC

### Re: Recursive definition of a String

Jplus wrote:Make that "a sequence of zero characters is a string". And then the recursive part.

Wouldn't the definition of "sequence" already cover the recursive part (eg. "the empty sequence or a concatenation of a sequence and an element")?
If you're going to use this term to define a string couldn't you just say "a sequence of [zero or more] characters is a string"?

diabolo

Posts: 71
Joined: Fri Aug 08, 2008 4:17 pm UTC
Location: france

### Re: Recursive definition of a String

Yeah perhaps you should leave "sequence" out. In that case, either define how the absence of any character is enough to call it a string (without calling it an "empty string" straight away), or use some kind of special terminal symbol.
Hey, like coding? Perhaps you should check out the red spider project.
Feel free to call me Julian. J+ is just an abbreviation.

Jplus

Posts: 1091
Joined: Wed Apr 21, 2010 12:29 pm UTC

### Re: Recursive definition of a String

I talked to my lecturer and discovered the answer.

The base case is definitely missing and the base case is that a lone character is counted as a string.

Makes less sense than some of the stuff mentioned in this thread, but that's apparently what he was expecting.
DantesInferno

Posts: 5
Joined: Tue Jan 18, 2011 11:13 pm UTC

### Re: Recursive definition of a String

Hmm? Zero characters isn't a string? How Fortran of the lecturer.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk

Posts: 10038
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Recursive definition of a String

Yakk wrote:Hmm? Zero characters isn't a string? How Fortran of the lecturer.

Funny that you say that, the lecturer actually had a big (Off-topic) discussion about the development of programming languages and how he's been there since the beginning. He gave great emphasis on his time as a FORTRAN programmer
DantesInferno

Posts: 5
Joined: Tue Jan 18, 2011 11:13 pm UTC

### Re: Recursive definition of a String

Well, your lecturer's preferred answer is valid, but it doesn't match the definition of "string" in virtually any programming language (except FORTRAN I guess). So maybe don't learn that answer from him. ^_^
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 3989
Joined: Tue Feb 20, 2007 12:49 am UTC

### Re: Recursive definition of a String

Hadn't they invented empty strings back then? Maybe one day we'll invent negative strings and then we'll need a third clause to the recursive definition.

(Actually negative strings would come in handy sometimes, especially when you've got string operators. But I guess it'd be a bad idea to unify string concatenation and string difference when you'd be corrupting the "always succeeds" aspect of concatenation. Maybe you could have different datatypes, strings and signed strings where the former are automatically cast to the latter, like a mini numerical-tower.)
troyp

Posts: 398
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW