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.
i
values.