Functions

Recursion

Recursion solves a small problem by calling the same function with a smaller value.

base case A recursive function needs a base case that stops the chain of calls.

Recursion

value
recursion.cpp
Replay: real traced execution (multi-file project)
#include <iostream>

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

int main() {
    int value = 4;
    int result = factorial(value);

    std::cout << "value=" << value << std::endl;
    std::cout << "factorial=" << result << std::endl;
    return 0;
}

#include <iostream>

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

int main() {
    int value = 3;
    int result = factorial(value);

    std::cout << "value=" << value << std::endl;
    std::cout << "factorial=" << result << std::endl;
    return 0;
}

#include <iostream>

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

int main() {
    int value = 5;
    int result = factorial(value);

    std::cout << "value=" << value << std::endl;
    std::cout << "factorial=" << result << std::endl;
    return 0;
}

  1. value ← 4

    10int main() {11    int value→ 4 = 4; //@value=3, 512    int result = factorial(value4);

  2. int factorial(int value)

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

  3. if (value <= 1)

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

  4. result ← 24

    11    int value = 4; //@value=3, 512    int result→ 24 = factorial(value4);1314    std::cout << "value=" << value4 << std::endl;15    std::cout << "factorial=" << result24 << std::endl;16    return 0;17}
    outputvalue=4
factorial=24

  1. value ← 3

    10int main() {11    int value→ 3 = 3;12    int result = factorial(value3);

  2. int factorial(int value)

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

  3. if (value <= 1)

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

  4. result ← 6

    11    int value = 3;12    int result→ 6 = factorial(value3);1314    std::cout << "value=" << value3 << std::endl;15    std::cout << "factorial=" << result6 << std::endl;16    return 0;17}
    outputvalue=3
factorial=6

  1. value ← 5

    10int main() {11    int value→ 5 = 5;12    int result = factorial(value5);

  2. int factorial(int value)

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

  3. if (value <= 1)

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

  4. result ← 120

    11    int value = 5;12    int result→ 120 = factorial(value5);1314    std::cout << "value=" << value5 << std::endl;15    std::cout << "factorial=" << result120 << std::endl;16    return 0;17}
    outputvalue=5
factorial=120

Follow the Calls

  1. value starts as 4.
  2. factorial(4) returns 4 * factorial(3).
  3. The chain continues through 3, 2, and the base case 1.
  4. The multiplied result is 24.
  5. The program prints value=4 and factorial=24. | call | result path | | --- | --- | | factorial(1) | 1 | | factorial(2) | 2 * 1 = 2 | | factorial(3) | 3 * 2 = 6 | | factorial(4) | 4 * 6 = 24 |

Exercise: recursion.cpp

Reproduce value=4 and factorial=24, then use the pinned value variants 3 and 5 to predict factorial=6 and factorial=120.