Can anybody tell me how does this work and why the answer is 11?

Question

public static int lucas(int n)
{
if(n == 1)
return 1;
if(n == 2)
return 3;

return lucas(n-1) + lucas(n-2);
}

Answer 1

it is called akermen function. search web about this

Answer 2

You are missing a handler for lucas(0). This is a recursive function, meaning that the values are output as a sequence, higher values built from lower values.

The table of inputs to outputs for this seems to be:

input output
0 {undefined}
1 -> 1 // defined
2 -> 3 // defined
3 -> 4 [ lucas(2)+lucas(1) = 3 + 1 ]
4 -> 7 [ lucas(3)+lucas(2) = 4 + 3 ]
5 -> 11 [ lucas(4)+lucas(3) = 7 + 4 ]
6 -> 18 [ lucas(5)+lucas(4) = 11 + 7 ]
7 -> 29 [ lucas(6)+lucas(5) = 18 + 11 ]
8 -> 47 [ lucas(7)+lucas(6) = 29 + 18 ]
and so on...
...

The sequence of output is related to, but not the same as, the Fibonacci numbers. The difference there is [ 2 -> 2 ]. You can examine this sequence in the source list, and how universal that one is.

For academic reasons, CS discrete math classes will propose your sequence as an alternative study sequence for recursion introductions.

Your sequence has a "closed form" (non-recursive solution) that is a variant of the golden ratio, also in the sources.

Answer 3

The function name is a clue; these are actually called "Lucas Numbers", and they are very similar (and related) to Fibonacci Numbers.

http://en.wikipedia.org/wiki/Lucas_numbers

Starting from n=1 in your function, the sequence would be:

1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...

where each number is the sum of the previous two (123 = 47 + 76).

The way the function works is through recursion. Recursion is where a function calls itself to perform some part of the operation; this is often used when a task progressively builds upon previous results, as in this case. It's not the most practical way to implement the sequence, though... in this case, every number in the sequence winds up getting calculated twice.

Answer 4

the answer is only 11 if n=5 (the first time).

This is a recursive function, meaning it calls itself over and over until it gets a final result.

if you input 5 - lucas(5); it returns lucas(4) + lucas(3)
lucas(4) returns lucas(3)+lucas(2)
lucas(3) returns lucas(2)+lucas(1)
lucas(2) returns 3
lucas(1) retuns 1

if you plug it in recursively:
lucas(3) returns 3+1 ->4
lucas(4) returns 4+3 ->7
lucas (5) returns 7+4 -> 11

Answer 5

The answer, understood as the final return, is not really 11. It varies depending on n.

Each time a lucas() function is ran, it calls itself twice, so it ends up calling itself a lot of times. (For example, for the number 10, it calls itself around 109 times and returns 123 - for the number 20, it calls itself 13529 times and returns 15127).

However, I don't really understand the logic behind this function, or how the number serie goes.