C Programming Functions Recursion
Examples of Recursive Functions
GCD Using Euclids method (m n > 0): GCD(m, n) = n, if m%n = 0 GCD(n, m%n), otherwise
Dijkstras method (assuming m > n > 0) GCD(m, n) is same as GCD(m n, n): n, if m = n GCD(m, n) = GCD(m n, n), if m > n GCD(m, n m), if n > m
R. K. Ghosh (IIT-Kanpur) C Programming March 2, 2011 7/8
C Programming Functions Recursion
Examples of Recursive Functions
GCD: Euclids Method
#i n c l u d e < s t d i o . h> i n t GCD( i n t m, i n t n ) { i f ( (m % n ) == 0 ) return n ; r e t u r n GCD( n , m % n ) ; } i n t main ( ) { i n t m, n ; p r i n t f ( E n t e r m, n ) ; s c a n f ( %d %d , &m, &n ) ; i f (m < n ) p r i n t f ( GCD(%d , %d ) = %d\n , m, n , GCD( n , m) ) ; else p r i n t f ( GCD(%d , %d ) = %d\n , m, n , GCD(m, n ) ) ; }
R. K. Ghosh (IIT-Kanpur) C Programming March 2, 2011 7/8
C Programming Functions Recursion
Examples of Recursive Functions
GCD: Dijkstra Method
#i n c l u d e < s t d i o . h> i n t GCD( i n t m, i n t n ) { i f (m == n ) r e t u r n m; i f (m > n ) r e t u r n GCD(m , n ) ; n r e t u r n GCD(m, nm) ; } i n t main ( ) { i n t m, n ; p r i n t f ( E n t e r m and n : ) ; s c a n f ( %d %d , &m, &n ) ; p r i n t f ( GCD(%d , %d ) = %d\n , m, n , GCD(m, n ) ) ; }
R. K. Ghosh (IIT-Kanpur)
C Programming
March 2, 2011
7/8
C Programming Functions Recursion
Examples of Recursive Functions
Binomial Coecient 1, if r = 0 = 1, if n = r n1 r + n1 otherwise r1
n r
R. K. Ghosh (IIT-Kanpur)
C Programming
March 2, 2011
7/8
C Programming Functions Recursion
Examples of Recursive Functions
Binomial Coecient
#i n c l u d e < s t d i o . h> i n t binom ( i n t n , i n t r ) { i f ( r == 0 | | n == r ) return 1; r e t u r n binom ( n 1 , r ) + binom ( n 1 , r 1); } i n t main ( ) { int n , r ; p r i n t f ( Enter n , r : ) ; s c a n f ( %d %d , &n , &r ) ; p r i n t f ( binom(%d , %d ) = %d\n , n , r , binom ( n , r ) ) ; }
R. K. Ghosh (IIT-Kanpur)
C Programming
March 2, 2011
7/8
C Programming Functions Recursion
Examples of Recursive Functions
Pascals Triangle
i n t main ( ) { int i , j , n; p r i n t f ( Enter n : ) ; s c a n f ( %d , &n ) ; f o r ( i = 0 ; i < n ; i ++) { f o r ( j = 0 ; j <= i ; j ++) { p r i n t f ( %6d , binom ( i , j ) ) ; } p r i n t f ( \n ) ; } }
R. K. Ghosh (IIT-Kanpur)
C Programming
March 2, 2011
7/8
C Programming Functions Recursion
Examples of Recursive Functions
Tower of Hanoi
2
Two recursive problems of size n 1 to be solved.
B C
Base case is moving the disk with largest diameter. So, spec of tower(n, A, B, C):
If n = 1 then move disk n from A to C Else execute following steps:
1 2
B 3
tower(n-1, A, C, B), move disk n from A to C, tower(n-1, B, A, C)
R. K. Ghosh (IIT-Kanpur)
C Programming
March 2, 2011
7/8
C Programming Functions Recursion
Examples of Recursive Functions
Tower of Hanoi
#i n c l u d e < s t d i o . h> v o i d t o w e r ( i n t n , c h a r A , c h a r B , c h a r C) { i f ( n == 1 ) { p r i n t f ( Move d i s k 1 from %c t o %c \n , A , C ) ; return ; } t o w e r ( n 1 , A , C , B ) ; p r i n t f ( Move d i s k %d from %c t o %c \n , n , A , C ) ; t o w e r ( n 1 , B , A , C ) ; return ; } i n t main ( ) { int n; p r i n t f ( Enter n : ) ; s c a n f ( %d , &n ) ; t o w e r ( n , A , B , C ) ; }
R. K. Ghosh (IIT-Kanpur)
C Programming
March 2, 2011
7/8
C Programming Functions Recursion
Merge Sort
Merging
auxiliary array (double the size of A or B) smaller 0 1 smaller 2 3 smaller smaller comp 0 3 4 6 8 11 12 13 A 1 2 5 7 9 10 14 15 B 0 3 4 6 8 11 12 13 A comp 1 2 5 7 9 10 14 15 B 0 comp 3 4 6 8 11 12 13 A 1 2 5 7 9 10 14 15 B
March 2, 2011 8/8
comp 0 3 4 6 8 11 12 13 A 1 2 5 7 9 10 14 15 B
R. K. Ghosh (IIT-Kanpur)
C Programming
