Report

Algorithmic Recursion Recursion Alongside the algorithm, recursion is one of the most important and fundamental concepts in computer science as well as many areas of mathematics. Recursive solutions to problems tend be simple eloquent concise Definition: A recursive algorithm is one that calls or refers to itself within its algorithmic body. Like other iterative constructs such as the FOR loop and the WHILE loop a particular condition needs to be met that prevents the algorithm from executing indefinitely. In recursive algorithms this condition is called the base or end case. The base case usually represents a lower bound on the number of times the recursive algorithm will call itself. A recursive algorithm normally expects INPUT parameters and returns a single RETURN value. Each subsequent recursive call of the algorithm should pass INPUT parameters that are closer to the base case Recursion Example The Fibonacci Sequence is powerful integer number sequence which has many applications in mathematics, computer science and even nature ( the arrangements of flower petals, spirals in pine cones all follow the Fibonacci sequence ). The Fibonacci sequence is defined as follows: Fib(n) = Fib(n-1) + Fib(n-2) where N > 1 Fib(0) = Fib(1) = 1 The first ten terms in the sequence are 1,1,2,3,5,8,13,21,33,54 Fibonacci Sequence Module {Module to compute the nth term in the Fibonacci sequence} Module Name: Fib Input: n Output: nth term in sequence Process: IF (n<=1) {base condition} THEN RETURN 1 ELSE {recursive call} RETURN Fib(n-1) + Fib(n-2) ENDIF Compute fib_5 Fib(5) Fib(5) Fib(4) Fib(3) + Fib(2) + Fib(1) Fib(2) + Fib(3) Fib(2) Fib(1) + Fib(0) + Fib(1) Fib(1) + Fib(0) Fib(1) + Fib(0) = 1+1+1+1+1+1+1+1 = 8 When looking at recursive solution to a problem we try to identify two main characteristics: 1. Can we identify a solution where the solution is based upon solving a simpler problem of itself each time. 2. Can we identify a base case where the simpler solutions stop. Most recursive modules (functions) take the following form: IF ( base case ) THEN RETURN base_case solution ELSE RETURN recursive solution ENDIF Example: Evaluate xy recursively Firstly we need to answer the two questions. (1) (2) Answer yes xy = x * xy-1 Answer yes x0 = 1 xy Recursive Module { Module to compute xy recursively } Module Name: power Input: x,y Output: x to the power of y Process: IF (y=0) {base condition} THEN RETURN 1 ELSE {recursive call} RETURN x*power(x,y-1) ENDIF Example: Triangular values Design an iterative algorithm to read a number from a user and print it’s triangular value. ( if the number 5 is input its triangular value is 5+4+3+2+1 = 15 ) {Print triangular value of input number} PRINT “Enter a number “ READ number triangular_value 0 FOR ( value FROM 1 TO number ) triangular_value triangular_value + value ENDFOR PRINT triangular_value Now design a recursive module to solve the same problem. Step 1 – Answer questions (1) Yes - tri(n) = n + tri(n-1) (2) Yes - n = 1 Algorithm: Module Name: tri Inputs: n Outputs: triangular value of n Process: IF ( n = 1 ) THEN /* Base Case */ RETURN 1 ELSE /* Recursive solution */ RETURN n + tri(n-1) ENDIF