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.

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