Introduction to Recursion

Function is recursive when it calls itself. Recursion is another way to make a loop, but it is much more than just a loop.

Recursion solves huge set of problems in intuitive way. But it needs to spent some time with the technique to understand it.

Description

Each recursion needs some termination, otherwise it leads to runtime error. When working with recursion you approch has to be more scientific and precise. Because recursion is very fragile, you have to ensure that everything leads to termination. Termination can be handled by termination conditions or recursive call (so called nested call) may be conditional.

#include <stdio.h>

void recursion (int number) {
    if (number == 0) { // termination condition of recursion
        printf("BOUNCE\n");
        return;
    }

    printf("> %d\n", number); // before nested call (pre order)
    recursion(number - 1);
    printf("< %d\n", number); // after nested call (post order)
}

int main () {
    recursion(4);
    return 0;
}

Try to simulate in your mind or on paper how computer is processing this program.

reveal output

user@pc:~/pa1/recursion$ ./a.out 
> 4
> 3
> 2
> 1
BOUNCE!
< 1
< 2
< 3
< 4

info

In post-order output is reversed.

info

Call of recursive function generates tree of calls. In the example above it is tree with just one branch, because recursion is unary (one subcall in the function).