Original subtitles

Another category of functions is recursive programs, which are programs that are defined using references to themselves.

Here is an example of a recursive method, the Faculty function. The faculty of some number is defined as the

multiple of all whole numbers from that number down to 1. It is a function that grows extremely fast,

and as you can see in the code, whenever the input parameter n is not equal to 1, the function returns n

times itself, but called with an input that is 1 smaller. If n does equal 1, the function returns 1.

Let's try to illustrate it. Here is Faculty of N, which is N times Faculty of N-1.

Faculty of N-1 in turn gets N-1 as the input, so that is N-1 times Faculty of N-2.

Faculty of N-2 is N-2 times Faculty of N-3, and so on, until we have subtracted so much from N, so we are

down at, say, 2 times Faculty of 1, and Faculty of 1 returns 1 by definition.

The execution then goes all the way back up the recursion chain with all the return values.

All in all, we have seen N recursion steps from N all the way down to 1.

Each recursion step required some constant number of instructions.

We have seen that the exact constant number is not important when making this kind of asymptotic complexity

analysis, which is what all this Big O, Big Theta, and Big Omega is all about, so let's just write c as any constant.

In total, we get a complexity of c times N instructions, and we can use the component N and the slightly

larger constant c + 1 to express an upper bound of the complexity.

Similarly, we can use c - 1 to express a lower bound. And since we now both have a lower and an upper bound,

we can denote the complexity with Big Theta of N. Let's try a slightly more complicated example.

You may know the Fibonacci numbers, which is a sequence of numbers where any element in the sequence is

defined as a sum of the former two elements. Consider 1 and 1 as the first 2 elements.

The next element must be 2, because 1 + 1 is 2. The next element is 3, because the 2 former elements,

1 and 2 added gives 3, and so on. The code shown returns the Fibonacci number with precision N.

If the input is 0 or 1, it returns 1. That was the two first positions.

Otherwise, it returns the sum of the previous Fibonacci number, and the number before that.

Like with the Faculty function in the previous example, we can try to unfold the Fibonacci function called

with the input value of 5. That call results in 2 new calls, Fibonacci of 4 and Fibonacci of 3, respectively.

Fibonacci of 4 results in 2 new calls, namely 2 Fibonacci of 3 and Fibonacci of 2.

Also, the Fibonacci of 3 from before similarly results in 2 new calls, namely Fibonacci of 2 and Fibonacci of 1.

Notice that at Fibonacci of 1, that part of the recursion tree stops as the function just returns 1.

Fibonacci of 3 results in 2 new calls, namely Fibonacci of 2 and Fibonacci of 1, like we have seen just before.

Fibonacci of 2 results in 2 new calls, Fibonacci of 1 and Fibonacci of 0, both of which returns with a 1

instead of continuing the recursion. The 2 final recursion steps happen at the Fibonacci of 2 here, and here.

That seemed relatively complex, almost as if the execution exploded in recursion steps.

But how complex is it actually? Consider the recursion chain along the shown arrow.

This is the longest of all the recursion chains in the tree. Along that chain we have N recursion steps

for the input parameter N. If we should provide a quick upper bound and worst-case for the complexity,

we could notice that for each step along this longest chain, the total number of notes in the tree at most doubles.

So, there are N levels in the tree and at each level, the width of the tree at most doubles.

If the body of the function consumes some constant number of instructions, the total complexity can be

described as that constant number times the total number of function calls across a whole tree.

And since the number of function calls doubles at each level, it can be expressed as 2 times 2 times 2 and

so on, or c times 2 to the power of N - 1, to be precise, because we do not answer the recursion for values

of N smaller than or equal to 1. If we should come up with some upper bound for that expression,

we could use this constant c, but maybe the double value, for example, c times 2.

So, an upper bound can be written like this. And as you can see, we just got a factor of 2 more,

so instead of writing 2 to the power of N - 1, we can write 2 to the power of N, which is simpler.

In other words, the worst-case complexity of our recursive Fibonacci function is the exponential function,

Big O of 2 to the power of N. That results in a really poor performance.

And I therefore challenge you, try to implement the function yourself, and execute it with 2 inputs, 8 and 80, respectively.

If you accept the challenge, I recommend that you change the return type of the function from an int to a long.

I'm glad you're still here, because that means that you didn't wait to continue with the course until the

recursive Fibonacci function returned. The thing is that even though Fibonacci of 8 might return as within

the blink of an eye, Fibonacci of _____ will explode in complexity to a level where you shouldn't expect it to return.

Here you see another approach to the Fibonacci function. I will not dive into details, but as you can see,

it follows a plain old iterative strategy. Let's describe the complexity of that implementation.

The two initial declarations and assignments, as well as the last return statement are independent on

the input in and can thus be considered constant in complexity. Let's use c1 to describe these.

Next the follow up has iterations, and in each iteration, some things happen that are also independent on

the input end. It's just a bunch of assignments and the single declaration, therefore, we can describe the

complexity of the loop internals with another constant, say, c2.

So, c1 + N times c2 is a complexity of this method where c1 and c2 are constant numbers.

In order to come up with an upper bound for that complexity, I could use c2 and increase it; for example, to c2 + 1.

Then, N times c2 + 1 would be a steeper line than this c1 + N times c2, and thus an upper bound sooner or

later, and therefore the worst-case complexity of this implementation is O of N, Big O of N.

This is a straight line, and a much, much better performance guarantee than the recursive implementation from

before, which was Big O of 2 to the power of N. This implementation is also Big Omega of N, by the way,

since we can use, for example, c2 - 1 to express a lower bound or best-case for the complexity.

And thus, the complexity is also Big Theta of N. As a last example of recursive complexity calculation,

consider this somewhat complex function. It is a recursive implementation of the binary search that we have

looked at earlier. We will not go into details in the code, but use it as an example of how to recognize

what can be considered as constant elements of the code and how to quickly get an idea of the worst-case performance.

Again, we consider a haystack that is ordered, and this time the needle that we look for is the element 25.

The code uses two pointers representing a lower and upper boundary of the haystack.

The two boundaries define the interesting area to search in. The first thing that happens is that the

midpoint between the two boundaries is calculated. In this case, that midpoint points to the value 17.

Seventeen is smaller than 25, so everything to the left is irrelevant and can be ignored in further search.

We therefore move the lower boundary to the right of the midpoint.

Now we calculate the midpoint again, and this time it points to the value 26.

Twenty-six is larger than 25, so everything to the right is now irrelevant, and we can now move the upper

boundary to the left of the midpoint. A new midpoint is calculated, 21 is smaller than 25, and thus we move

the lower boundary to the right of the midpoint. Notice that the lower and upper boundaries now point to

the same element. The midpoint is therefore also the same element and in that we find the needle, namely 25.

Let's quickly calculate the complexity and assume that the haystack has N elements.

The worst-case is as follows. Each time we perform the recursion, either the lower or upper boundary is

replaced by the midpoint, effectively cutting the remaining search area in half.

And we have seen, therefore, N elements log N halvings unnecessary, and therefore we need at most log N recursion steps.

Consider the highlighted part of the code here. Nothing of that part is related to the input N.

Well, some of the code may return at some point, and we will not always run all of the highlighted code.

The point is, however, that even if we did run all the highlighted code, it would still be at most, say,

100 or 200 instructions. In other words, a constant number. Let's use a c to denote this constant number.

This gives c times log N instructions in total, and since we can easily find an upper bound for this

expression, for example, by multiplying with c + 1 instead of c, we can now say that the worst-case

complexity is Big O of log N. So, a good strategy when dealing with complexity analysis of recursive

functions is to first try to fold the recursion out and see how many recursion steps we worst-case have to

deal with, and then count the size in the number of instructions of each step.

In our examples, we were lucky that only a constant number of instructions was needed.