1

I have a simple java program that takes a number and executes a function based on that number.

public class Palidrome {
public static void main (String[] args) {
    int N = 3;
    System.out.println(palidrome(N));
}

public static String palidrome(int i) {
    if (i == 0) return "S";
    if (i == 1) return "T";
    return palidrome(i-2) 
            + palidrome(i-1)
            + palidrome(i-2);
    }
}

So for this example N = 3, and the output is "TSTST". If N is changed to 5, the output is "TSTSTSTSTSTSTSTSTSTST" etc.

I'm struggling to figure out why this is the case. If N = 5, palidrome(i-1) and palidrome(i-2) will never reach (i == 0) or (i == 1) so nothing should be returned theoretically?

Thanks in advance!

1
  • "palidrome(i-1) and palidrome(i-2) will never reach (i == 0) or (i == 1)" .. this is correct, it doesn't satisfy these checks, but your method doesn't stop there, so keep reading it ... Also this code is incomplete, since it can't handle negative i values.
    – Tom
    May 30, 2016 at 17:36

3 Answers 3

4

This can be understood by drawing the recursion tree.

                                            palindrome(5)
                                         /        |         \   
                            palindrome(3)     palindrome(4)  palindrome(3)
                           /     |        \  ............................
                          /      |         \
              palindrome(1)   palindrome(2)  palindrome(1)
                             /     |       \
                            /      |        \
              palindrome(0)  palindrome(1)  palindrome(0)

So palindrome(5) will ultimately reach palindrome(0) and palindrome(1) calls.
NOTE: The recursion ends at palindrome(0) and palindrome(1) calls.

0
1

Let's run through what happens line by line for N = 5.

  1. palindrome(5) is called --> i is not 0 or 1 --> return the results of palindrome(3) + palindrome(4) + palindrome(3)
  2. We need the results of palindrome(3) to build our result for palindrome(5). So palindrome(3) is called. --> i is not 0 or 1 --> return the results of palindrome(1) + palindrome(2) + palindrome(1)
  3. We need the results of palindrome(1) to build our result for palindrome(3). So palindrome(1) is called. --> i = 1, so "T" is returned
  4. We need the results of palindrome(2) to build our result for palindrome(3). So palindrome(2) is called. --> i is not 0 or 1 --> return the results of palindrome(0) + palindrome(1) + palindrome(0)
  5. I'll glaze over the recursion here, but we get "STS" for the results for palindrome(2).
  6. This means we get palindrome(1) + palindrome(2) + palindrome(1) = "TSTST" for palindrome(3).
  7. This result is returned to our original palindrome(5) call.

Hopefully that helps illustrate the recursion for you.

1

Each successive recursive call for palidrome should bring you closer to the base-case which is here:

if (i == 0) return "S";
if (i == 1) return "T";

so theoritcally saying

palidrome(i-1) and palidrome(i-2) will never reach (i == 0) or (i == 1)

is wrong as those statements will be eventually reached but after the i changes to satisfy the condition.

How would var i change you are probably wondering! well through this statement:

return palidrome(i-2) 
            + palidrome(i-1)
            + palidrome(i-2);

Here you are calling palidrome recursively but (i is decreased), this will eventually lead you to the base-case.

if your function never hit the base-case then you'll have an infinite recursion and this is not the case over here.


To simplify things lets take a look at this Example:

assume that you have a generous neighbor that will give you one apple if you visit him once, also another one if you visit him twice then he'll start giving you as mush as he gave you that last 2 times (that's actually a fibonacci sequence) so the general-case here is: numberOfApplesThatYouGet= numberOfApplesThatYou'veGotIn(currentVisitNumber-1(Which is Last Visit))+numberOfApplesThatYou'veGotIn(currentVisitNumber-2)

and lets assume that currentVisitNumber = n and numberOfApplesThatYouGet = a method called fib

so general rule would be -->

fib(n)=fib(n-1)+fib(n-2)

But we still need a base-case to terminate an infinite recursion and here the base-case is your first visit condition which is

if(n==0) return 0;//if you didn't visit him you'll get nothing
if(n==1) return 1;//if you did you'll get an apple

so the Method will look like this:

public int fib(int n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
      return 1;
   else
      return fib(n - 1) + fib(n - 2);
}

lets assume that you bare him three visits, how many apples would you get?

fib(3)->fib(2)+fib(1)

fib(2)->fib(1)+fib(0)->1+0->1

fib(1)->1

1+1=2
#done

Also take a look at this to form a better understanding of recursion.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.