Recursion, divide and conquer
Orion Electric Age
  2018-08-12 01:05:36 2018-08-12 01:05    

the stack

Base actions are push and pop, just like FILO(first in last out) queue.

base case and recursive case

Every recursive function has two parts: the base case, and the recursive case.

divide and conquer

Suppose you’re a farmer with a plot of land. You want to divide this farm evenly into square plots. You want the plots to be as big as possible. Just divide to get the largest square, and repeat the step with the remaining part.

inductive proofs

For example, suppose I want to prove that I can climb to the top of a ladder. In the inductive case, if my legs are on a rung, I can put my legs on the next rung. So if I’m on rung 2, I can climb to rung 3. That’s the inductive case.

Tower of Hanoi

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  • Only one disk can be moved at a time.
  • Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
  • No disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2^n − 1, where n is the number of disks.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>

static int times = 0;

/**
  * @param n, layers of tower
  * @param A, the source
  * @param B, the destination
  * @param C, the swap
  */ 
static void hanoi(int n, char A, char B, char C);

static void hanoi(int n, char A, char B, char C)
{
    if (n > 0) {
        hanoi(n - 1, A, C, B);
        printf("%c -> %c ", A, C);
        hanoi(n - 1, C, B, A);

        times++;
    }
}

int main(int argc, char *argv[])
{
    int layer;


    layer = 3, times = 0;
    hanoi(layer, 'A', 'B', 'C');
    printf("layer = %d, times %d = 2^%d - 1\n", layer, times, layer);

    layer = 4, times = 0;
    hanoi(layer, 'A', 'B', 'C');
    printf("layer = %d, times %d = 2^%d - 1\n", layer, times, layer);

    layer = 7, times = 0;
    hanoi(layer, 'A', 'B', 'C');
    printf("layer = %d, times %d = 2^%d - 1\n", layer, times, layer);

    return 0;
}

Fibonacci sequence

A typical recursive example, F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n>=2，n∈N)
As described above, the base case is F(1)=1, F(2)=1, and the recursive case is F(n)=F(n-1)+F(n-2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>

static unsigned long fibonacci(int n)
{
  if (n == 1 || n == 2) {
    return 1;
  }

  return fibonacci(n - 1) + fibonacci(n - 2);
}

int main(int argc, char *argv[])
{
  int n;

  if (argc != 2) {
    printf("argc invalid\n");
    return -1;
  }

  n = atoi(argv[1]);
  printf("fibonacci n = %d\n", n);

  printf("f(%d) = %lu\n", n, fibonacci(n));

  return 0;
}

Some other fibonacci interesting sequences

  • Fibonacci Brick Wall Patterns, The point of this activity is to see how many ways you can build a brick wall using the given amount of bricks.
    • Each wall needs to be two units tall.
    • Each brick standing on end is two units tall.
    • Each brick laying on it’s side is one unit tall.
    • You are first given one, then two, three, etc.
    • For one brick there is only one method of building a wall. Two methods for two, and three methods for three.
    • How many ways are there to build a wall with four bricks, five?Show your work, and how does this tie into the Fibonacci sequence?

quick sort

Another typical recursive example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <stdio.h>

static int array[] = {15, 9, 23, 21, 111, 101, 98, 101, 0, 1};
static int asize = sizeof(array) / sizeof(int);

static void dump_array(int array[], int size, const char *prefix)
{
  int i;

  if (NULL != prefix) {
    printf("%s: ", prefix);
  }

  for (i = 0; i < asize; i++) {
    printf("%d ", array[i]);
  }
  printf("\n");

  return;
}

static int partition(int array[], int size)
{
  int i, pivot;
  int s;

  pivot = size / 2;

  for (i = 0; i < size; i++) {
    if (i == pivot) continue;

    if (array[i] < array[pivot]) { /* if < pivot, and on the right */
      if (i == (pivot + 1)) {
        s = array[pivot];
        array[pivot] = array[i];
        array[i] = s;

        pivot = i;
      } else if (i > pivot) {
        s = array[i];
        array[i] = array[pivot + 1];
        array[pivot + 1] = array[pivot];
        array[pivot] = s;

        pivot += 1;
      }
    } else if (array[i] > array[pivot]) { /* if > pivot, and on the left */
      if (i < pivot) {
        s = array[pivot];
        array[pivot] = array[i];
        array[i] = s;

        pivot = i;
      }
    }
  }

  return pivot;
}

static void qsort(int array[], int size)
{
  int pivot;

  if (size < 2) return;

  pivot = partition(array, size);

  qsort(&array[0], pivot);
  qsort(&array[pivot + 1], size - pivot - 1);

  return;
}

int main(int argc, char *argv[])
{
  dump_array(array, asize, "Before sort");

  qsort(array, asize);

  dump_array(array, asize, " After sort");

  return 0;
}

Pascal’s triangle

Reference

  • 程序员的数学（日 结城浩）
  • Algorithms, 4th Edition
  • Grokking Algorithms: An illustrated guide for programmers and other curious people