How does the recursion here work?
fibonacci, java, recursion
Solution
Well, putting aside what a compiler actually does to your code (it's horrible, yet beautiful) and what how a CPU actually interprets your code (likewise), there's a fairly simple solution.
Consider these text instructions:
To sort numbered blocks:
- pick a random block.
- if it is the only block, stop.
- move the blocks with lower numbers to the left side, higher numbers to the right.
- sort the lower-numbered blocks.
- sort the higher-numbered blocks.
When you get to instructions 4 and 5, you are being asked to start the whole process over again. However, this isn't a problem, because you still know how to start the process, and when it all works out in the end, you've got a bunch of sorted blocks. You could cover the instructions with slips of paper and they wouldn't be any harder to follow.
Problem
Code 1: ``` public static int fibonacci (int n){ if (n == 0 || n == 1) { return 1; } else { return fibonacci (n-1) + fibonacci (n-2); } } ``` How can you use `fibonacci` if you haven't gotten done explaining what it is yet? I've been able to understand using recursion in other cases like this: Code 2: ``` class two { public static void two (int n) { if (n>0) { System.out.println (n) ; two (n-1) ; } else { return ; } } public static void main (String[] arg) { two (12) ; } } ``` In the case of code 2, though, `n` will eventually reach a point at which it doesn't satisfy `n>0` and the method will stop calling itself recursively. In the case of code 2, though, I don't see how it would be able to get itself from 1 if `n=1` was the starting point to 2 and 3 and 5 and so on. Also, I don't see how the line `return fibonacci (n-1) + fibonacci (n-2)` would work since `fibonacci (n-2)` has to contain in some sense `fibonacci (n-1)` in order to work, but it isn't there yet. The book I'm looking at says it will work. How does it work?