Is this method a case of recursion or an Iteration?

Question

I have been working on understanding recursion as applies to some examples like Fibonacci and also an Additive Sequence like the one below..

int AdditiveSequence(int n, int t0, int t1){
    if(n == 0) return t0;
    if(n == 1) return t1;
    return AdditiveSequence(n - 1, t1, t0 + t1);
}

I thought about how it could apply and tried this:

static final double PERCENT = 0.005;

double Depreciation(int month, double currentValue){
    if(month == 0)return currentValue;
    return Depreciation(month - 1, currentValue -= currentValue * PERCENT);
}

But this does not seem to be a recursion and more like an iteration as when I view in Eclipse debug screen it exits on month == 0 with the iterated currentValue being returned correctly.

In the case of the Factorial(n) method:

int Factorial(f){
    if(f == 1){
      return 1;
    }else{
      return f * Factorial(f - 1);
    }
}

It seems to defer computation until the base case is reached and then return back down the stack until the result is reached...

Can anyone help me identify what I have done with the above Depreciation method and if it is in fact recursion or iteration.

It is recursion I think because function refer to itself so it goes like a chain until condition will success and all chain goes back. — solvator, Feb 22 '14 at 17:30
As @solvator said it is definitely a recursion since it's calling itself in order to calculate the return value. — fejese, Feb 22 '14 at 17:45
Note that you should use `currentValue - (currentValue * PERCENT)` since the modification of currentValue in the current recursion does not make sense. — Ingo, Feb 22 '14 at 17:47
It is recursion at the source level. Now, what optimization can the JVM do to make recursion "faster"? This may explain the debug output. — Eric Platon, Feb 22 '14 at 17:48

score 1 · Answer 1 · answered Feb 22 '14 at 17:46

This is actually called tail recursion, which means you have the result when you reach the end of the recursion. This type of recursion is easily converted to iterative code and often is by the compiler

static final double PERCENT = 0.005;

double Depreciation(int month, double currentValue){
    if(month == 0)return currentValue;
    return Depreciation(month - 1, currentValue -= currentValue * PERCENT);
}

in you're case the current value is being accumulated the whole way, which is the reason it fits the profile for tail recursion.

score 1 · Answer 2 · answered Feb 22 '14 at 18:37

1

I think the AdditiveSequence too must be called tail recursion as that too exits on completion - i.e. (n == 1)return t1; as that satisfies the computation...

answered Feb 22 '14 at 18:37

DevelopeXCode

65
6

yes `AdditiveSequence` is also tail recursion ( [what is tail recursion](http://stackoverflow.com/questions/33923/what-is-tail-recursion)) – aaronman Feb 26 '14 at 00:58

Is this method a case of recursion or an Iteration?

2 Answers2