# Give a recursive function $r$ on $A$ that reverses a string

I really need help with this task here. Im stuck at it and I really would appreciate your help

Give a recursive function $$r$$ on $$A$$ that reverses a string. For instance, $$r(logikk) = kkigol$$ and $$r(moro) = orom$$. (given that $$A$$ the amount of letters in the Norwegian alphabet which has 29 letters.). Define the function in such a way that it is correctly regardless of what $$A$$ are.

Also $$logikk$$ means $$logic$$ in norwegian, and $$moro$$ means $$fun$$ in norwegian in case you're wondering.

Edit:

I tried to solve one of the recursive functions, $$r(logikk)$$, but i'm not sure if all of it is correct:

$$\Lambda =$$ The empty string

$$r(\Lambda) =$$ $$\Lambda$$, $$r(k) = k$$, $$r(k) = k$$, $$r(i) = i$$, $$r(g) = g$$, $$r(o) = o$$, $$r(l) = l$$

For any word $$w$$ and letter $$a$$, $$r(wa) = wa$$

Can someone please check if this is correct for $$r(logikk)$$ I feel like i'm missing something but i'm not sure what.

• In which way is this a computer science and not a programming question (which should be on Stack Overflow)? (Hint: you can do stuff while descending recursively, and while "coming up".)
– Raphael
Oct 14 '13 at 7:57
• It's an exercise in some computer science course. Can you guess which, and how theoretical the course is? Oct 14 '13 at 16:59

A recursive function requires base cases and recursive rules. Depending on how your system works, your base cases might include:

• $r(\lambda) = \lambda$
• $r(\sigma) = \sigma$ for $\sigma \in \Sigma$
• etc.

You then need a general rule for more complicated cases. You're on the right track; you need a rule that takes something of the form $\sigma w$, where $\sigma \in \Sigma$ is a single letter and $w \in \Sigma^*$ is some arbitrary string, and produces the correct output. You will likely find, and should try to prove, that a rule like the following works:

• $r(\sigma w) = w \sigma$

Fits the bill. Putting it all together, in pseudocode, you should arrive at something roughly like the following:

Reverse(string[1...n])
1. if n = 0 then return the empty string
2. else if n = 1 then return string[1]
3. else return the concatenation of Reverse(string[2...n]) with string[1]


Hint: Distinguish between two cases: the input is a single letter $\alpha$, and the input is a word $w = \alpha x$ (where $\alpha$ is a letter). In the first case, $f(\alpha) = \alpha$. What can you say in the second case? (For example, consider $w = logikk$, $\alpha = l$, $x = ogikk$.)

• could you please check my edit on the post and check if i'm in the right direction? Oct 13 '13 at 20:48
• I'm afraid your answer is meaningless. You should write a function $r$ that on input $w$ outputs the reverse of $w$. You can check you definition to see if it indeed gives $r(logikk) = kkigol$. Also, I don't see why you need to define $r(k) = k$ twice, and why you can't just define in general $r(x) = x$ for any symbol (letter) $x$. Finally, you are confusing variable names and strings. Your function should really satisfy $r("logikk") = "kkigol"$, where "..." indicates a string. Oct 14 '13 at 1:54