Twelve problems, from beginner to advanced, where you write recursive functions (functions that call themselves). The main function is already written, so all you write is the body of the requested function. The goal is to use recursion instead of loops. Press "Check" to run your code with real gcc on several inputs and see whether the output is correct.
Note: Run and Check send your code to Wandbox, a free external compiler service, and run it with gcc.
int sum_to(int n) that takes an integer n (0 ≤ n ≤ 1000) and returns the sum from 1 to n, using recursion instead of a loop. When n is 0, return 0. The main function is provided."Run" executes your code with the input above. "Check" tests it against 4 prepared inputs.
return sum_to(n - 1) + n;. On its own this never stops, so first write the stopping condition: return 0 when n == 0.#include <stdio.h> int sum_to(int n) { if (n == 0) { return 0; } return sum_to(n - 1) + n; } int main(void) { int n; scanf("%d", &n); printf("Sum: %d\n", sum_to(n)); return 0; }
long long power(int x, int n) that takes an integer x (−9 ≤ x ≤ 9) and an integer n (0 ≤ n ≤ 18) and returns x to the power n. x0 is 1 (00 is also 1). The main function is provided."Run" executes your code with the input above. "Check" tests it against 5 prepared inputs.
n == 0, return 1; otherwise return x * power(x, n - 1);.#include <stdio.h> long long power(int x, int n) { if (n == 0) { return 1; } return x * power(x, n - 1); } int main(void) { int x, n; scanf("%d %d", &x, &n); if (x < 0) printf("(%d)^%d = %lld\n", x, n, power(x, n)); else printf("%d^%d = %lld\n", x, n, power(x, n)); return 0; }
long long. In x * power(...), x is converted to long long before the multiplication.int count_digits(int n) that takes an integer n (0 ≤ n ≤ 2000000000) and returns its number of digits. 0 has 1 digit. The main function is provided."Run" executes your code with the input above. "Check" tests it against 5 prepared inputs.
n < 10), return 1. Otherwise, the answer is the number of digits of n / 10 (n with the ones digit dropped) plus 1.#include <stdio.h> int count_digits(int n) { if (n < 10) { return 1; } return 1 + count_digits(n / 10); } int main(void) { int n; scanf("%d", &n); printf("Digits: %d\n", count_digits(n)); return 0; }
n == 0", the input 0 gets 0 digits. Check which value to stop at by making sure the answer is right for the smallest input (here, 0).int fib(int n) that returns the n-th Fibonacci number, where F(0) = 0, F(1) = 1 and F(n) = F(n−1) + F(n−2) (0 ≤ n ≤ 30). The main function is provided."Run" executes your code with the input above. "Check" tests it against 5 prepared inputs.
n == 0, 1 if n == 1, and otherwise return fib(n - 1) + fib(n - 2);.#include <stdio.h> int fib(int n) { if (n == 0) return 0; if (n == 1) return 1; return fib(n - 1) + fib(n - 2); } int main(void) { int n; scanf("%d", &n); printf("fib(%d) = %d\n", n, fib(n)); return 0; }
fib(1) calls fib(-1) and never stops. Note that this way of writing it repeats the same calculations many times, so the amount of work grows about 1.6 times each time n increases by 1 (about 2.7 million calls for n=30).void print_reverse(const char s[], int i) that takes a string s and a position i and prints the characters from s[i] to the end of the string in reverse order (do not use a loop). The main function is provided: it reads a string of letters, digits and symbols without spaces (at most 100 characters), calls print_reverse(s, 0), and then prints a newline."Run" executes your code with the input above. "Check" tests it against 5 prepared inputs.
s[i] is the null character '\0', return without doing anything. Otherwise, first print the rest in reverse with print_reverse(s, i + 1), and after that print s[i].#include <stdio.h> void print_reverse(const char s[], int i) { if (s[i] == '\0') { return; } print_reverse(s, i + 1); printf("%c", s[i]); } int main(void) { char s[101]; scanf("%100s", s); print_reverse(s, 0); printf("\n"); return 0; }
printf before the recursive call, the string is printed in its original order. If you put it after, the characters are printed in the order the calls return, starting from the deepest call (the last character), so the result is reversed.void print_binary(int n) that takes an integer n (0 ≤ n ≤ 1000000000) and prints it in binary (do not use loops or arrays). Do not print extra leading zeros. 0 is printed as 0. The main function is provided and prints a newline after calling the function."Run" executes your code with the input above. "Check" tests it against 6 prepared inputs.
n % 2, and the digits above it are the binary form of n / 2. Since you want to print from the highest digit, if n >= 2, call print_binary(n / 2) first, and then print n % 2.#include <stdio.h> void print_binary(int n) { if (n >= 2) { print_binary(n / 2); } printf("%d", n % 2); } int main(void) { int n; scanf("%d", &n); print_binary(n); printf("\n"); return 0; }
n == 0", nothing is printed for the input 0.int array_max(const int a[], int n) that returns the maximum of the first n elements (n ≥ 1) of the array a (do not use a loop). The main function is provided and reads n (1 ≤ n ≤ 100) and n integers (absolute value at most 10000)."Run" executes your code with the input above. "Check" tests it against 5 prepared inputs.
n == 1), a[0] is the maximum. Otherwise, return the larger of "the maximum of the first n−1 elements", array_max(a, n - 1), and the last element a[n - 1].#include <stdio.h> int array_max(const int a[], int n) { if (n == 1) { return a[0]; } int m = array_max(a, n - 1); if (a[n - 1] > m) { return a[n - 1]; } return m; } int main(void) { int a[100]; int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } printf("Max: %d\n", array_max(a, n)); return 0; }
a[n - 1], not a[n] (a[n] is out of range). Storing the result of the recursive call in a variable m saves you from writing the same call twice.int is_palindrome(const char s[], int left, int right) that returns 1 if the part s[left] to s[right] of the string s is a palindrome (reads the same forwards and backwards), and 0 otherwise. The main function is provided: it reads a string of lowercase letters without spaces (1–100 characters) and checks the whole string."Run" executes your code with the input above. "Check" tests it against 6 prepared inputs.
left >= right (one character or fewer left), it is a palindrome, so return 1. If the two ends s[left] and s[right] differ, return 0. If they are the same, recursively check the inner part (left + 1, right - 1) and return that result.#include <stdio.h> #include <string.h> int is_palindrome(const char s[], int left, int right) { if (left >= right) { return 1; } if (s[left] != s[right]) { return 0; } return is_palindrome(s, left + 1, right - 1); } int main(void) { char s[101]; scanf("%100s", s); int len = (int)strlen(s); if (is_palindrome(s, 0, len - 1)) { printf("%s is a palindrome\n", s); } else { printf("%s is not a palindrome\n", s); } return 0; }
is_palindrome(...) and you forget to write return, the result of the inner check is not passed back to the caller (using that value is undefined behavior). If the only stopping condition is left == right, then for strings with an even number of characters (such as abba) left and right pass each other, and the function reads beyond the end of the string.void hanoi(int n, char from, char to, char via) that prints the steps for moving all disks to C (it moves n disks from from to to, using via). Print one line "Disk k: X -> Y" for each move. The main function is provided: it reads n (1 ≤ n ≤ 10) and calls hanoi(n, 'A', 'C', 'B')."Run" executes your code with the input above. "Check" tests it against 5 prepared inputs.
n == 0".#include <stdio.h> void hanoi(int n, char from, char to, char via) { if (n == 0) { return; } hanoi(n - 1, from, via, to); printf("Disk %d: %c -> %c\n", n, from, to); hanoi(n - 1, via, to, from); } int main(void) { int n; scanf("%d", &n); hanoi(n, 'A', 'C', 'B'); return 0; }
int bsearch_rec(const int a[], int lo, int hi, int key) that searches for key in the range a[lo] to a[hi] of an array a sorted in ascending order, returning its index if found and −1 otherwise, using recursive binary search. The main function is provided: it reads n (1 ≤ n ≤ 100), n integers in strictly ascending order (no duplicates), and the value key to search for. Indices start at 0."Run" executes your code with the input above. "Check" tests it against 6 prepared inputs.
lo > hi (the search range is empty), return −1. Look at the middle mid = (lo + hi) / 2: if a[mid] == key, return mid; if key is smaller, search the left half (lo, mid - 1) recursively, and if it is larger, the right half (mid + 1, hi), and return that result.#include <stdio.h> int bsearch_rec(const int a[], int lo, int hi, int key) { if (lo > hi) { return -1; } int mid = (lo + hi) / 2; if (a[mid] == key) { return mid; } else if (key < a[mid]) { return bsearch_rec(a, lo, mid - 1, key); } else { return bsearch_rec(a, mid + 1, hi, key); } } int main(void) { int a[100]; int n, key; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } scanf("%d", &key); int pos = bsearch_rec(a, 0, n - 1, key); if (pos >= 0) { printf("%d is at a[%d]\n", key, pos); } else { printf("%d not found\n", key); } return 0; }
(lo, mid) or (mid, hi), the range may not shrink, and the same call can repeat forever. mid has already been checked, so always exclude it. The range halves with each call, so even with 100 elements it finishes in about 7 calls.int comb(int n, int r) that returns the number of combinations nCr of choosing r items from n, recursively using the relation nCr = n−1Cr−1 + n−1Cr (do not use factorials). nC0 = nCn = 1. The main function is provided and reads n and r (0 ≤ r ≤ n ≤ 20)."Run" executes your code with the input above. "Check" tests it against 6 prepared inputs.
r == 0 || r == n. Otherwise, return comb(n - 1, r - 1) + comb(n - 1, r); ("the sum of the upper-left and upper-right numbers" in Pascal's triangle).#include <stdio.h> int comb(int n, int r) { if (r == 0 || r == n) { return 1; } return comb(n - 1, r - 1) + comb(n - 1, r); } int main(void) { int n, r; scanf("%d %d", &n, &r); printf("%dC%d = %d\n", n, r, comb(n, r)); return 0; }
r == 0, comb(n - 1, r) produces calls where r is larger than n, and they do not stop even when n becomes negative. You need both ends (r=0 and r=n). The factorial method n!/(r!(n−r)!) easily overflows int in the intermediate factorials (13! already exceeds the range of int), so this recursion is also safer in that respect.void permute(int perm[], int used[], int depth, int n). perm is the permutation being built, used[k] is 1 if the number k+1 is in use, and depth is how many numbers have already been chosen. The main function is provided: it reads n (1 ≤ n ≤ 5) and calls permute(perm, used, 0, n)."Run" executes your code with the input above. "Check" tests it against 5 prepared inputs.
depth == n, everything has been chosen, so print perm and return. Otherwise, pick each number from 1 to n that is not yet used, in ascending order: put it in perm[depth], set used to 1, and call permute(perm, used, depth + 1, n). When it returns, set used back to 0.#include <stdio.h> void permute(int perm[], int used[], int depth, int n) { if (depth == n) { for (int i = 0; i < n; i++) { printf("%d ", perm[i]); } printf("\n"); return; } for (int k = 0; k < n; k++) { if (!used[k]) { used[k] = 1; perm[depth] = k + 1; permute(perm, used, depth + 1, n); used[k] = 0; } } } int main(void) { int perm[5]; int used[5] = {0}; int n; scanf("%d", &n); permute(perm, used, 0, n); return 0; }
used[k] = 0; after returning from the recursion, a number once used can never be chosen again, and only the first permutation is printed. Arrays are shared with the called function, so you have to manage setting and clearing the marks yourself. There are n! permutations (120 for n=5).