How do I think about recursion?

[shivajikobardan]

 

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.
 

 

[Eigenvektor]

A function is recursive if it calls itself again (and again, and again, …) to arrive at the solution. Not every problem is recursive in nature and even if it is, in practice you very rarely use a recursive algorithm to solve it, because they tend to be very inefficient.

 

For example the factorial of 4 is 4 + the factorial of 3. The factorial of 3 is 3 + the factorial of 2 and so on. You can generalize this as

"the solution of n! is n + (n - 1)!"

You need an abort condition, so 1! or 0! is defined as 1.

 

So you can write this as:

int factorial(int n) {
  if (n < 0) {
    throw new IllegalArgumentException("n must be greater than or equal to 0");
  }
  if (n <= 1) {
    return 1;
  }
  return n + factorial(n - 1);
}

This is considered "recursive" because the factorial method internally calls itself again with a different argument.

39 minutes ago, shivajikobardan said:

eg: a+b

=a+b-1+1

=SUM(a+1,b-1)

Not sure what you're trying to do here, but that is not recursive?

 

Quote

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.

Do you mean you want to determine whether a number is a palindrome? You could write this as a recursive algorithm by checking whether first and last digit of the number are identical. If they are, call yourself again with the first and last digit removed otherwise return false.

 

Example:

123454321

 

To determine whether this is a palindrome, you check whether the first and last digit are identical. They are, so you can continue (otherwise the answer is no). Call yourself again with the first and last digit removed, i.e. 2345432. Abort condition: If you're left with a single digit, it's a palindrome. If you're left with two digits it's a palindrome if both are identical.

[BlueChinchillaEatingDorito]

32 minutes ago, shivajikobardan said:

 

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.

So recursion you can think of is breaking a problem into the smallest sub-problem with a base case. So in the case of factorials, you break 4! to the sub problems shown in your image.

 

The result of all of these sub-problems combined will be your answer. 

 

So in the case of palindrome, you want to break the phrase 10101 for instance into sub problems where if all the inner sub-numbers of 10101 are palindromes, then 10101 is also a palindrome. 

Number = 10101

isPalindrome(10101)
	10101 is longer than 2 digits, call isPalindrome for the inner digits
  	isPalindrome(010)
    	010 is longer than 2 digits, call isPalindrome for the inner digits
        	isPalindrome(1)
            	any single digit or character is a palindrome, 1 is a palindrome, return True
        the first and last digits in 101 match and inner digits are also a palindrome, thus 101 is also a palindrome, return True
    the first and last digits in 10101 match and inner digits are also a palindrome, thus 10101 is also a palindrome, return True
    

 

1          0          1          0          1   <- Both outer digits are same and inner sub-number are a Palindrome so it too is a Palindrome
           |                     |
           -----------------------
                      |
                 0    1    0   <- Both outer digits are same and inner sub-number are a Palindrome so it too is a Palindrome
                      |
                      1     <- Is a single nubmer so a Palindrome

 

[mariushm]

Recursivity is not an optimal method to determine if a number is a palindrome or not. Even for strings, it's a bad application, because other methods work better.

 

For a number, you could just reverse the digits and then compare the two integer values:

 

$number = 12321;
$reverse= 0;
$temp = $number;
while ($temp > 0) {
	$reverse = $reverse * 10 + $temp % 10; // % = mod, \, remainder of number divided by 10
	$temp = intdiv($temp,10);	// integer division or temp / 10 in c , if both values are integer
}
echo $reverse;

 

For strings, it's much faster and less memory and processor intensive to do it without recursivity, because each time the function calls itself, there's some data that has to be saved up and then restored once the function exits, and lots of functions nested inside each other , you get all those extra "save and restore at exit" stuff that uses resources.

 

For strings you just determine the string length, divide it by 2 and then go from the edges to the center and check characters.

 

<?php
$text = "abcdefgfedcca";

var_dump(is_palindrome($text));
var_dump(is_palindrome2($text));

function is_palindrome($text){
	$len = strlen($text);
	$half = intdiv($len,2);
	for ($i=0;$i<$len;$i++) {
		$a = substr($text,$i,1);
		$b = substr($text,$len-1-$i,1); // because strings start from 0
		if ($a!=$b) return FALSE;
	}
	return TRUE;
}
                            
// using reverse string function in php 
//(could be slower because in previous function we exit at the first bad character)
// this one has to reverse whole string before we check
                            
function is_palindrome2($text) {
	return strrev($text)==$text ? true : false;
}
?>

 

A good application of recursivity could be for example sorting a big array of numbers.

You have 1000 numbers, you start the function  with two parameters, the start point and end point  in array.

The function can then call itself two times, with half the array, and so on until the length is low enough it's not worth dividing further.

Then when you come out of recursivity, merge the two strings, and return and so on ...

 

Here's an example of such usage :

(json_encode is just used to output the array of numbers on the screen in a nice way, it just does "[  number 1 , number 2 , .... , number n ] so ignore it :

 

 

<?php

$numbers = [];
for ($i=0;$i<24;$i++) { $numbers[$i]=mt_rand(0,1000); }
echo json_encode($numbers)."\n";
$result = sort_recursive($numbers,0,23);


function sort_recursive(&$numbers,$from,$to,$level=0) {
	echo "level=$level, from=$from,  to=$to\n";
	$count = $to-$from;
	if ($count<8) { // too few numbers to recursive it, so sort it
		$sorted=false;
		while ($sorted==false) {
			$sorted=true;
			for ($i=$from;$i<$to;$i++) {
				if ($numbers[$i]>$numbers[$i+1]) { 
					$temp=$numbers[$i];
					$numbers[$i]=$numbers[$i+1];
					$numbers[$i+1]=$temp;
					$sorted=false;
				}
			}
		}
		echo json_encode($numbers)."\n";
		return ; 
	} else {
		//split this interval into two smaller chunks,
		// call myself two times and then merge the two sorted intervals
		$split = intdiv($count,2);
		$result = sort_recursive($numbers,$from,$from+$split,$level+1);
		$result = sort_recursive($numbers,$from+$split+1,$to,$level+1);
		// when we return the two segments are sorted but the whole segment.
		// may not be sorted ex s1 = 1,5,7 s2 = 2,3,10
		// we need to merge them ex s = 1,2,3,5,7,10
		$i=$from;
		$j=$from+$split+1;
		//can be done without extra temp arrays but easier to understand this way
		$a = [];
		$b = [];
		// array_push places the value into array
		for ($i=$from;$i<$j;$i++) array_push($a,$numbers[$i]);
		for ($i=$j;$i<=$to;$i++) array_push($b,$numbers[$i]);
		
		for ($k=0;$k<=$count;$k++){
			if ((count($a)>0) && (count($b)>0)) {
				if ($a[0]<=$b[0]) {
					// pulls first value from a and shrinks the a array
					$numbers[$from+$k] = array_shift($a);
				} else {
					// pulls first value from b and shrinks the b array
					$numbers[$from+$k] = array_shift($b);
				}
			} else {
				// at some point one of the arrays may be empty so we jus
				// copy what's left from the other non empty array
				if (count($a)>0) $numbers[$from+$k] = array_shift($a);
				if (count($b)>0) $numbers[$from+$k] = array_shift($b);
			}
		}
		echo "merge $from $to ".json_encode($numbers)."\n";
	}
}
?>

 

and here's the output with 24 random numbers :

 

[859,516,465,276,36,148,695,473,320,87,839,725,165,616,538,534,171,93,329,744,676,447,755,542]
level=0, from=0,  to=23
level=1, from=0,  to=11
level=2, from=0,  to=5
[36,148,276,465,516,859,695,473,320,87,839,725,165,616,538,534,171,93,329,744,676,447,755,542]
level=2, from=6,  to=11
[36,148,276,465,516,859,87,320,473,695,725,839,165,616,538,534,171,93,329,744,676,447,755,542]
merge 0 11 [36,87,148,276,320,465,473,516,695,725,839,859,165,616,538,534,171,93,329,744,676,447,755,542]
level=1, from=12,  to=23
level=2, from=12,  to=17
[36,87,148,276,320,465,473,516,695,725,839,859,93,165,171,534,538,616,329,744,676,447,755,542]
level=2, from=18,  to=23
[36,87,148,276,320,465,473,516,695,725,839,859,93,165,171,534,538,616,329,447,542,676,744,755]
merge 12 23 [36,87,148,276,320,465,473,516,695,725,839,859,93,165,171,329,447,534,538,542,616,676,744,755]
merge 0 23 [36,87,93,148,165,171,276,320,329,447,465,473,516,534,538,542,616,676,695,725,744,755,839,859]

 

You can see the function starts at level 0 with from = 0 and to = 23 , so it knows there's more than 8 values to sort, so it calls itself two times. Once it's with level 1 from 0 to 11, and the second time is level 1 from 12 to 23.

so we go first in level 1 from 0 to 11 and that function also realizes it's more than 8 numbers, so it calls itself again twice, and we're at level 2 from 0 to 5 , and level 2 from 6 to 11

The function level 2 from 0 to 5 notices finds there's only 6 numbers to sort so no longer calls itself, it just sorts the numbers and returns.

The function level 2 from 6 to 11 also notices there's less than 8 numbers to sort, so it just sorts the array and returns.

Now the control goes back to the previous function (level 1, from 0 to 11) and the function now knows there's two segments that are each sorted : from 0 to 5 and from 6 to 11, so it merges them and returns.

Now the control goes back to the previous function, which calls sort with the 2nd segment, when that function returns it merges the two segments and so on... 

[Guest]

Do you know what a for loop is? 

 

That but extra steps. 

[Takumidesh]

I tend to avoid recursion in real life, it adds complexity and makes it hard to maintain. The compiler unrolls it anyway 99% of the time.

 

Whenever I see recursion in production code I always roll my eyes because I know it will be difficult to troubleshoot.

[Toxocious]

I'll spare you an example of recursion as there are plenty of solid examples in previous posts here, but I want to add that when you're attempting to make a recursive function, also consider the exit case(s) of the function before anything else. Add the logic for your exit cases first, where applicable, and then add the logic for whatever the function needs to accomplish second. Go back when necessary to add additional exit cases if the need arises.

 

Recursion has its use cases where it makes more sense than using a traditional loop, but if you forget about an exit case, there's a high chance that you'll end up endlessly recursing.