Recursion in C programming ppt

recursion ppt presentation in c and algorithm for factorial of a number using recursion and advantages and disadvantages of recursion in c
OscarTucker Profile Pic
OscarTucker,Singapore,Professional
Published Date:19-07-2017
Your Website URL(Optional)
Comment
2.3 Recursion Introduction to Programming in Java: An Interdisciplinary Approach · Robert Sedgewick and Kevin Wayne · Copyright © 2002–2010 · 9/14/11 10:07 AM Overview What is recursion? When one function calls itself directly or indirectly. Why learn recursion?   New mode of thinking.   Powerful programming paradigm. Many computations are naturally self-referential.   Mergesort, FFT, gcd, depth-first search.   Linked data structures.   A folder contains files and other folders. Closely related to mathematical induction. Reproductive Parts M. C. Escher, 1948 2 Greatest Common Divisor Gcd. Find largest integer that evenly divides into p and q. Ex. gcd(4032, 1272) = 24. 6 2 1 4032 = 2 × 3 × 7 3 1 1 1272 = 2 × 3 × 53 3 1 gcd = 2 × 3 = 24 Applications.   Simplify fractions: 1272/4032 = 53/168.   RSA cryptosystem. 3 Greatest Common Divisor Gcd. Find largest integer d that evenly divides into p and q. Euclid's algorithm. Euclid 300 BCE ⎧ base case p if q = 0 gcd(p, q) =⎨ gcd(q, p % q) otherwise reduction step, ⎩ converges to base case € gcd(4032, 1272) = gcd(1272, 216) = gcd(216, 192) = gcd(192, 24) 4032 = 3 × 1272 + 216 = gcd(24, 0) = 24. 4 Greatest Common Divisor Gcd. Find largest integer d that evenly divides into p and q. ⎧ base case p if q = 0 gcd(p, q) =⎨ reduction step, gcd(q, p % q) otherwise ⎩ converges to base case € p q q p % q x x x x x x x x gcd p = 8x q = 3x gcd(p, q) = x 5 Greatest Common Divisor Gcd. Find largest integer d that evenly divides into p and q. ⎧ base case p if q = 0 gcd(p, q) =⎨ reduction step, gcd(q, p % q) otherwise ⎩ converges to base case € Java implementation. public static int gcd(int p, int q) if (q == 0) return p; base case else return gcd(q, p % q); reduction step 6 Recursive Graphics 9 Htree H-tree of order n. and half the size   Draw an H.   Recursively draw 4 H-trees of order n-1, one connected to each tip. tip size order 3 order 1 order 2 10 Htree in Java public class Htree public static void draw(int n, double sz, double x, double y) if (n == 0) return; double x0 = x - sz/2, x1 = x + sz/2; double y0 = y - sz/2, y1 = y + sz/2; draw the H, centered on (x, y) StdDraw.line(x0, y, x1, y); StdDraw.line(x0, y0, x0, y1); StdDraw.line(x1, y0, x1, y1); recursively draw 4 half-size Hs draw(n-1, sz/2, x0, y0); draw(n-1, sz/2, x0, y1); draw(n-1, sz/2, x1, y0); draw(n-1, sz/2, x1, y1); public static void main(String args) int n = Integer.parseInt(args0); draw(n, .5, .5, .5); 11 Animated H-tree Animated H-tree. Pause for 1 second after drawing each H. 20% 40% 60% 80% 100% 12 Towers of Hanoi http://en.wikipedia.org/wiki/Image:Hanoiklein.jpg Towers of Hanoi Move all the discs from the leftmost peg to the rightmost one.   Only one disc may be moved at a time.   A disc can be placed either on empty peg or on top of a larger disc. start finish Towers of Hanoi demo Edouard Lucas (1883) 14 Towers of Hanoi Legend Q. Is world going to end (according to legend)?   64 golden discs on 3 diamond pegs.   World ends when certain group of monks accomplish task. Q. Will computer algorithms help? 15 Towers of Hanoi: Recursive Solution Move n-1 smallest discs right. Move largest disc left. cyclic wrap-around Move n-1 smallest discs right. 16 Towers of Hanoi: Recursive Solution public class TowersOfHanoi public static void moves(int n, boolean left) if (n == 0) return; moves(n-1, left); if (left) System.out.println(n + " left"); else System.out.println(n + " right"); moves(n-1, left); public static void main(String args) int N = Integer.parseInt(args0); moves(N, true); moves(n, true) : move discs 1 to n one pole to the left moves(n, false): move discs 1 to n one pole to the right smallest disc 17 Towers of Hanoi: Recursive Solution % java TowersOfHanoi 4 % java TowersOfHanoi 3 1 right 1 left 2 left 2 right 1 right 1 left 3 right 3 left 1 right 1 left 2 left 2 right 1 right 1 left 4 left 1 right 2 left 1 right 3 right every other move is smallest disc 1 right 2 left 1 right subdivisions of ruler 18 Towers of Hanoi: Recursion Tree n, left 3, true 1 14 28 15 2, false 2, false 8 16 21 2 7 13 27 22 1, true 1, true 1, true 1, true 3 4 6 5 9 17 18 10 11 12 19 20 23 24 25 26 1 left 2 right 1 left 3 left 1 left 2 right 1 left 19 Towers of Hanoi: Properties of Solution Remarkable properties of recursive solution. n   Takes 2 - 1 moves to solve n disc problem.   Sequence of discs is same as subdivisions of ruler.   Every other move involves smallest disc. Recursive algorithm yields non-recursive solution   Alternate between two moves: to left if n is odd –  move smallest disc to right if n is even –  make only legal move not involving smallest disc Recursive algorithm may reveal fate of world.   Takes 585 billion years for n = 64 (at rate of 1 disc per second).   Reassuring fact: any solution takes at least this long 20 Divide-and-Conquer Divide-and-conquer paradigm.   Break up problem into smaller subproblems of same structure.   Solve subproblems recursively using same method.   Combine results to produce solution to original problem. Divide et impera. Veni, vidi, vici. - Julius Caesar Many important problems succumb to divide-and-conquer.   FFT for signal processing.   Parsers for programming languages.   Multigrid methods for solving PDEs.   Quicksort and mergesort for sorting.   Hilbert curve for domain decomposition.   Quad-tree for efficient N-body simulation.   Midpoint displacement method for fractional Brownian motion. 21