Introduction to recursive functions
In the introduction to functions' chapter we learned that, in computing, the definition of a function borrows the mathematical definition. We also learned that, much like in mathematics, a function can call another function. If you have wondered if a function can call itself, you were right and that's called recursion. The question about recursive algorithm's performance vs non recursive algorithms is not studied in this course, that is left for later disciplines. For now let's just focus on what is recursion and how to use it.
The logic of an recursive algorithm is pretty similar to the mathematical induction's logic. Depending on the class and the teacher, exercises about recursion are not studied or are, but very briefly. It's recommended that many exercises which can be solved both by recursive and iterative methods are done to learn well the concept. Optionally you can solve some exercises about mathematical induction to see the relationship between induction and recursion.
The basic logic is: see if a sequence's term can be expressed in function of another, for example an geometric or arithmetic progression, then we can write a recursive algorithm. In other words: if the next step can be expressed in function of the previous one or one of the previous, then we can convert an iterative algorithm to a recursive algorithm.
Errors of logic:
- Confuse iteration with recursion;
- Confuse a function that calls itself with calling a function with itself as an argument;
- Infinite or excessive recursion.
What comes below requires knowledge about functions
- Sum of the first n natural numbers, now with a recursive function:
if (n == 0) return n;
else return n + sum_n(n-1);
}
Consider the following logic:
- The sum of n numbers is equal to summing n with the sum of all numbers behind n;
- Mathematically, the sum is n + S(n - 1);
- However, the sum S(n - 1) in turn, recurring to itself, is S(S(n - 1) - 1);
- Till where the recursion goes on? Until S(1) or S(0), a base case which can be solved directly without any more recursive calls.
This is how we write that using mathematical function notation:
[math]\displaystyle{ f(n) = \begin{cases} n & \text{if} & n = 0 \\ n + f(n - 1) & \text{if} & n \gt 0 \end{cases} }[/math]
Notice how that is completely different from using a loop. Is there iteration? No, what we have is a function calling itself until a limit is hit, the base case. With a loop there is a sum operation that is repeated till a variable accumulates the desired sum. In the case of the recursive function what happens is a succession of recursive calls in which one call waits for the returned value of the next, until the base case is hit and the function returns the base value. There are technical details about the limits of recursion but they are skipped for this introductory level.
This is how the computer processes it:
- n = 10. Is this the base case? No. Then 10 + f(9);
- Is 9 the base case? No. Then 9 + f(8);
- Continue in this succession until it hits 1 + f(0);
- We have two things to track: one is the variable n, the other is the value of the function itself;
- Calculate the nth term of the Fibonacci's sequence
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Using a mathematical notation:
[math]\displaystyle{ f(n) = \begin{cases} n & \text{if} & n = 1 \\ n = 0 & \text{if} & n = 0 \\ n + f(n - 1) + f(n - 2) & \text{if} & n \gt 2 \end{cases} }[/math]
Be careful! The n represents the position in the sequence, not the number itself!
We track this function in the same way we tracked the sum of the first n integers. As an exercise, try to write a recursion function to calculate the factorial of n. Another exercise: try to calculate xn recursively.
For this introductory level we aren't concerned about performance or other technical details. Our only concern is with the logic of recursion x iteration. Sometimes one is easier to write than the other.
Iterative version:
int i, auxiliary, current = 1, previous = 0;
if (n == 0) return 0;
if (n == 1) return 1;
auxiliary = current;
current = current + previous;
}
return current;}
The iterative version is much more efficient for a simple reason: a variable stores the partial sum for the next term. The recursive version is "dumber", it goes all the way back to the beginning of the series to calculate the next term.
- Print an array using recursion
/* receives an array and the index of its last element */
printf("\n%d", array[index]);
if (n == 0) return 0;
return print (array, index - 1);
}
The function prints in descending order, from the last index to the first. Be careful! The indexes start at n - 1, therefore, if the array has 10 elements and the function is called with n = 10, the first element is going to be array[10], and the last, array[0], is going to be skipped.
As an exercise, try to modify the function such as n means the number of elements to be printed, not the last array's index position.
Same thing, but in ascending order:
/* receives an array and the last element's index to be printed
level is a counter of recursive calls */
printf("\n%d", array[index]);
if (level == 0) return 0;
return print (array, index + 1, level - 1);
}
To print in ascending order the function requires an extra parameter, a counter of function's levels inside itself. To print the first 10 array's elements, n must start at zero and level must start at 9. Notice how the function's call literally reads "print array from 0 (index) to 9 (function's levels inside itself)".
Repeat the previous exercise, but now try to make the function be read as "print array from the first element to the last".
An analogy: think on a building. When we printed in descending order, we started at the 9th floor (highest level) and walked down to the zero floor (base case), the ground level. Each level matched the array's index. When we print in ascending order, we still start at the highest level and go down to the zero, but at each level, rather than counting "9th floor, 8th floor, ..." we are counting "advancing one step, two steps, ...".
- Read an array and return one if all elements are equal or zero if they aren't
/* Receives two values, if they are equal, return 1.
If they aren't, return 0. */
if (a == b) return 1;
return 0;
}
/* Receives an array and the last element's index.
If two consecutive elements are different, return 0.
If the index counter reaches 1, then all elements are equal
Otherwise, the function goes one level deeper in itself */
if (compare(a[i], a[i - 1]) == 0) return 0;
if (i == 1) return 1;
return search(a, i - 1);
}
There are two functions, a regular one and a recursive one. Remember: a function cannot return two values at the same time, itself plus one or zero depending on whether all the array's elements are equal or not. That's why the problem has been split into two functions. One compares two values, the other does the recursive search. Notice that there are two ways to interrupt the recursion: one is to have two different consecutive elements, the other is reaching the array's end (base case); both in that order! If we solved it using a loop, we'd have the same two ways of interrupting the loop's iterative process.
