Mathematical Analysis of Non Recursive Algorithms

MaxElement
Finding the value of the largest element in the list of n numbers
MaxElement(A[1..n]) maxval A[1] for i 2 to n do if A[i] > maxval maxval A[i] return maxval

Complexity of Algorithm
The Loop is repeated n-1 times so

General Plan for Analyzing Time Efficiency of Nonrecursive Algorithms

1. Decide on a parameter(or parameters) indicating an inputs size. 2.Identify the algorithms basic operation.(As a rule, it is located in its innermost loop) 3.Check whether the number of times the basic operation is executed depends only on the size of an input. 4.Set up a sum expressing the number of times the algorithms basic operation is executed. 5.Using standard formulas and rules of sum manipulation, either find a closed form formula for the count or, at the very least, establish its order of growth.

UniqueElement
UniqueElement(A[1..n]) for i 1 to n-1 do for j i+1 to n do{ if A[i] = A[j] return false} return true

complexity

Binary digits in the binary representation of a positive decimal integer Algorithm Binary(n) { count 1 while n>1 { Count count+1 n [n/2] } return count}

Fibonacci series
Algorithm Fibonacci(n) { if n<1 Return n; Else F1 0, F2 1; For i 2 to n do { F F1+F2 F1 F2 F2 F }return F

 What is recursion?recursion When one function calls ITSELF directly or indirectly. Recursion means defining something, such as a function, in terms of itself
For example, let f(x) = x! We can define f(x) as f(x) = x * f(x-1)

Recursion outside Computer Science

Names
PHP : PHP Hypertext Preprocessor GNU : GNU is Not Unix

Mathematics
Definition of the set of non negative numbers N
0 is in N If n is in N, then n+1 is in N.

Images
Fractals

Fractals
A fractal is a pattern that uses recursion
The pattern itself repeats indefinitely

13

Fractals

14

Onion Model of Recursive Every Onion is either Naturals

Base Case : The core Recursive Case: A layer of skin around a smaller onion (which may be the core, or some deeper layer)

The value of an onion is the number of layers of skin beyond the core s(0) = 1 s(s(0)) = 2 s(s(s(0))) = 3

Meaning of recursion
To recur means to happen again. In computer science, we say that a subroutine (function or procedure) is recursive when it calls itself one or more times. We call the programming technique by using recursive subroutine(s) as recursion.

 The recursive function is

Recursive Function

a kind of function that calls itself, or a function that is part of a cycle in the sequence of function calls.

f1

f1

f2

fn

 One or more simple cases of the problem have a straightforward solution. The other cases can be redefined in terms of problems that are closer to the simple cases. The problem can be reduced entirely to simple cases by calling the recursive function.
If this is a simple case solve it else redefine the problem using recursion

Problems Suitable for Recursive Functions

Splitting a Problem into Smaller Problems

Assume that the problem of size 1 can be solved easily (i.e., the simple case). We can recursively split the problem into a problem of size 1 and another problem of size n1.

General Form of Recursive methods Solve(Problem)

{ if (Problem is minimal/not decomposable: a base case) solve Problem directly; i.e., without recursion else { (1) Decompose Problem into one or more similar, strictly smaller subproblems: SP1, SP2, ... , SPN (2) Recursively call Solve (this method) on each subproblem: Solve(SP1), Solve(SP2),..., Solve(SPN) (3) Combine the solutions to these subproblems into a solution that solves the original Problem } }

Defining sets via recursion

Same two parts:
Base case (or basis step) Recursive step

Example: the set of positive integers

Basis step: 1 S Recursive step: if x S, then x+1 S

Defining sets via recursion

recursive definitions for:
a)

The set of odd positive integers

1S If x S, then x+2 S

b)

The set of positive integer powers of 3

3S If x S, then 3*x S

Recurrence in mathematical functions

Factorial

n! _ ( n 1)! =n
n

Permutation

Pr _ nn 1 Pr =

Combination
n

Cr _ ( n / r )n 1 Cr =

Pascal relationship
n

Cr = n 1 Cr 1 + n 1 Cr _

Integer power

x n = x x n 1 _

Structure of recursion
Similar to mathematic induction, recursion requires the following two components
Recurrence relation(s) Base case(s)

Example F(n) IF (n=0) RETURN 1 ELSE RETURN n*F(n-1) //Base Case //Recurrence Relation

Recurrence Relations
1. Base Case: the initial condition or basis which defines the first (or first few) elements of the sequence Inductive (Recursive) Case: an inductive step in which later terms in the sequence are defined in terms of earlier terms. 2.

A recurrence relation for a sequence a1, a2, a3, ... is a formula that relates each term a k to certain of its predecessors ak-1, ak-2, ..., a k-i, where i is a fixed integer and k is any integer greater than or equal to i. The initial conditions for such a recurrence relation specify the values of a1, a2, a3, ..., ai-1.

Recursive Definition
We can also define the factorial function in the following way:

Recursive Algorithm
factorial(n) { if (n = 0) return 1 else return n*factorial(n-1) end if }

How Recursion Works

To truly understand how recursion works we need to first explore how any function call works. When a program calls a subroutine (function) the current function must suspend its processing. The called function then takes over control of the program.

How Recursion Works

When the function is finished, it needs to return to the function that called it. The calling function then wakes up and continues processing.

Recursion
To see how the recursion works, lets break down the factorial function to solve factorial(3)

Breakdown

Here, we see that we start at the top level, factorial(3), and simplify the problem into 3 x factorial(2). Now, we have a slightly less complicated problem in factorial(2), and we simplify this problem into 2 x factorial(1).s

Breakdown

We continue this process until we are able to reach a problem that has a known solution. In this case, that known solution is factorial(0) = 1. The functions then return in reverse order to complete the solution.

 The basic operation of the algorithm is multiplication, whose number of executions we denote M(n). Since the function F(n) is computed according to the formula F(n)=F(n-1).n for n>0

Complexity O(n)

Fibonacci Numbers
The Fibonacci numbers, a famous sequence 0,1,1,2,3,5,8,13,21,34.. That can be defined by the simple recurrence

fibonacci
int Fibonacci (int n) { if ( (n == 1) || (n == 2) ) return 1; else return Fibonacci (n-1) + Fibonacci (n-2); }

Recursive power example

Write method pow that takes integers x and y as parameters and returns xy. xy = x * x * x * ... * x (y times, in total) An iterative solution:
int pow(int x, int y) { int product = 1; for (int i = 0; i < y; i++) product = product * x; return product; }

36

Recursive power function

Another way to define the power function:
pow(x, 0) = 1 pow(x, y) = x * pow(x, y-1),
int pow(int x, int y) { if (y == 0) return 1; else return x * pow(x, y - 1); }
37

y > 0

How recursion works

each call sets up a new instance of all the parameters and the local variables as always, when the method completes, control returns to the method that invoked it (which might be another invocation of the same method) pow(4, 3) = 4 * pow(4, 2) = 4 * 4 * pow(4, 1) = 4 * 4 * 4 * pow(4, 0) = 4 * 4 * 4 * 1 = 64
38

Infinite recursion
a definition with a missing or badly written base case causes infinite recursion, similar to an infinite loop
avoided by making sure that the recursive call gets closer to the solution (moving toward the base case)
int pow(int x, int y) { return x * pow(x, y - 1); case } pow(4, 3) = = = = = = 4 * 4 * 4 * 4 * 4 * ... // Oops! Forgot base

pow(4, 2) 4 * pow(4, 1) 4 * 4 * pow(4, 0) 4 * 4 * 4 * pow(4, -1) 4 * 4 * 4 * 4 * pow(4, -2) crashes: Stack Overflow Error!

39

How C Maintains the Recursive Steps of variables by the C keeps track of the values
stack data structure.
Recall that stack is a data structure where the last item added is the first item processed. There are two operations (push and pop) associated with stack.
a b c pop b c push d d b c

How C Maintains the Recursive Steps

Each time a function is called, the execution state of the caller function (e.g., parameters, local variables, and memory address) are pushed onto the stack. When the execution of the called function is finished, the execution can be restored by popping up the execution state from the stack. This is sufficient to maintain the execution of the recursive function.
The execution state of each recursive step are stored and kept in order in the stack.

Activation records
activation record: memory allocates to store information about each running method
return point ("RP"), argument values, local variable values stacks up the records as methods are called; a method's activation record exists until it returns drawing the act. records helps us trace the behavior of a recursive method
[ 4 ] [pow(4,1)] [ 4 ] [pow(4,2)] [ 4 ] [pow(4,3)] [ 4 ] [main] _ y = [ 0 ] | | y = [ 1 ] | | y = [ 2 ] | | y = [ 3 ] | | | pow(4, 0) pow(4, 1) pow(4, 2) pow(4, 3) main

| | | | | | | | |

x RP x RP x RP x RP

= = = = = = = =

42

Iterative vs. Recursive

Iterative factorial(n) = 1

Function does NOT calls itself

if n=0 if n>0

n x (n-1) x (n-2) x x 2 x 1 Recursive factorial(n) = 1 n x factorial(n-1)

Function calls itself

if n=0 if n>0

Recursion vs. iteration

every recursive solution has a corresponding iterative solution
For example, N! can be calculated with a loop

Recursion
Uses more storage than iteration Runs slower due to runtime overhead

however, for some problems recursive solutions are often more simple and elegant than iterative solutions you must be able to determine when recursion is appropriate
44

The main benefits of using recursion as a programming technique are these:

invariably recursive functions are clearer, simpler, shorter, and easier to understand than their nonrecursive counterparts. the program directly reflects the abstract solution strategy (algorithm). Recursion works the best when the algorithm and/or data structure that is used naturally supports recursion. One such data structure is the tree

From a practical software engineering point of view these are important benefits, greatly enhancing the cost of maintaining the software.

Limitations of Recursion
In general, recursive algorithms run slower than their iterative counterparts. Also, every time we make a call, we must use some of the memory resources to make room for the stackframe.

Limitations of Recursion
Recursive solutions may involve extensive overhead because they use calls. When a call is made, it takes time to build a stackframe and push it onto the system stack. Conversely, when a return is executed, the stackframe must be popped from the stack and the local variables reset to their previous values this also takes time.

Limitations of Recursion
Consider the recursive Fibonacci generator How many recursive calls does it make?
F(1): 1 F(2): 1 F(3): 3 F(4): 5 F(5): 9 F(10): 109 F(20): 13,529 F(30): 1,664,079 F(40): 204,668,309 F(50): 25,172,538,049 F(100): 708,449,696,358,523,830,149 7 * 1020

At 1 billion recursive calls per second (generous), this would take over 22,000 years But that would also take well over 1012 Gb of memory!

Limitations of Recursion
Therefore, if the recursion is deep, say, factorial(1000), we may run out of memory. Because of this, it is usually best to develop iterative algorithms when we are working with large numbers.

Empirical Analysis of Algorithm

Empirical analysis of time efficiency

Select a specific (typical) sample of inputs Use physical unit of time (e.g., milliseconds) or Count actual number of basic operations executions Analyze the empirical data

Algorithm Visualization
Static Algorithm Visualization (series of still images) Dynamic Algorithm Visualization (Animation)