Advanced Programming Language Concepts: Recursion
Advanced Programming Language Concepts: Recursion
Advanced Programming Language Concepts: Recursion
Concepts
CT006-3-3-APLC and Version VD1
Recursion
Topic & Structure of the lesson
• Recursion technique
– Recursion basic
– Recursion vs. iteration with code samples
– Head recursion and tail recursion
– Recursive lambda
– Difference between recursion and iteration
Assume n = 5,
n>0? 15
5 + sum_by_recursion(5-1=4) 5+10
4 + sum_by_recursion(3) 4+6
3 + sum_by_recursion(2) 3+3
2 + sum_by_recursion(1) 2+1
1 + sum_by_recursion(0) 1+0
0
CT006-3-3-Advanced Programming Language Concepts Recursion Slide 9 of 20
Tail recursion
• tail-recursion when the recursive call is the last
thing that function executes. Otherwise, it's
known as head-recursion.
static int sum_by_tail(int curr, int n) {
if ( n <= 0 ) {
return curr + n;
}
return sum_by_tail( curr + n, n - 1 );
}
Assume curr = 0, n = 5,
n <= 0?
sum_by_tail(0+5, 5-1)
sum_by_tail(5+4, 4-1)
sum_by_tail(9+3, 3-1)
sum_by_tail(12+2, 2-1)
sum_by_tail(14+1, 1-1)
15 + 0
15
CT006-3-3-Advanced Programming Language Concepts Recursion Slide 11 of 20
Code sample for factorial number
• Recursion technique
– Recursion basic
– Recursion vs. iteration with code samples
– Head recursion and tail recursion
– Recursive lambda
– Difference between recursion and iteration
Q&A
• Parametric polymorphism:
– Generics