How do I think about recursion.

Question

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 10-Dec-22 20:34pm

bhaskar977

Updated 11-Dec-22 2:21am

Add a Solution

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

OriginalGriff · Answer 1 · 2022-12-10T21:54:00

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!

Patrice T · Answer 2 · 2022-12-11T02:21:00

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.

Richard MacCutchan · Answer 3 · 2022-12-10T21:26:00

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.

How do I think about recursion.

3 solutions

Solution 2

Solution 3

Solution 1

Add your solution here

Preview 0