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

Question

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

Here is the task:

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.

• Raphael: 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".)
• Yuval Filmus: It's an exercise in some computer science course. Can you guess which, and how theoretical the course is?

Answer 1

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]

Answer 2

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$.)

• Dabbish: could you please check my edit on the post and check if i'm in the right direction?
• Yuval Filmus: 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.