Session 2: Recursion

To understand recursion, one must first understand recursion.

In this session we will learn how to define recursive predicates: predicates using their 'own' predicate in their definition.

Introduction

Consider the following problem: we want to compute the sum of all digits in a given number. E.g. if the number is 26, we must return 8 (=2 + 6); if the number is 13758, we must return 24.

Before we discuss how to solve this in prolog, we first give some remarks on iteration and recursion for people who know other programming languages such as C/C++, Java, Pascal, ... (don't worry if you do not know any of these languages !).

The C/C++, Java, ... -style

In most programming languages one can iterate an instruction with for, while or repeat (this repeats the instruction until some condition holds). A typical 'iterative' solution for our example-problem is the next program (this is not prolog):

total = 0
while number>9 do
	total = total + (number mod 10)
	number = number / 10
total = total + number

The prolog-style

In prolog there is no for, while or repeat. In prolog iteration is done through recursion: define the solution of the complete problem in terms of solving a smaller variant of the same problem.

More precisely, we can solve our example-problem in prolog as follows: we express the solution as either the solution of the 'simple case' (the number only has one digit) or we reduce the problem to a simpler variant of the problem, namely for a number with one digit less.

% the simple case: if the number has only one digit
% then this number is the sum of all digits
count(Number,Number):-
	Number < 10.

% the recursive case: cut away the first digit, 
% let someone (=recursive call) add the rest, 
% and add your digit to that sum.
count(Number,Sum):-
	Number >= 10,
	Digit is mod(Number,10),
	NewNumber is Number // 10,
	count(NewNumber,TmpSum),
	Sum is TmpSum + Digit.

First some side-remarks about this program. If you are not yet familiar with 'is', check Bratko's book at page 81. In prolog we denote 'larger or equal' as '>='. Less or equal is denoted '=<'. It's easy to remember, you always 'point' towards the equal sign. For arithmetic operations we do not use '=' (as in Java, C++,...) but 'is'. '//' stands for integer division (X is 555 / 10 results in X being 55.5, but X is 555 // 10 results in X being 55). 

To understand how the above program works, draw a call tree for a call of count(437,Result).

Now how can you find this kind of recursive definitions yourself? Essentially, you have to think about how the big problem can be solved easily if you already have a solution for a subproblem. Usually this subproblem is the same problem but with a smaller input (a lower number, a shorter list,...). E.g. the recursive way of building a pile of N blocks is: let someone build a pile of N-1 blocks and put one block on top of it. Also, remember that you should always include a definition of the simple, non-recursive case (e.g. building a pile of 1 block is simply putting 1 block down)! 

Exercises

As a lot of prolog programs are recursive, it is very important that you learn how to write recursive programs. Try to solve the following exercises!

Exercise 1: Suppose a group of students gets the following instructions:

What does this 'program' do? What would appear on the blackboard if the leftmost student is given a piece of paper with the word 'hello'? 

Try to write a prolog program that solves this task. You may assume that there is a predicate split_string that splits a word into the first letter and the rest of the word. E.g. ?-split_string('hello',First,Rest) results in First being 'h' and Rest being 'ello'. Of course, you can also use the built-in predicate write (see session 1).

Exercise 2: Write a predicate all_even/1 taking as input a number. The predicate should succeed if all digits in that number are even, otherwise it should fail. Draw a call tree for all_even(2496).

Exercise 3: Write a predicate count_even/2 taking as input parameter a number. The output parameter should be the number of even digits in the input-number. E.g. count_even(24,A) should result in A being 2; count_even(25,A) should result in A being 1. Draw a call tree for these two examples.

Exercise 4: Try to understand the following program.

even(N):-
	A is mod(N,2),
	A = 0.
odd(N):-
	A is mod(N,2),
	A = 1.

funny(1):-
	write('I will quit'),nl.
funny(N):-
	even(N),
	write(N), nl,  % <-this
	NewN is N / 2,
	funny(NewN).
funny(N):-
	odd(N),
	write(N), nl,  % <-this
	N>1,
	NewN is 3 * N + 1,
	funny(NewN).

What is the result of the query funny(6) (if you only ask for the first answer of Prolog)? Write down what prolog would write to the screen. Do the same for funny(7)? What happens when you put the two lines with write(N), nl (marked with % <-this) before the even(N) and odd(N) in the definition of funny/1? (Optional if you have time : what would be the second answer of Prolog if you ask for another solution ?)

Exercise 5: (This is a more difficult exercise, skip it if you have problems with the other exercises.) a) Write a predicate double_digit/1 taking as an input a number. It should succeed if the number contains at least 2 equal digits, otherwise it should fail. E.g. doubledigit(12345) should fail; doubledigit(13423) should succeed. b) Repeat this exercise with the extra constraint that the two equal digits must occur next to each other. Which one is the most easy to program?

Exercise 6: Write a predicate fib/2 taking as an input an integer N. The output parameter should be the Nth fibonacci-number. The first two fibonacci numbers are both 1. The Nth fibonacci-number is the sum of the N-1th and the N-2th fibonacci number. In which respect is this recursion different from the previous exercises? What is the result of fib(5,F)? Is the way you calculate fibonacci numbers efficient? Why or why not?