Advanced Programming Language Concepts: Recursion

Download as pptx, pdf, or txt
Download as pptx, pdf, or txt
You are on page 1of 20

Advanced Programming Language

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

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 2 of 20


Learning Outcomes

At the end of the lecture you should be able


to
• Understand the recursion technique
• Implement recursive lambda for a given
problem

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 3 of 20


Key Terms you must be able to use

If you have mastered this topic, you should be able to use


the following terms correctly in your lab assignments and
exams:
• Write recursion/recursive lambda for the given
problem

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 4 of 20


What is Recursion?
• Recursion is a technique that allows us to break
down a problem into smaller pieces.
• This technique allows us to remove some local
side effects.
• There are two main requirements of a recursive
function.
– A Stop Condition – the function returns a value when a
certain condition is satisfied, without a further recursive
call
– The Recursive Call – the function calls itself with
an input which is a step closer to the stop condition

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 5 of 20


Code sample using iteration
// PROBLEM: iterate each number of given n to find out the sum of them
// impact: difficult to read and complicated
static int sum_by_iteration(int n) {
int sum = 0;
if (n > 0) {
for (int i = 0; i <= n; i++) {
sum += i;
}
return sum;
} else {
return -1;
}
}

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 6 of 20


Code sample using recursion
// impact: clear code and readable
static int sum_by_recursion(int n) {
if (n > 0) {
return n + sum_by_recursion(n - 1); // recursive call
}
return n; // stop condition
}

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 7 of 20


Head recursion

• The first technique that we are going to use


is called head recursion.
• This does not introduce any side effects.
• Given the method sum_by_recursion(n).

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 8 of 20


Head recursion

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 );
}

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 10 of 20


Tail recursion

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

// Find the factorial number using recursion


static final int factorial(int n) {
// stop condition
if (n == 0) {
return 1;
}
return n * factorial(n - 1); // recursive call
}

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 12 of 20


Quick and Review

Rewrite the following code using recursion technique.

static void nLines(int n) {


for (int i = 0; i < n; i++) {
System.out.println(i);
}
}

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 13 of 20


Recursive Lambda

// Find the factorial number using recursion


static final int factorial(int n) {
// stop condition
if (n == 0) {
return 1;
}
return n * factorial(n - 1); // recursive call
}

static final UnaryOperator<Integer> fac = n -> n == 0


?1
: n * Demo.fac.apply(n - 1);

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 14 of 20


Recursion or Iteration?
Point Recursion Iteration
Implementation Function call itself With loops
Simplification Clear and readable code Harder to understand
Memory consumption / More memory needed as Better consumption and
performance stack memory increases performance
when recursive call
performs
Problem solving Not all problems has Any recursive problem
recursive solution can be solved iteratively
Repetition Recursion terminates Iteration terminates
when a base case is when the loop
recognized continuation
Code size Recursion decreases the Iterative code tends to
size of code be bigger or longer in
size

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 15 of 20


Recursion or Iteration?

• Making the right choice between head recursion,


tail recursion and an iterative approach all
depend on the specific problem and situation.

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 16 of 20


Quick and Review

Rewrite the following code using recursive lambda.


static long pw(int base, int expo) {
long result = 1;
for (int i = 0; i < expo; i++) {
result *= base;
} static long power(int base, int expo) {
return result; if ( expo != 0 ) {
} return power(base, expo-1) * base;
}else {
return 1;
}
}
CT006-3-3-Advanced Programming Language Concepts Recursion Slide 17 of 20
Summary of Main Teaching Points

• Recursion technique
– Recursion basic
– Recursion vs. iteration with code samples
– Head recursion and tail recursion
– Recursive lambda
– Difference between recursion and iteration

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 18 of 20


Question and Answer Session

Q&A

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 19 of 20


What we will cover next

• Parametric polymorphism:
– Generics

CT006-3-3-Advanced Programming Language Concepts Recursion Slide 20 of 20

You might also like