1RecursionRecursion• Idea: Some problems can be brokendown into smaller versions of the sameproblem• Example: n!• 1*2*3*…*(n-1)*n• n*factorial of (n-1)Base Case• 5! = 5*4!• 4! = 4*3!• 3! = 3*2!• 2! = 1*1!• 1! = 1Base case – you always need a terminating condition to endFunction: factorialint factorial(int n) {if(n == 1)return 1;elsereturn (n*factorial(n-1));}Iterative Factorialint factorial(int n) {int i;int product = 1;for(i = n; i > 1; i--) {product = product * i;}return product;}Comparison• Why use iteration over recursion or viceversa?2Linear Recursion• At most 1 recursive call at each iteration– Example: Factorial• General algorithm– Test for base cases– Recurse• Make 1 recursive call• Should make progress toward the base case• Tail recursion– Recursive call is last operation– Can be easily converted to iterativeHigher-Order Recursion• Algorithm makes more than one recursivecall• Binary recursion– Halve the problem and make two recursivecalls– Example?• Multiple recursion– Algorithm makes many recursive calls– Example?Rules of Recursion1. Base cases. You must always have somebases cases, which can be solved withoutrecursion.2. Making progress. For the cases that are to besolved recursively, the recursive call mustalways be to a case that makes progresstoward a base case.3. Design rule. Assume that all the recursivecalls work.4. Compound interest rule. Never duplicate workby solving the same instance of a problem inseparate recursive calls.Exercises1. Implement and test a method that usestail recursion to convert an array ofintegers into their absolute values.Towers of Hanoi• Three pegs and a set of disks• Goal: move all disks from peg 1 to peg 3• Rules:– move 1 disk at a time– a larger disk cannot be placed on top of asmaller disk– all disks must be on some peg except thedisk in-transitExamples• Design a binary recursive method forfinding an element X in a sorted array A.• Design a recursive method for printing allpermutations of a given string.3Exercises1. Design a recursive program to produce the followingoutput:00 10 1 20 1 2 30 1 2 3 40 1 2 30 1 20
View Full Document