Recursion
The recursive function is
– a kind of function that calls itself, or
– a function that is part of a cycle in the sequence of function calls.
f1 f1 f2 … fn
Let’s we want to find the factorial of a number: f(n) = n! We know that
n! = 1 * 2 * 3 * … * (n – 1) * n
For example, f(5) = 1 * 2 * 3 * 4 * 5. We also know that f(4) = 1 * 2 * 3 * 4. So
f(5) = (1 * 2 * 3 * 4) * 5 = f(4) * 5
The problem of calculating f(5) is reduced to the problem of calculating f(4): in
order to find f(5) we first must find f(4) and then multiply the result by 5. This process
can be continues like
f(5) = f(4) * 5 = f(3) * 4 * 5 = f(2) * 3 * 4 * 5 = …
How long shall we continue this process? We know that 0! = 1, but there is no
sense for calculating factorial for negative numbers. The equality 0! = 1 or f(0) = 1 is
called simple case or terminating case or base case. When we need to find f(0), we do
not continue the reduction like f(0) = f(-1) * 0 because it has no sense, but simply
substitute the value of f(0) by 1. So
f(2) = f(1) * 2 = f(0) * 1 * 2 = 1 * 1 * 2 = 2
A recursive function consists of two types of cases:
a base case(s)
a recursive case
The base case is a small problem
the solution to this problem should not be recursive, so that the function is
guaranteed to terminate
there can be more than one base case
The recursive case defines the problem in terms of a smaller problem of the same
type
the recursive case includes a recursive function call
there can be more than one recursive case
From the definition of factorial we can conclude that
n! = (1 * 2 * 3 * … * (n – 1)) * n = (n – 1)! * n
If we denote f(n) = n! then f(n) = f(n – 1) * n. This is called recursive case. We
continue the recursive process till n = 0, when 0! = 1. So f(0) = 1. This is called the base
case.
f(3) = f(2) * 3
f(1) * 2
1*1*2*3 = 6
f(0) * 1
1
f (n) f (n 1) * n recursive case
f (0) 1 base case
E-OLYMP 1658. Factorial For the given number n find the factorial n!
► The problem can be solved with for loop, but we’ll consider the recursive
solution. To solve the problem, simply call a function fact(n). The value n ≤ 20, use
long long type.
long long fact(int n)
{
if (n == 0) return 1;
return fact(n-1) * n;
}
E-OLYMP 1603. The sum of digits Find the sum of digits of an integer.
► Input number n can be negative. In this case we must take the absolute value of
it (sum of digits for -n and n is the same).
Let sum(n) be the function that returns the sum of digits of n.
If n < 10, the sum of digits equals to the number itself: sum(n) = n;
Otherwise we add the last digit of n to sum(n / 10);
We have the following recurrence relation:
sum (n / 10 ) n%10, n 10
sum(n) =
n, n 10
sum(123) = sum(12) +3 = sum(1) +2 +3 = 1 +2 +3 = 6
E-OLYMP 2. Digits Find the number of digits in a nonnegative integer n.
► Let digits(n) be the function that returns the number of digits of n. Note that
sum of digits for n = 0 equals to 1.
If n < 10, the number of digits equals to 1: digits(n) = 1;
Otherwise we add 1 to digits(n / 10);
We have the following recurrence relation:
digits (n / 10 ) 1, n 10
digits(n) =
1, n 10
Example: digits(246) = digits(24) + 1 = digits(2) + 1 + 1 = 1 + 1 + 1 = 3.
E-OLYMP 3258. Fibonacci Sequence The Fibonacci sequence is defined as
follows:
a0 = 0
a1 = 1
ak = ak-1 + ak-2
For a given value of n find the n-th element of Fibonacci sequence.
► In the problem you must find the n-th Fibonacci number. For n ≤ 40 the
recursive implementation will pass time limit. The Fibonacci sequence has the
following form:
i 0 1 2 3 4 5 6 7 8 9 10 ...
fi 0 1 1 2 3 5 8 13 21 34 55 ...
The biggest Fibonacci number that fits into int type is
f46 = 1836311903
For n ≤ 40 its enough to use type int.
Let fib(n) be the function that returns the n-th Fibonacci number. We have the
following recurrence relation:
fib(n 1) fib(n 2), n 1
fib(n) = 1, n 1
0, n 0
int fib(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n-1) + fib(n - 2);
}
