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
5Output
1 2 3 4 5Recursion 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.
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:
Without a base case the function would call itself endlessly – the program stops with an error (stack overflow).
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.
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;
}
| Step | Call | What happens |
|---|---|---|
| 1 | sum(4) | it needs sum(3) – it waits |
| 2 | sum(3) | it needs sum(2) – it waits |
| 3 | sum(2) | it needs sum(1) – it waits |
| 4 | sum(1) | it needs sum(0) – it waits |
| 5 | sum(0) | the base case, returns 0 |
| 6 | sum(1) | returns 1 + 0 = 1 |
| 7 | sum(2) | returns 2 + 1 = 3 |
| 8 | sum(3) | returns 3 + 3 = 6 |
| 9 | sum(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.
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.
| Loop | Recursion | |
|---|---|---|
| Repetition | the body of the loop | a new function call |
| End | the loop condition becomes false | the base case |
| Memory | constant | grows with the depth (the call stack) |
| When it is better | simple 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.
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
Write a recursive function that prints the numbers from 1 to n (in one line, separated by spaces). Loops are not allowed.
51 2 3 4 5Write a recursive function int digitSum(int n) and print the sum of the digits of the natural number that is entered.
407213Read a natural number n and a digit c. Recursively count how many times the digit c appears in the notation of the number n.
1231271 13Write 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.
racecarYESrecursionNOn - 1, n / 10), otherwise the recursion does not stop.string and vector as const & – otherwise a copy is made at every call.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?