Recursion and Dynamic Programming

Recursion and Dynamic Programming

Biostatistics 615/815 Lecture 5

Last Lecture

z Principles for analysis of algorithms

? Empirical Analysis ? Theoretical Analysis

z Common relationships between inputs and running time

z Described two simple search algorithms

Recursive refers to ...

z A function that is part of its own definition

e.g.

N Factorial(N -1)

Factorial ( N

)

=

1

if N > 0 if N = 0

z A program that calls itself

Key Applications of Recursion

z Dynamic Programming

? Related to Markov processes in Statistics

z Divide-and-Conquer Algorithms

z Tree Processing

Recursive Function in C

int factorial (int N) { if (N == 0) return 1; else return N * factorial(N - 1); }

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download