Dikstra's Algorithm

Overview

Lecture P6: Recursion

What is recursion?

s

When one function calls ITSELF directly or indirectly.

Why learn recursion?

s

New mode of thinking. Powerful programming tool. Many computations are naturally self-referential. – a Unix directory contains files and other directories – Euclid’s gcd algorithm – linked lists and trees – GNU = GNU’s Not Emacs

s

Start

s

Goal

2

Overview

How does recursion work? ! Just like any other function call. How does a function call work?

s

Implementing Functions

How does the compiler implement functions? ! With a STACK. Return from functions in last-in first-out (LIFO) order.

s

A function lives in a local environment: – values of local variables – which statement the computer is currently executing When f() calls g(), the system – saves local environment of f – sets value of parameters in g – jumps to first instruction of g, and executes that function – returns from g, passing return value to f – restores local environment of f – resumes execution in f just after the function call to g

FUNCTION CALL: push local environment onto stack. RETURN: pop from stack and restore local environment.

s

s

3

4

A Simple Example

Goal: function to compute sum(n) = 0 + 1 + 2 + . . . + n-1 + n. Simple ITERATIVE solution. iterative sum 1 int sum(int n) { int i, s = 0; for (i = 0; i 0) { n--; s += n; } return s; }

A Simple Example

Goal: function to compute sum(n) = 0 + 1 + 2 + . . . + n-1 + n. Simple ITERATIVE solution. sum(n-1)

s

s

s

Can also express using SELF-REFERENCE.

if n = 0 0 sum(n ) =   n + sum( n − 1) otherwise

base case reduction step converges to base case

recursive sum int sum(int n) { if (n == 0) return 0; return n + sum(n-1); } base case reduction step

Note that changing the variable n in sum does not change the value in the calling function.

5

6

A Simple Example

Goal: function to compute sum(n) = 0 + 1 + 2 + . . . + n-1 + n. Simple...