Slide 1RecursionRecursion (cont.)Recursion vs. IterationExample Using Recursion: FactorialExample Using Recursion: The Fibonacci SeriesSlide 7Recursion vs. IterationSlide 9AcknowledgementsDale RobertsCSCI 230Functions RecursionDepartment of Computer and Information Science,School of Science, IUPUIDale Roberts, LecturerDale Roberts, [email protected]@cs.iupui.eduDale RobertsRecursionRecursionRecursive functions A function can invoke any other function; A function can invoke any other function; “ Can a function invoke itself?”“ Can a function invoke itself?”Functions that call themselves either directly or indirectly (through Functions that call themselves either directly or indirectly (through another function) is called a another function) is called a recursive functionrecursive function..If a function is called with a simple case, the function actually knows If a function is called with a simple case, the function actually knows how to solve the simplest case(s) - “how to solve the simplest case(s) - “base casebase case” and simply returns a ” and simply returns a result.result.If a function is called with a complex case - “If a function is called with a complex case - “recursive caserecursive case” , it invokes ” , it invokes itself again with simpler actual parameters.itself again with simpler actual parameters.1.1.must resembles original problem but slightly simplifiedmust resembles original problem but slightly simplified2.2.function will call itself (recursion step or recursive call) to solve slightly function will call itself (recursion step or recursive call) to solve slightly simplified problemsimplified problem3.3.process continues until the last recursive call is with the base caseprocess continues until the last recursive call is with the base case4.4.that call returns the result of the base casethat call returns the result of the base case5.5.return to previous calling functionsreturn to previous calling functions6.6.finally reaches main.c.finally reaches main.c.Eventually base case gets solvedEventually base case gets solvedGets plugged in, works its way up and solves whole problemGets plugged in, works its way up and solves whole problemDale RobertsRecursion Recursion (cont.)(cont.)ExampleExample: Compute : Compute x x yy for for x x > 0> 0 & & y y > 0> 0x y = x * x * x * … * xbase case: x1 = x x y = x1 * ( x * x * … * x)= x1 * ( x1 * ( x * x * … * x ))= x1 * ( x1 * ( x1 * ( x * x * … * x )))= x1 * x y-1 ex. x 4 = x1 * ( x1 * ( x1 * ( x1 )))Fundamental rules of recursionFundamental rules of recursion1.) Base cases1.) Base cases2.) Making progress through recursion2.) Making progress through recursion3.) Design rule: assuming all recursive call work (details hidden)3.) Design rule: assuming all recursive call work (details hidden)4.) Always specify the base case; otherwise, indefinite recursive will 4.) Always specify the base case; otherwise, indefinite recursive will occur and cause “occur and cause “stack-overflowstack-overflow” error.” error.x1x1x1x1***x1x3x2x1x2x3x4x45515151***515352x1x212562554255y timesDale RobertsRecursion: #include <stdio.h>int x_pow_y(int, int);main(){ printf(“enter x and y: \n”); scanf(“%d, %d”, x, y); z = x_pow_y(x,y); printf(“z: %d\n”, z);}x_pow_y(int a, int b){ if (b==1) return a; else return (a * x_pow_y(a, b-1)) }Recursion vs. IterationRecursion vs. IterationIteration: x_pow_y = 1;for (i = y; i >=1; i--) x_pow_y*=x;If x = 5, y = 4x_pow_y = 1, x = 5, y = 4, i = 4;1.) x_pow_y = 5*1 = 5, i = 3;2.) x_pow_y = 5*5 = 25, i = 2;3.) x_pow_y = 25*5 = 125, i = 1;4.) x_pow_y = 125*5 = 625, i = 0;…x=5;y=4;x_pow_y(5,4);…is (4==1)?no…is (3==1)?no…is (2==1)?no…is (1==1)?yesreturn 5x_pow_y(5,4) x_pow_y(5,3) x_pow_y(5,2) x_pow_y(5,1)Base Casemain525125625Dale RobertsExample Using Recursion: FactorialExample Using Recursion: FactorialExample: factorials: 5! = 5 * 4 * 3 * 2 * 1Notice thatNotice that5! = 5 * 4!5! = 5 * 4!4! = 4 * 3! 4! = 4 * 3! ……Can compute factorials recursively Can compute factorials recursively Solve base case (Solve base case (1! = 0! = 11! = 0! = 1) then plug in) then plug in2! = 2 * 1! = 2 * 1 = 2;2! = 2 * 1! = 2 * 1 = 2;3! = 3 * 2! = 3 * 2 = 6;3! = 3 * 2! = 3 * 2 = 6;long factorial(int n)long factorial(int n){{if (n <= 1)if (n <= 1)return 1;return 1;elseelsereturn n * factorial(n-1);return n * factorial(n-1);}} 00 )!1(1!nnnnnDale RobertsExample Using Recursion: The Fibonacci SeriesExample Using Recursion: The Fibonacci SeriesExample: Fibonacci series:FFk k = = FFk-1 k-1 + + FFk-2k-2,, FF0 0 = 1, = 1, FF11 = 1 ex: 0, = 1 ex: 0, 1, 1, 2, 3, 5, 8…1, 1, 2, 3, 5, 8…Each number is the sum of the previous two Each number is the sum of the previous two Can be solved recursively:Can be solved recursively:fib( n ) = fib( n - 1 ) + fib( n – 2 )fib( n ) = fib( n - 1 ) + fib( n – 2 )Set of recursive calls to function Set of recursive calls to function fibonaccifibonacciCode for the Code for the fibonaccifibonacci function functionlong fibonacci(long n)long fibonacci(long n){{ if (n <= 1)if (n <= 1) return n;return n;else;else;return return fibonaccifibonacci(n-1) + (n-1) + fibonaccifibonacci(n-2);(n-2);}}f( 3 )f( 1 )f( 2 )f( 1 ) f( 0 ) return 1return 1 return 0return++returnDale Roberts1 /* Fig. 5.15: fig05_15.c2 Recursive fibonacci function */3 #include <stdio.h>45 long fibonacci( long );67 int main()8 {9 long result, number;1011 printf( "Enter an integer: " );12 scanf( "%ld", &number );13 result = fibonacci( number );14 printf( "Fibonacci( %ld ) = %ld\n", number, result );15 return 0;16 }1718 /* Recursive definition of function fibonacci */19 long fibonacci( long n )20 {21 if ( n == 0 || n == 1 )22 return n;23 else24 return fibonacci( n - 1 ) + fibonacci( n - 2 );25 }Enter an integer: 0Fibonacci(0) = 0 Enter an integer: 1Fibonacci(1) = 1Enter an integer: 2Fibonacci(2) = 1 Enter an integer: 3Fibonacci(3) = 2 Enter an integer: 4Fibonacci(4) = 3 Enter an integer: 5Fibonacci(5) = 5 Enter an integer: 6Fibonacci(6) = 8 Enter an integer: 10Fibonacci(10) = 55 Enter an integer: 20Fibonacci(20) = 6765 Enter an integer: 30Fibonacci(30) = 832040 Enter an integer: 35Fibonacci(35) = 92274651. Function prototype2. Declare variables3. Input an integer4. Call function fibonacci5. Output results.6. Define fibonacci recursivelyDale