Best way to think about implementing recursive methods?

Question

so I was wondering if any of you can give me tips regarding this. I've been doing some challenges like (the classical) making a method to calculate the nth number of a Fibonacci sequence using a single recursive call (aka. avoid return fibo(n-1) + fibo(n-2);).

I really scratched my head on that one and ended up looking at the solution that made use of a helper method -

public static int fibonacci(int n) {
    if (n < 2) {
        return n;
    }
    return fibonacci_helper(n, 1, 0);
}

public static int fibonacci_helper(int n, int previous, int current) {
    if (n < 1) {
        return current;
    }
    return fibonacci_helper(n - 1,  current, previous + current);
}

I'm not really sure what approach one takes to solve questions like that quickly (without first solving it iteratively and translating that to a tail recursion, which takes a lot of time).

Would really appreciate some tips, thanks in advance.

Answer 1

Play with it on paper, and try discover hidden computations that are redone needlessly. Then try to avoid them.

Here you have f(n) = f(n-1) + f(n-2); obviously f(n-1) = f(n-2) + f(n-3) redoes f(n-2) needlessly, etc. etc. etc.. What if you could do the two at once?

Have f2(n) return two values, for n and for (n-1); then you do (in pseudocode)

f(n) = let { (a,b) := f2(n-1) } in (a+b)

Now you have two functions, none is yet defined, what good does it do? Turn this f into f2 as well, so it returns two values, not one, just as we expect it to do:

f2(n) = let { (a,b) := f2(n-1) } in (a+b,a)

And voila, a recursive definition where a is reused.

All that's left is to add some corner/edge/base case(s), and check for the off-by-1 errors.

Or even better, reverse the time arrow, start from the base case, and get your iterative version for free.

Recursion is a tool which is there to help us, to make problem solving easier.