12.txt

一個計算機系教授的上課講義 主要是教導學生使用C語言編寫程序

CS 1355
Introduction to Programming in C
Thursday 2006.10.19 (Week 6)
Lecture notes (at http://r638-2.cs.nthu.edu.tw/C/notes/12.txt)

Chapter 5 continued (pp.170-179)
- Recursion

Recursion: 
- a function that calls itself, directly or indirectly.
- must have at least two cases:
  - a "base case" (where it does not call itself)
  - a "recursive case" (where it calls itself)
- Reason this works: a stack keeps track of multiple copies of the
  local (auto) variables.

Mathematically
- "recurrence" = an equation that is expressed in terms of itself.
- example: factorial
  n! = n * (n-1)!  => for n >= 1
  n! = 1           => for n < 1
- in terms of recursion, 
  the first is the recursive case, and the second is the base case.

as a C function

1	int factorial(int n) {
2		if (n < 1) { return 1; }	/* base case */
3		return n * factorial(n-1);
4	}

Why does this work?
- because of a stack structure:
  - each time a function is called, it's a push() of 
    - the location to continue,
    - the space for the parameters and (auto) local variables
  - the last function that is called is the first to return.
    => again, a stack structure

Calling
 factorial(0) => line 2 returns (base case, no recursive call
 factorial(1) => 1 * factorial(0) => (recursive case)
 factorial(10) => 10 * factorial(9)
                      => 9 * factorial(8)
                               => 8 * factorial (7)
                                  ...
However, this can be wasteful.
you could accomplish the same with a loop (in this case! but not in general)
	int fac = 1;
	for (i=2; i<= n; i++) {
		fac *= i;
	}
 	return fac;
 
Because this is "tail recursion" 
=> the last thing that this function does is to call itself.
   then we can just use a loop instead.

Another example: Fibonacci numbers
(see also Lecture 07)

It is defined recursively
fib(n) = n                      for n < 2  (base case)
fib(n) = fib(n-1) + fib(n-2)    for n >= 2 (recursive case)

as a C function

int fib(int n) {
	if (n < 2) { return n; }
	return fib(n-2) + fib(n-1);
}


f(0), f(1), f(2), f(3), f(4), f(5), f(6), f(7)... =
  0     1     1     2    3      5     8     13 ...


This can be also written as a loop, but a little more complicated
=> use two variables to keep track of f(n-1) and f(n-2),
=> see lecture notes 07.txt 


Where else do you use recursion?
1. on recursive data structures
   trees, graphs/networks, linked lists
2. on languages, parsing; any parenthesized data structures

Example: Prefix calculator => put operator in front

+ 2 3
5
+ 2 (+ 3 (* 4 5))
25

number operator number operator number operator ... ;

#include <stdio.h>
typedef enum { NUMBER, PLUS, TIMES, END, LPAREN, RPAREN } TokenType;

TokenType
Scan(int *value) {
	if (scanf("%d", value) == 1) {
		return NUMBER;
	}
	/* if it's not a number, try one of the operators */
	switch(getchar()) {
	case '+':  return PLUS;
	case '*' : return TIMES;
	case '(':  return LPAREN;
	case ')':  return RPAREN;
	case EOF:  return END;
	default: /* try again */
		return Scan(value);
	}
}

int main() {
	int v;
	int result = Eval(&v);
	if (result == NUMBER) {
		printf("%d\n", v);
	}
}

int Eval(int *value) {
	int v1, v2, t;
	int r1, r2, result = Scan(&v1);
	switch (result) {
	case NUMBER:  /* a base case, no recursion */
		*value = v1;
		return NUMBER;
	case LPAREN:  /* this is a single recursion -- stuff inside ( ) */
		result = Eval(value);
		/* expect RPAREN */
		t = Scan(&v1);
		if (t != RPAREN) {
			printf("Syntax error: missing )\n");
		}
		return result;
	case PLUS: 
		/* expect two expressions -- double recursion */
		r1 = Eval(&v1);
		r2 = Eval(&v2);
		if (r1 == NUMBER && r2 == NUMBER) {
			*value = v1 + v2;
			return NUMBER;
		}
		return r1;
	case TIMES:
		/* also expect two expressions -- double recursion */
		r1 = Eval(&v1);
		r2 = Eval(&v2);
		if (r1 == NUMBER && r2 == NUMBER) {
			*value = v1 * v2;
			return NUMBER;
		}
		return r1;
	case RPAREN: /* unexpected ?? */
		printf("Syntax error: unexpected )\n");
		return result;
	default:
		return result;
	}
}


Try it out:

% ./a.out
+ 2 3
5
% ./a.out
+ 2 (+ 3 (* 4 5))
25
% ./a.out
(4)
4
% ./a.out
+ (* 4 5) (+ * 2 3 4)
30
=> the last one evaluates it as
  4 * 5 = 20
  2 * 3 = 6
  6 + 4 = 10
  20 + 10 = 30

There are two "return values"
1. the token type (whether it is a number, a ( ) + * etc
2. the numeric value, passed as (int *value)

Use recursion to process a sub-expression
This is how the lisp language looks like 
- prefix operator
- parentheses notation

Recursion is used for processing "self-similar" problems
- expressions
- program statements
- tree, graph data structures