OO21090
Recursion Trees Recursionis a concept of defining a method that makes a call to itself
RecursionRecursion isaconceptofdefining a method that makesa call to itself
Recursion Trees Recursion is a concept of defining a method that makes a call to itself
FactorialExample:f(n)=n!=nx(n-1)×(n-2)×...×2×1Initialization:f(O)=1RecursiveCall:f(n)=nxf(n-1)andJava code:public static int recursiveFactorial(intn)if (n==0) return 1;elsereturnn*recursiveFactorial(n-1);1Trees
Factorial Example: f(n)=n!=n×(n-1)×(n-2)×.×2×1 Initialization: f(0)=1 Recursive Call: f(n)=n×f(n-1) and. Java code: public static int recursiveFactorial(int n) { if (n==0) return 1; else return n*recursiveFactorial(n-1); } Trees
Fibonacci sequenceCFibonaccisequence:f,1=0,1,1,2,3,5,8,13,21,34,55,..Initialization: f。=O, f,=1Recursive Call: f, = fn-1+fn-2 for n > 1.Java code:public staticint recursiveFibonacci(int n) [if (n==0) return 0;if (n==1) return 1;else return recursiveFibonacci(n-1)+recursiveFibonacci (n-2);1
L 1 6 Fibonacci sequence Fibonacci sequence: {fn } = 0,1,1,2,3,5,8,13,21,34,55,. Initialization: f0 = 0, f1 = 1 Recursive Call: fn = fn-1+fn-2 for n > 1. Java code: public static int recursiveFibonacci(int n) { if (n==0) return 0; if (n==1) return 1; else return recursiveFibonacci(n-1)+recursiveFibonacci (n-2); }
A=[4,3,6,2,5)LinearSumreturn 15+A[4]=20LinearSum(A,5)Algorithm LinearSum(A, n)return 13+A[3]=15Input: an integer array A of n elementsOutput: The sum of the n elementsLinearSum(A,4)if n=1 thenreturn 7+A[2]=13return A[0]LinearSum(A,3)return LinearSum(A, n-1)+A[n-1]return 4+A[1]=7The recursivemethod should alwaysLinearSum(A,2)possess-themethod terminates.return A[0]=4.Wedid it by setting:LinearSum(A,1)" if n=1 then return A[0]Thecompilerof anyhighlevel computerf(n)=A[n-1]+f(n-1) for n>0 and f(1)=A[0]languageuses a stack tohandlerecursive calls.Trees
LinearSum Trees LinearSum(A,5) LinearSum(A,4) LinearSum(A,3) LinearSum(A,2) LinearSum(A,1) Algorithm LinearSum(A, n) Input: an integer array A of n elements Output: The sum of the n elements if n=1 then return A[0] return LinearSum(A, n-1)+A[n-1] • The recursive method should always possess—the method terminates. • We did it by setting : • ” if n=1 then return A[0] ” return A[0]=4 return 4+A[1]=7 return 7+A[2]=13 return 13+A[3]=15 return 15+A[4]=20 A={4,3,6,2,5} The compiler of any high level computer language uses a stack to handle recursive calls. f(n)=A[n-1]+f(n-1) for n>0 and f(1)=A[0]