Click here to Skip to main content
15,946,988 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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

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!
 
Share this answer
 
Comments
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 ...
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.
 
Share this answer
 
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.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900