15,742,655 members
See more:
I got the idea for problems like factorials or finding sum from 1 to n, where there's a pattern visible. Like this:

Source:https://99x.io/blog/recursion-is-not-hard-here-is-the-right-way-to-think

I got it for things like addition, subtraction, division, multiplication of two numbers as well.

eg: a+b

=a+b-1+1

=SUM(a+1,b-1)

Now, I am wondering how it'll be for finding a palindrome of a number? I've a solution but I'm not understanding how we came towards it. I'm looking for how to come towards a solution than a solution itself.

What I have tried:

I've tried learning other materials like addition, fibonacci etc.
Posted
Updated 11-Dec-22 2:21am

## Solution 3

Quote:
Now, I am wondering how it'll be for finding a palindrome of a number?

Finding palindrome in a number is a bad idea because you have no practical tool to work on digits in a number. Number are made to work on the whole thing, like adding 2 number or multiply them.
The only practical way is having the digits in a string.
Quote:
How do I think about recursion.

Recursion is only 1 way to find an answer, there is other solutions, usually with loops.
Fibonacci: you think of recursion because the definition is very recursion friendly, but recursion is not the most efficient in this case.
```Recursion:
F(1) is 1 call to Fibonacci function.
F(2) is 1 call to Fibonacci function.
F(3) is 3 call to Fibonacci function.
F(4) is 5 call to Fibonacci function.
F(5) is 9 call to Fibonacci function.
F(6) is 15 call to Fibonacci function.
F(7) is 25 call to Fibonacci function.```

The high cost is that to calculate any Fibonacci value, there is more calls to the function than the result itself.

You can also use a loop and go upward.
C++
```int Fibonacci(int N) {
int A=1, B=1;
if (N < 3) return 1;
for(int Cnt=1; Cnt < N; Cnt++) {
Int Tmp= A+ B;
A= B;
B= Tmp;
}
return B;
}```

For Fibonacci(N), it loop N times.

Palindrome: The loop approach.
Any 1 letter substring is a palindrome, say Center.
For any Center, if the letter on right is same, it is a bigger palindrome.
If letter on left and letter on right of current palindrome are same, it is a bigger palindrome.
Any palindrome of size N can be the center part of a palindrome of size N+2.

## Solution 2

Recursion means calling a function from itself, either directly or indirectly.
If you look at a palindrome, you can see that it's either this pattern:
`ABCDEDCBA`
for an odd number of elements, or this pattern:
`ABCDDCBA`
for an even number of elements.
So you can think of it as a "set" of strings nested inside each other, all of which must be a palindrome in order for the whole to be:
```ABCDEDCBA
BCDEDCB
CDEDC
DED
E```
Or
```ABCDDCBA
BCDDCB
CDDC
DD```
Which gives you a "recursive algorithm" you could apply: pass the function a string `str`, it's length `len`, and the current check index `n` and you can compare substrings by comparing the character at index `n` with the character at index `(len - (n + 1))`
If they are different, the string is not a palindrome, so you return `false`
If they are the same, you call the same function with the index `n` increased by one.

Obviously, you need a check that you haven't checked all the elements - if you have, you return `true`.

That'll work. But ... it's a very poor idea to apply recursion to this kind of problem (just as it is for factorials and most other "school homework" examples) as each time you call a function, you take up memory on the Stack - which is not infinite, in fact it's pretty small. If you use up all the stack space, your app will crash, and it doesn't take a particularly long string you want to check to use up the whole stack!

Recursion is a powerful technique, but it needs to be applied sensibly: just because you can do something, doesn;t mean you should!

Member 15627495 11-Dec-22 5:09am
as fact, once you have a loop to write you can go through recursion.
only keep the 'body' of the loop and write a function with the good parameters to transmit to the next iteration. // recursion style stay hard to read , you'll see that 'lean code' exists too, with the aim to be quickly understandable by others. //
because of great speed, recursion is a powerful style of writing code lines. It's 'less code', and more calls of memory heap/stack. that is where the gain of velocity by recursion operates. Instead of iterations in a loop , the involved function is call again and again, it's 'shortest path' features.
OriginalGriff 11-Dec-22 5:47am
"Great speed"? "Shortest path"? "Less code"?

No, no, and no again!
Recursion is expensive compared to a loop: it takes more memory than an equivelant loop, takes longer to execute as a result, takes more code to write, and ultimately is less reliable because it relies on stack space you have no control over!

Recursion is a tool - and like any other type of tool it is suitable only for specific circumstances so using it "willy-nilly" is a schoolboy error!

In this specific case, a loop is both simpler and a lot more appropriate to the data.
Member 15627495 11-Dec-22 5:57am
I join your opinion on the case of badly written recursion ...

## Solution 1

Testing whether a string is a palindrome requires you to compare the letters from opposite ends. So a recursive method could be to compare the first and last letters. Then recursively pass a copy of the string without the first and last letters. If the letters match return TRUE, if not return FALSE.