Problems with understanding recursion

Question

I have problems with understanding recursion, I don't get the explanations in books and tutorials. The example below finds the greatest value in a list, here I get stuck at the second line, I simply don't understand what is happening after max([H|T], Max) when H > Max ->

I would really appreciate if I could get an explanation of all the steps in the code, for instance why it goes -> max(T, H); and -> Max.

max([H|T]) -> max(T, H).

max([H|T], Max) when H > Max -> max(T, H);
max([_|T], Max)              -> max(T, Max);
max([],    Max)              -> Max.

Many thanks! E.

There's a really detailed post on recursion on SO if you haven't found it already: http://stackoverflow.com/questions/717725/understanding-recursion?rq=1 — kjw0188, Jan 10 '14 at 08:41

score 3 · Accepted Answer · answered Jan 09 '14 at 23:25

3

I tried to explain step by step. Let's assume that you have a list: [2, 3, 1]

max([2, 3, 1]).
H=2 , T=[3, 1]
max([H|T]) -> max(T, H).
H=3, T=[1], Max=2
max([H|T], Max) when H > Max -> max(T, H);
Here when block says: if H is greater than Max then call max function again as max([1], 3).
Here we are again but with different values:
H=1, T=[], Max=3
max([H|T], Max) when H > Max -> max(T, H);
1 > 3 is false so when block fails and trying next max function definition which leads to step 5.
We know H is less than Max because step 4 failed so we are ignoring it.
T = [], Max=3
max([_|T], Max) -> max(T, Max);
We are matching last function definition which says max element found:
[] = [], Max = 3
max([], Max) -> Max.

answered Jan 09 '14 at 23:25

Mustafa

401
2
7

I really like this explanation but how does it turns out that Max=2 in the third step? – Eri. Jan 10 '14 at 00:02
@Eri that's because it is passed as `2` by the second step (see that `H=2`?). – Agis Jan 10 '14 at 00:05
I must be blind or just stupid but I don't see where in the second step Max is passed as 2. Or how. – Eri. Jan 10 '14 at 00:12
At second step, `H=2 , T=[3, 1]` when you call `max(T=[3, 1], H=2)`. It is passing H as Max. – Mustafa Jan 10 '14 at 00:34
Could you please explain why? It seems that I don't really understand step 2 and 3. H=2 , T=[3, 1] of course make sense but then at -> max(T, H) I get stuck. – Eri. Jan 10 '14 at 01:01
At step 2 `max(T, H)` means `max([3, 1], 2)`. So you are calling max function with two parameters. And it matches with `max([H|T], Max) when H > Max -> max(T, H);` block because it has two parameters (list and int). At this step `H=3` and `Max=2` so `when` blocks returns true (3 > 2), then inner function call is being executed: `max(T, H)`. I don't know how I can explain more clearly :) – Mustafa Jan 10 '14 at 01:15

score 1 · Answer 2 · answered Mar 03 '15 at 05:35

Best way to understand recursion is by visualizing it. Let me give you a very simple example:

Suppose you want to know what is eligibility to become a prime minister of US, which is:

You have to be national citizen of US, for which here is the rule:

You are a natural born of US (or)
Your parents are national citizen of US

Now, first option straight forward makes you citizen of US, or same whole thing applies to your parents, which may again check for their parents ..and so on.

So there will be a straight forward answer, which is here 1st option. That is called Base Case. And in 2nd option you might apply same process of checking citizenship for your parents.

Here is a very simple pseudo code that can explain recursion:

isEligibleForPrimeMinister checkCitizenship(You, yourParents){
          Base Case {returns true(That you are US citizen)}
          checkCitizenship(yourParents, YourGrandParents)
          }

Hope this helps.

score 0 · Answer 3 · answered Jan 09 '14 at 23:49

This function could be rewritten like this:

max([H|T]) -> max(T, H).

max([], Max) -> Max;
max([H|T], Max) ->
   NewMax = if H > Max -> H;
               true -> Max
            end,
   %% NewMax = erlang:max(H, Max),
   max(T, NewMax).

To understand it you must know how pattern matching works.

We take the head element of the list and consider it current maximum. We need to look at all the rest elements that are in the tail and check if any of them is greater.
If the rest of the list is empty, the current maximum is the result.
If the list is not empty take new head and determine the new maximum. Then go on with the rest of the list and new maximum. The thing that must be noticed here is that list passed to the next iteration of max/2 is always the tail of the previously passed value so we don't check values we already saw.

score 0 · Answer 4 · answered Jan 10 '14 at 00:01

The last three lines in your code are all different clauses of the same function (max/2). This means that whenever the max function is called with two arguments passed, it will be pattern-matched against these three clauses.

This clause:

max([_|T], Max) -> max(T, Max);

will match whenever the list is non-empty and the head of the list (H) is less than or equal to Max. It will call max/2 passing T which is a list and Max which is a number. This new call will also be pattern-matched against the three clauses.

This clause:

max([], Max) -> Max.

will match whenever the list is empty and will return just Max which is a number.

Problems with understanding recursion

4 Answers4