Recursion
Inst. Nguyễn Minh Huy
Advanced Programming - Nguyễn Minh Huy 1
Contents
Introduction.
Classifications.
Applications.
Advanced Programming - Nguyễn Minh Huy 2
Contents
Introduction.
Classifications.
Applications.
Advanced Programming - Nguyễn Minh Huy 3
Introduction
Basic concepts:
What is recursion?
Look up slides #5: “What is recursion?”!!
Recursion is…
Defining a problem by itself!!
For example:
Factorial: n! = n * (n – 1)!.
Fibonacci: f(n) = f(n – 1) + f(n – 2).
Natural number: n is natural n – 1 is also natural.
Ancestor: A’s ancestors are also A’s parents’ ancestors.
Advanced Programming - Nguyễn Minh Huy 4
Introduction
Basic concepts:
Meaningful recursion:
Base case: explicit definition.
Recursive case: reduce problem to simpler cases.
- 0! = 1
- n! = n * (n – 1)!.
- f(0) = 0
- f(1) = 1
- f(n) = f(n – 1) + f(n – 2).
- 0 is smallest natural number
- n is natural n – 1 is natural.
- Nearest A’s ancestors are A’s parents.
- A’s ancestors are also A’s parents’ ancestors.
Advanced Programming - Nguyễn Minh Huy 5
Introduction
Recursion in programming:
Recursive function:
Has a call to itself in function body.
// Direct call. // Indirect call.
void func() void func1()
{ {
// … // …
func(); func2();
// … // …
} }
void func2()
{
// …
func1();
// …
}
Advanced Programming - Nguyễn Minh Huy 6
Introduction
Recursion in programming:
Meaningful recursive function:
<Return type> <Function name>( [Arguments] )
{
if (<base case>)
// solve explicit.
else
// call to itself with simpler arguments.
}
int factorial( int n ) int fibo( int n )
{ {
if (n == 0) if (n == 0)
return 1; return 0;
return n * factorial(n – 1); if (n == 1)
} return 1;
return fibo(n – 1) + fibo(n – 2);
}
Advanced Programming - Nguyễn Minh Huy 7
Introduction
Recursion in programming:
Recursive struct:
struct <Struct name>
{
// …
<Struct name> <member>;
// …
};
struct Person struct Employee
{ {
char *name; char *name;
int age; char *address;
Person *father; double salary;
Person *mother; Employee *manager;
}; };
Advanced Programming - Nguyễn Minh Huy 8
Introduction
Recursion in other fields:
Graphics
Nature
Graphics
Marketing
Advanced Programming - Nguyễn Minh Huy 9
Contents
Introduction.
Classifications.
Applications.
Advanced Programming - Nguyễn Minh Huy 10
Classifications
Types of recursion:
Linear recursion:
Function body has ONE call to itself.
int factorial( int n )
{ factorial(n)
if (n == 0)
return 1; factorial(n-1)
return n * factorial( n – 1 );
factorial(n-2)
}
Complexity: O(n). …
Advanced Programming - Nguyễn Minh Huy 11
Classifications
Types of recursion:
Binary recursion:
Function body has TWO calls to itself.
int fibo(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
return fibo(n – 1) + fibo(n – 1);
} fibo(n)
Complexity: O(2n).
fibo(n-1) fibo(n-2)
fibo(n-2) fibo(n-3) fibo(n-3) fibo(n-4)
… … … …
Advanced Programming - Nguyễn Minh Huy 12
Classifications
Types of recursion:
Mutual recursion:
Function f1 has a call to f2.
Function f2 has a call to f1.
bool checkEven(int n) bool checkOdd(int n)
{ {
if (n == 0) if (n == 0)
return true; return false;
return checkOdd(n – 1); return checkEven(n – 1);
} }
Advanced Programming - Nguyễn Minh Huy 13
Classifications
Types of recursion:
Non-linear recursion:
Function body has call to itself inside a loop.
Calculate: S(1) = 1
S(n) = S(1) + S(2) + … + S(n – 1).
int calculate( int n )
S(n)
{
if (n == 1)
return 1; S(1) S(2) S(3) … S(n-1)
int S = 0; …
for (int i = 1; i <= n - 1; i++) S(1) S(1) S(2)
S += calculate( i ); …
return S;
}
Complexity: O(n!).
Advanced Programming - Nguyễn Minh Huy 14
Contents
Introduction.
Classifications.
Applications.
Advanced Programming - Nguyễn Minh Huy 15
Applications
Problem solving:
Non-recursive solution:
Direct solution.
Find steps to the problem.
Recrusive solution:
Indirect solution.
Move the problem to us!
Re-define the problem recursively:
Step 1: solve base case directly.
Step 2: reduce the problem to simpler cases.
Regression formula (reduce by formula).
Divide and conquer (reduce by splitting).
Advanced Programming - Nguyễn Minh Huy 16
Applications
Regression formula:
Calculate element An in series { A }:
Regression formula:
Step 1: find direct way to calculate A0.
Step 2: find way to calculate An from An-1.
Advanced Programming - Nguyễn Minh Huy 17
Applications
Regression formula:
Example 1:
Bacteria double in every min. int calcBac( int n )
1 bacteria at first. {
if ( n == 0)
How many after 20 mins? return 1;
V( 0 ) = 1 return 2 * calcBac( n – 1 );
V( n ) = 2 * V( n – 1 ). }
Example 2:
Saving rate: 7% / year. int calcMoney( int k )
{
Deposit 1 million.
if ( k == 0)
How much after 20 years? return 1;
T( 0 ) = 1 return 1.07 * calcMoney(k -1);
T( n ) = T( n – 1 ) + 0.07 * T( n – 1 ) }
= 1.07 T( n – 1 ).
Advanced Programming - Nguyễn Minh Huy 18
Applications
Divide-conquer:
How to eat a cow?
Split into small parts.
How small is enough?
Divide-conquer structure:
Conquer ( P )
{
if ( P is small enough )
Solve P directly;
else
Split P P1, P2;
Conquer ( P1 );
Conquer ( P2 );
Join results;
}
Advanced Programming - Nguyễn Minh Huy 19
Applications
Divide-conquer:
Example: array b/w segment left & right
Given array of integers. int countNegs( int *a, int l, int r )
Count negative numbers. {
if (l == r)
- Mảng đủ nhỏ (1 phần tử): return a[ r ] < 0 ? 1 : 0;
+ Kiểm tra âm phần tử duy nhất.
- Mảng nhiều phần tử: int mid = ( l + r ) / 2;
+ Chia mảng làm 2 phần. int c1 = countNegs(a, l, mid);
+ Đếm âm từng phần. int c2 = countNegs(a, mid+1, r);
+ Cộng kết quả lại.
return c1 + c2;
}
Advanced Programming - Nguyễn Minh Huy 20
Summary
Introduction:
Recursion is define a problem by using itself.
Meaningful recursion:
Base case: explicit definition.
Recursive case: reduce problem to simpler cases.
Recursive function: has a call to itself.
Recursive struct: has itself as member.
Classifications:
Types: linear, binary, mutal, non-linear.
Applications:
Techniques: regression formula, divide-conquer.
Advanced Programming - Nguyễn Minh Huy 21
Practice
Practice 5.1:
Write C functions to do the followings:
a) S(n) = 1 + 2 + … + n.
b) T(n) = xn.
c) S(n) = 1/1 – 1/2 + 1/3 – 1/4 + … (+/-) 1/n.
c) Base case: n = 1 return 1
Recursion: S(n) = S(n-1) + (-1)^n /n
Advanced Programming - Nguyễn Minh Huy 22
Practice
Practice 5.2:
Given array of integers, write C recursive functions to do the followings:
a) Sum all even numbers in array.
b) Find max number in array.
c) Find position of x in array. !!
pos1 = findXpos(a,x,L,mid);
if (pos1 != -1) return pos1;
return findXpos(a,x,mid+1,R);
Advanced Programming - Nguyễn Minh Huy 23
Practice
Practice 5.3:
By using struct Person in this slides, write C recursive function to do
the followings:
a) Count all ancestors of a given person.
b) Count all ancestors from the mother-side of a given person.
Advanced Programming - Nguyễn Minh Huy 24
