CSCD 326 Data Structures ICSCD 326 Data Structures IRecursionCSCD 326 Data Structures I1CSCD 326 Data Structures IRecursionProof by Induction• Introduction only -topic wi327• Prove: NΣΣΣΣNΣΣΣΣi = N ( N + 1 ) / 2i=1• Basis Step:–show true for trivial case •for N = 1 the sum is 1( 1 + 1 ) / 2 = 1Proof by Induction will be covered in detail in CS 2show true for trivial case - here N = 1for N = 1 the sum is 1( 1 + 1 ) / 2 = 1Proof by Induction• Inductive hypothesis:–statement is true for N = kInductive step:•Inductive step:–if true for N = k show true for N = k + 1k+1 kΣΣΣΣi = (k + 1)+ ΣΣΣΣ ii=1 i=1Proof by Inductionstatement is true for N = k3if true for N = k show true for N = k + 1Proof by Induction• Inductive step:k+1ΣΣΣΣi = (k + 1) + k(k + 1) / 2 = (k + 1) (k + 2) /2i=1 –so by induction the statement is true for all kProof by Inductioni = (k + 1) + k(k + 1) / 2 = (k + 1) (k + 2) /2so by induction the statement is true for all k4Recursion• Math definition:–a solution to a problem that is defined in terms of a simpler version of itself•Programming definition:–a function which calls itselfRecursiona solution to a problem that is defined in terms of a simpler version of itself5Programming definition:a function which calls itselfRecursion•Recursive definition of Sum of Integers:public static intSum ( int n ) {// assumes n is >= 1// assumes n is >= 1if( n == 1)return 1;elsereturn Sum( n - 1 ) + n;}RecursionRecursive definition of Sum of Integers:6Factorial :Mathematical Definition•Mathematical definition (recursive):1 if N=1 or N=0N! = N! = N * (N -1)! if N > 1Factorial :Mathematical DefinitionMathematical definition (recursive):1 if N=1 or N=071)! if N > 1Factorial:Recursive Method• Recursive method:public static intfactorial ( int n ) {int temp;System.out.println("Entering factorial: n = " + n);System.out.println("Entering factorial: n = " + n);if((n == 1)|| (n == 0))temp = 1;elsetemp = n * factorial(n-1);System.out.println("Leaving factorial: n = "+ n );return temp;}Call:System.out.println("Factorial(4):" + factorial(4)); Factorial:Recursive MethodSystem.out.println("Entering factorial: n = " + n);8System.out.println("Entering factorial: n = " + n);System.out.println("Leaving factorial: n = "+ n );System.out.println("Factorial(4):" + factorial(4));Stack Frames • System Stack –used to control which function is currently active and to reverse the order of function calls when returning.returning.• Stack Frame–a variable size piece of memory that is pushed onto the system stack each time a function call is made. Stack Frames used to control which function is currently active and to reverse the order of function calls when 9a variable size piece of memory that is pushed onto the system stack each time a function call is made.Stack Frames • Stack Frame contains:•space for all local (automatic) variables• the return address -the place in the program to which execution will return when this function endsthe return value from the function•the return value from the function•all parameters for a funcvalues copied in–The stack frame on top of the stack always represents the function being executed at any point in time -only the stack frame on accessible at any time.Stack Frames space for all local (automatic) variablesthe place in the program to which execution will return when this function endsthe return value from the function10the return value from the functionnction (with actual parameter The stack frame on top of the stack always represents the function being executed at any point only the stack frame on top of the stack isFactorial TraceRet AddrN = 1 Ret Value : 212Ret AddrN = 2 2N = 2 Ret Value : Ret AddrN = 3 2Ret Value : Ret AddrN = 4 1Ret Value : 2624Factorial TraceEntering factorial N = 4 Entering factorial N = 3 Entering factorial N = 211Entering factorial N = 1Leaving factorial N = 1 Leaving factorial N = 2 Leaving factorial N = 3 Leaving factorial N = 4Rules of Recursion• Always include a terminal caserequire recursion to calculate•Each recursive call should •Each recursive call should the terminal case•Assume each recursive call works when designing a recursive algorithmRules of Recursionterminal casewhich does not require recursion to calculateEach recursive call should progresstoward 12Each recursive call should progresstoward Assume each recursive call works when designing a recursive algorithmRecursive Array Printingpublic class ArrayPrintDriver {public static voidprintem( int[ ] array, int n, int last ) {if(n <= last){System.out.println( array[n]);printem(array, n + 1, last);printem(array, n + 1, last);}}public static void main( String args[] ) {int[] values = new int[5];for(int i = 0; i < 5 ; i++)values[i] = i+1;printem(values, 0, 4);}1Recursive Array Printingprintem( int[ ] array, int n, int last ) {System.out.println( array[n]);13public static void main( String args[] ) {2Array Printing TraceRet Addrlast = 4 2array = valuesRet Addrlast = 4 n = 42array = valuesRet Addrlast = 4 n = 01array = valuesRet Addrlast = 4 n = 12array = valuesRet Addrlast = 4 n = 22array = valueslast = 4 n = 3array = valuesArray Printing Tracee12 3array = valuesarray = values14345 array = valuesarray = valuesarray = valuesarray = valuesMultiple Recursion• Fibonacci Sequence:0 1 1 2 3 5 8 13 21 44–each number in sequence is the sum of the previous two numbers (except the first two)Fibonacci number 0 = –Fibonacci number 0 = 1–all other Fibonacci numbers are defined as the sum of the previous two•Multiple Recursion0 1 1 2 3 5 8 13 21 44each number in sequence is the sum of the previous two numbers (except the first two) = 0 Fibonacci number 1 = 15 = 0 Fibonacci number 1 = all other Fibonacci numbers are defined as the sum of the previous twoMultiple Recursionpublic static intfib ( int n ) { if ( n <= 1)return n;elsereturn Fib( n -1) + Fib( n -2 );return Fib( n -1) + Fib( n -2 );}•Problem: multiple calls are made to calculate the same Fibonacci numberMultiple Recursion16Problem: multiple calls are made to calculate the same Fibonacci numberProblems with Recursion•Memory (stack) exhaustion: –if many stack frames are pushed space for stackspace for stack–if each call allocates much memory automatically or dynamically possible• Time:–each recursive call requires time to set up a new stack frame, copy in actual parameter values and transfer