Let me explain a bit about my father. He is 54 y.o. and he wants to study some programming to develop android apps for his personal needs. So I decided to give him beginners introduction to Java. He has a copy of H.Schildt's Java 8 book. At one point he got stuck on the section called Recursion.
You know, this is quite a challange to explain to non-programmer what recursion is.
So, first I asked my dad what will be the output of the following code:
void out(int n) {
if (n > 0) {
System.out.println(n);
out(n - 1);
}
}
out(3);
"3 2 1" - he said.
- Yes this is correct.
Fine, what will be the output of the following code, if we had changed the order of instructions?
void out(int n) {
if (n > 0) {
out(n - 1);
System.out.println(n);
}
}
out(3);
"3 2 1" he said.
When I told him, that the code will output "1 2 3", he said that he didn't understand why.
Then I tried to expand "out" recursive calls in java notation (using java syntax and System.out.println), and show him that println statements go in "1 2 3" order, but still no luck, he wouldn't understand.
We tried different approaches, and here is the one that actually did the trick.
We used following notation to expand recursion method calls.
Let's see what happens to "1 2 3" example, when we start to expand recursion calls (we'll do it step by step).
"1 2 3" example, step-by-step recursion expansion.
I will highlight in red expanded lines on every step.
Step 1, expand out(3) call
out(3) // We call out(3) from outer code
-> 3 > 1 // n > 0 condition is true, as n equals to 3, and 3 is greater than 0
-> out(2) // out(n - 1) call, as n equals to 3, then n - 1 will equal to 3 - 1 = 2, so we call out(2)
-> print(3) // System.out.println(n), n equals to 3, so print(3)
Step 2, expand inner out(2) call
out(3) // We call out(3) from outer code
-> 3 > 0 // n > 0 condition is true, as n equals to 3, and 3 is greater than 0
-> out(2) // out(n - 1) call, as n equals to 3, then n - 1 will equal to 3 - 1 = 2, so we call out(2)
-> 2 > 0 // we're expanding out(2) call, n > 0 condition is true, inside the inner call n equals to 2 and 2 > 0.
-> out(1) // out(n - 1) call, as n equals to 2 in the inner call, 2 - 1 = 1
-> print(2) // print 2
-> print(3) // System.out.println(n), n equals to 3, so print(3)
Step 3, expand inner out(1) call
out(3) // We call out(3) from outer code
-> 3 > 0 // n > 0 condition is true, as n equals to 3, and 3 is greater than 0
-> out(2) // out(n - 1) call, as n equals to 3, then n - 1 will equal to 3 - 1 = 2, so we call out(2)
-> 2 > 0 // we're expanding out(2) call, n > 0 condition is true, inside the inner call n equals to 2 and 2 > 0.
-> out(1) // out(n - 1) call, as n equals to 2 in the inner call, 2 - 1 = 1
-> 1 > 0 // true, n > 0, n equals to 1, so 1 > 0 is true
-> out(0) // out(n - 1) call
-> print(1) // print 1
-> print(2) // print 2
-> print(3) // System.out.println(n), n equals to 3, so print(3)
Step 4, expand inner out(0) call
out(3) // We call out(3) from outer code
-> 3 > 0 // n > 0 condition is true, as n equals to 3, and 3 is greater than 0
-> out(2) // out(n - 1) call, as n equals to 3, then n - 1 will equal to 3 - 1 = 2, so we call out(2)
-> 2 > 0 // we're expanding out(2) call, n > 0 condition is true, inside the inner call n equals to 2 and 2 > 0.
-> out(1) // out(n - 1) call, as n equals to 2 in the inner call, 2 - 1 = 1
-> 1 > 0 // true, n > 0, n equals to 1, so 1 > 0 is true
-> out(0) // out(n - 1) call
-> 0 > 0 // false, n equals to 0 here and 0 cannot be greater than 0. the rest of statements in out(0) call are not executed.
-> print(1) // print 1
-> print(2) // print 2
-> print(3) // System.out.println(n), n equals to 3, so print(3)
In step 4, I highlighted print statements in blue color.
As we all know, programs execute statements from top to bottom, so the code will print "1 2 3".
"Factorial" example, step-by-step recursion expansion.
Fine, we just saw how to expand recursion calls with no return value.
We have following factorial calculation code:
int fact(int n) {
if (n > l) {
int result = fact(n - 1);
result = result * n;
return result;
}
else {
return 1;
}
return result;
}
System.out.println(fact(3)); // prints out "6"
Now let's see how to expand recursion with return value.
When you deal with return value, you should perform expansion in 2 ways:
- Forward expansion - when you expand recursion calls from topmost call to innermost, will be highlighted in red;
- Backward expansion - when you collect return values from innermost call to topmost, will be highlighted in blue.
Step 1, forward expansion, expand fact(3) call
fact(3)
-> 3 > 1 // condition n > 1 is true, as n equals to 3, 3 is greater than 1
-> result = fact(2) // it is a fact(n - 1) call, as n equals to 3, 3 - 1 = 2, so we call fact(2)
-> result = result * 3 // "result = result * n" statement, n equals to 3, will be explained in backward expansion
-> return result // will be explained in backward expansion
Step 2, forward expansion, expand inner fact(2) call
fact(3)
-> 3 > 1 // condition n > 1 is true, as n equals to 3, 3 is greater than 1
-> result = fact(2) // it is a fact(n - 1) call, as n equals to 3, 3 - 1 = 2, so we call fact(2)
-> 2 > 1 // condition n > 1 is true, as n equals to 2, 2 is greater than 1
-> result = fact(1) // it is fact(n - 1) call, as n equals to 2, 2 - 1 = 1, so we call fact(1)
-> result = result * 2 // "result = result * n" statement, n equals to 2, will be explained in backward expansion
-> return result // will be explained in backward expansion
-> result = result * 3 // "result = result * n" statement, n equals to 3, will be explained in backward expansion
-> return result // will be explained in backward expansion
Step 3, forward expansion, expand inner fact(1) call
fact(3)
-> 3 > 1 // condition n > 1 is true, as n equals to 3, 3 is greater than 1
-> result = fact(2) // it is a fact(n - 1) call, as n equals to 3, 3 - 1 = 2, so we call fact(2)
-> 2 > 1 // condition n > 1 is true, as n equals to 2, 2 is greater than 1
-> result = fact(1) // it is fact(n - 1) call, as n equals to 2, 2 - 1 = 1, so we call fact(1)
-> 1 > 1 // condition n > 1 is false, as n equals to 1, 1 is not greater than 1
-> return 1 // here we start backward expansion, fact(1) returns 1
-> result = result * 2 // "result = result * n" statement, n equals to 2, will be explained in backward expansion
-> return result // will be explained in backward expansion
-> result = result * 3 // "result = result * n" statement, n equals to 3, will be explained in backward expansion
-> return result // will be explained in backward expansion
Step 4, backward expansion, gather result from inner fact(1) call
fact(3)
-> 3 > 1 // condition n > 1 is true, as n equals to 3, 3 is greater than 1
-> result = fact(2) // it is a fact(n - 1) call, as n equals to 3, 3 - 1 = 2, so we call fact(2)
-> 2 > 1 // condition n > 1 is true, as n equals to 2, 2 is greater than 1
-> result = fact(1) // fact(1) call returned 1, result equals to 1
-> 1 > 1 // condition n > 1 is false, as n equals to 1, 1 is not greater than 1
-> return 1 // fact(1) returns 1
-> result = result * 2 // as result equals to 1 from fact(1) assignment, and we multiply it by 2, so result = 2
-> return result // fact(2) returns 2
-> result = result * 3 // "result = result * n" statement, n equals to 3, will be explained in backward expansion
-> return result // will be explained in backward expansion
Step 5, backward expansion, gather result from inner fact(2) call
fact(3)
-> 3 > 1 // condition n > 1 is true, as n equals to 3, 3 is greater than 1
-> result = fact(2) // fact(2) call returned 2, result equals to 2
-> 2 > 1 // condition n > 1 is true, as n equals to 2, 2 is greater than 1
-> result = fact(1) // fact(1) call returned 1, result equals to 1
-> 1 > 1 // condition n > 1 is false, as n equals to 1, 1 is not greater than 1
-> return 1 // fact(1) returns 1
-> result = result * 2 // as result equals to 1 from fact(1) assignment, and we multiply it by 2, so result = 2
-> return result // fact(2) returns 2
-> result = result * 3 // as result equals to 2 from fact(2) assignment, and we multiply it by 3, so result = 6
-> return result // fact(3) returns result to outer method, result = 6
Recursion might get tricky when you try to explain that technique to someone else.
It feels like it is an obvious thing to you (when you're a programmer), but it makes no sense to person you explain it to.
Hopefully this article did not sound like "... to understand recursion you first have to understand recursion ...", haha.
