How do I think about recursion?

[polaryeti]

 

 

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.

[requinix]

What do you mean "finding a palindrome of a number"? Because you don't really find palindromes...

Do you want to check if a number is a palindrome? Like 12321 is but 1232 is not?

[polaryeti]

yes I mean to check palindrome string.

[requinix]

Recursion is the idea of solving a problem by breaking it down into smaller problems that look similar but are a bit smaller.

The classic example is the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55... It is defined as being F(n) = { if n <= 2 then 1; else F(n-1) + F(n-2) }. If you want to solve the problem of "what is the 10th Fibonacci number" then you apply recursion by (1) breaking it down into "what is the 9th Fibonacci number" and "what is the 8th Fibonacci number" and (2) adding the two results together. At the end you have what's called the "base case" which is the point where the problem has been broken down as far as it can go and you don't need to do any more recursion, which is "the 1st and 2nd Fibonacci numbers are 1".

Let's say you have the problem "Is the string 8762395408668055932678 a palindrome?" What can you do to make that into a similar but smaller problem?

 

[gizmola]

There are no doubt a number of different solutions to this.  Here is one.

So one way to look at it is that in order for a word to be a palindrome, letters offset from each other must be the same.  

Treating the word as an array, that means you can check word[0] against word[word.length-1] , and if those characters are the same, then it could be a palindrome.  If not, it is definitely not a palindrome.

Now if you then remove the outer characters (using shift and pop), and check again, this same process is also valid on the remaining inner string. 

Thus you have an opportunity to use recursion.  You can continue this process until the string you are checking has 1 character or less remaining.    If you get to the point that the array of characters has no characters remaining then it was a palindrome. 

 

 

Here is an implementation of this idea:

function isPalindrome(word) {
    let palindrome = true
    word = word.split("")
    //console.log(word)
    if (word.length < 2) {
        return palindrome
    }
    palindrome = (word[0] === word[word.length-1])
    if (!palindrome) {
        return palindrome
    }
    word.pop()
    word.shift()
    return isPalindrome(word.join(""))  
}


const words = ["HelloWorld", "abba", "abcdecba", "a", "oio", "nevermoreromreven"]
words.forEach(word => console.log(`"${word}" is a Palindrome: ` + isPalindrome(word)))

 

[gizmola]

I should probably add that the secret to determining if recursion allows for something elegant, is to determine if you can reduce the problem down to a discrete examination.  In the case of my solution, the insight I depend upon is that I only need to check the outer 2 letter of the string in order to determine if it *might* be a palindrome. 

Another solution using this insight could also be coded using map and reduce. 

It also needs to be said that the overhead of recursion means that it is almost never employed, although there are some problems involving nested arrays where I see people using it in PHP.  

[maxxd]

If the OP is looking to find out if the numerical string is a palindrome, recursion isn't necessary. A palindrome is the same forward and backwards; use split(), reverse(), and join() on the input and compare it to the original string. However, the images of code in the first post have nothing to do with palindromes, they're all about something like the Fibonnacci sequence that requinix describes.

Edited December 12, 2022 by maxxd