Functions

Recursion

A recursive function solves a problem by calling itself on a smaller input.

base case The base case stops the recursion.
recursive case The recursive case calls the same function with a smaller value.

Recursion

n
recursion.c
Replay: real traced execution (multi-file project)
#include <stdio.h>

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main(void) {
    int n = 4;
    int result = factorial(n);

    printf("factorial=%d\n", result);
    return 0;
}

#include <stdio.h>

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main(void) {
    int n = 3;
    int result = factorial(n);

    printf("factorial=%d\n", result);
    return 0;
}

#include <stdio.h>

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main(void) {
    int n = 5;
    int result = factorial(n);

    printf("factorial=%d\n", result);
    return 0;
}

  1. n ← 4

    10int main(void) {11    int n→ 4 = 4; //@n=3, 512    int result = factorial(n4);

  2. int factorial(int n)

    pass 1 of 4
    3int factorial(int n4) {4    if (n <= 1) {5        return 1;6    }7    return n4 * factorial(n - 1);8}
    All 4 passes — pass 1 is the card above
    passn
    14
    23
    32
    41

  3. if (n <= 1)

    3int factorial(int n) {4    if (n1 <= 1) {5        return 1;6    }

  4. result ← 24

    11    int n = 4; //@n=3, 512    int result→ 24 = factorial(n4);1314    printf("factorial=%d\n", result24);15    return 0;16}
    outputfactorial=24

  1. n ← 3

    10int main(void) {11    int n→ 3 = 3;12    int result = factorial(n3);

  2. int factorial(int n)

    pass 1 of 3
    3int factorial(int n3) {4    if (n <= 1) {5        return 1;6    }7    return n3 * factorial(n - 1);8}
    All 3 passes — pass 1 is the card above
    passn
    13
    22
    31

  3. if (n <= 1)

    3int factorial(int n) {4    if (n1 <= 1) {5        return 1;6    }

  4. result ← 6

    11    int n = 3;12    int result→ 6 = factorial(n3);1314    printf("factorial=%d\n", result6);15    return 0;16}
    outputfactorial=6

  1. n ← 5

    10int main(void) {11    int n→ 5 = 5;12    int result = factorial(n5);

  2. int factorial(int n)

    pass 1 of 5
    3int factorial(int n5) {4    if (n <= 1) {5        return 1;6    }7    return n5 * factorial(n - 1);8}
    All 5 passes — pass 1 is the card above
    passn
    15
    24
    33
    42
    51

  3. if (n <= 1)

    3int factorial(int n) {4    if (n1 <= 1) {5        return 1;6    }

  4. result ← 120

    11    int n = 5;12    int result→ 120 = factorial(n5);1314    printf("factorial=%d\n", result120);15    return 0;16}
    outputfactorial=120