* Ex 6.10, 6.11

Reading Assignment (for Mon July 10)

* Ch 7.1, 7.2 (skip Pointer Arithmetic), 7.4.

Assignment #3

* due Fri July 14.

Midterm #1

* Fri July 7.

Recursion

* When a function is invoked at execution time, it is said to be "activated".

* Each individual function activation has its own "activation frame".

main()

{ menu();

}

menu()

{ display();

}

display() ...

A recursive function

void echo_reversed()

{ char in_char;

cin.get(in_char);

if (in_char == `\n') {

cout << `\n';

} else {

echo_reversed();

cout << in_char;

}

}

* What will be the output of the recursive function if the cin stream contains "bat\n"?

* Compare this function with a stack.

Principles of writing recursive functions

* base case - when to stop.

* recursive case - (1) break the problem into smaller pieces; (2) combine the solutions to these smaller problems to produce the final solution.

The Factorial (iterative)

int

factorial(int n)

{ int result = 1;

for (int i = 2; i <= n; i++) {

result *= i;

}

return result;

}

The factorial (recursive)

int

factorial(int n)

{

}

Fibonacci Numbers (p.240)

* Definition:

1. The first Fibonacci number is 1.

2. The second Fibonacci number is also 1.

3. Every Fibonacci number after the first two is the sum of the two previous Fibonacci numbers.

fibonacci (recursive)

int

fibonacci(int n)

{

}