Introduction to Recursion

Lesson 1 of 7 · Recursion and backtracking

Recursion is a way of solving problems in which a function calls itself, but for a smaller problem. In this lesson we see how a recursive function is written, what the base case is and how the computer "remembers" unfinished calls.

Before you start: prerequisites – Functions in C++.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

What is recursion?

Imagine a queue of people and the question "what is your place in the queue?". A person does not count the whole queue, but asks the person in front of them and adds 1 to their answer. The first person in the queue does not ask anyone – they know they are first. A recursive function works the same way:

  • the base case – the smallest problem, whose answer is known without new calls (the first person in the queue);
  • the recursive step – the problem is reduced to the same, but smaller problem (ask the person in front of you and add 1).

Without a base case the function would call itself endlessly – the program stops with an error (stack overflow).

The first example: a countdown

The function prints the number n, and then leaves "the rest of the job" to the call for n - 1:

#include <iostream>
using namespace std;

void countdown(int n) {
    if (n == 0) {                 // the base case
        cout << "Start!" << endl;
        return;
    }
    cout << n << " ";
    countdown(n - 1);             // the recursive step: the same job for a smaller number
}

int main() {
    countdown(5);
    return 0;
}

Output: 5 4 3 2 1 Start!. Every call does only a small part of the job – it prints one number.

How it runs: the call stack

A function that returns a value waits for the result of the call for the smaller problem, and only then finishes its own computation. Let us look at the sum of the first n natural numbers: sum(n) = n + sum(n - 1), and sum(0) = 0.

#include <iostream>
using namespace std;

int sum(int n) {
    if (n == 0) return 0;         // the base case
    return n + sum(n - 1);        // waits for the result for n - 1
}

int main() {
    int n;
    cin >> n;
    cout << sum(n) << endl;
    return 0;
}
How the call sum(4) runs
StepCallWhat happens
1sum(4)it needs sum(3) – it waits
2sum(3)it needs sum(2) – it waits
3sum(2)it needs sum(1) – it waits
4sum(1)it needs sum(0) – it waits
5sum(0)the base case, returns 0
6sum(1)returns 1 + 0 = 1
7sum(2)returns 2 + 1 = 3
8sum(3)returns 3 + 3 = 6
9sum(4)returns 4 + 6 = 10

The unfinished calls are kept on the call stack: the last call started is the first to finish. That is why the depth of recursion is limited – for a few hundred thousand nested calls the memory for the stack can run out.

Work before and after the recursive call

The order of the statements relative to the recursive call changes the result. The function below prints the digits of a number from left to right, even though the digits are extracted from the right (n % 10): the printing is after the call, so it runs only when all the shorter calls have returned.

#include <iostream>
using namespace std;

void digits(int n) {
    if (n < 10) {                 // a one-digit number: the base case
        cout << n << " ";
        return;
    }
    digits(n / 10);               // first all the digits except the last one
    cout << n % 10 << " ";        // then the last digit
}

int main() {
    int n;
    cin >> n;
    digits(n);
    cout << endl;
    return 0;
}

If the printing is moved before the call (cout << n % 10; digits(n / 10);), the digits are printed in reverse order.

Recursion or a loop?

LoopRecursion
Repetitionthe body of the loopa new function call
Endthe loop condition becomes falsethe base case
Memoryconstantgrows with the depth (the call stack)
When it is bettersimple repetition (a sum, counting)the problem naturally splits into smaller identical problems: trees, graphs, backtracking, "divide and conquer"

Every recursion can be replaced with a loop (sometimes with your own stack), but a recursive solution is often much shorter and clearer – we will see this with the Towers of Hanoi and backtracking.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: easy

Printing from 1 to n

Write a recursive function that prints the numbers from 1 to n (in one line, separated by spaces). Loops are not allowed.

Example

Input

5

Output

1 2 3 4 5
TASK 02Difficulty: easy

The sum of the digits

Write a recursive function int digitSum(int n) and print the sum of the digits of the natural number that is entered.

Example

Input

4072

Output

13
TASK 03Difficulty: medium

How many times a digit appears

Read a natural number n and a digit c. Recursively count how many times the digit c appears in the notation of the number n.

Example

Input

1231271 1

Output

3
TASK 04Difficulty: medium

A palindrome (recursively)

Write a recursive function bool isPalindrome(const string &s, int i, int j) that checks whether the part of a word from the position i to j is a palindrome. Print YES or NO for the word that is read.

Example 1

Input

racecar

Output

YES

Example 2

Input

recursion

Output

NO
Common mistakes and tips
  • Always write the base case first, and only then the recursive step.
  • Check that the argument really decreases towards the base case (e.g. n - 1, n / 10), otherwise the recursion does not stop.
  • Pass parameters of the types string and vector as const & – otherwise a copy is made at every call.
  • For very deep recursion (several hundred thousand calls) a solution with a loop is better.

Check your knowledge

Open the quiz

Mini quiz: recursion

1. What is the base case of a recursion?




2. What does f(3) print if void f(int n){ if(n==0) return; f(n-1); cout<<n; }?




3. What happens when a recursive function has no base case?