Recursion

Recursive Definitions

• functions on natural numbers may be defined recursively

• value of function for n defined in terms of values for numbers < n

• “base” case defined for n = 0

• fibonacci numbers

– f(0) = f(1) = 1

– f(n) = f(n-1) + f(n-2) for n >= 2

• 0! = 1, n! = n* (n-1)! for n >= 1

Recursive Definitions

• other objects like sets and lists may also be defined recursively

• list of integers

– is either empty ( base case)

– is an ordered pair (i,l) where i is an integer and l is a list of integers ( i is the first element and l is the remaining list)

• all lists of integers can be constructed using this rule starting from the empty list

Recursive Computations

• computations on recursively defined objects expressed using recursive subprograms

• a subprogram is recursive if it directly or indirectly calls itself (with different arguments)

• result of subprogram depends on the result of subprogram for other values (usually smaller) of its actual arguments

• “base case” needs to be defined when subprogram computes result directly without calling itself

List Insertion

• use recursive definition of list to define list insertion

• insert integer i in a list l, two possibilities

• i is the first element in new list, i.e. new list is the ordered pair (i,l)

• i is not the first element, l is not empty and is an ordered pair (j, l’)

• new list is (j,l”) where l” is obtained from l’ by inserting i

Recursive List Insertion

recursive subroutine insert(list,i)

! inserts integer i in list if not already present

! note that target of list may be changed

! type element should be made public to user

integer, intent(in) :: i

type(element), pointer :: list, temp

logical :: empty, first

empty = .not. associated(list)

if (.not. empty) first = list%value > i

if (empty .or. first) then

temp => list

allocate(list)

list%value = i

list%next => temp

elseif( list%value < i) then

call insert(list%next,i) ! recursive call

end if

end subroutine insert

List Reversal

• reverse the order of elements in the list

• only pointer manipulations should be done

• elements should not be copied

• can be expressed more easily recursively

• recursive programs are often shorter, clearer, easier to correct and more elegant

• may be inefficient compared to non-recursive programs

• should not be used if efficiency is the main criterion

List Reversal

recursive subroutine reverse(list)

type(element), pointer :: list, temp

if (associated(list)) then

if (associated(list%next)) then

temp => list%next

call reverse(list%next)

temp%next => list

temp => list

list => list%next

nullify(temp%next)

endif

endif

end subroutine reverse

Sorting Lists

• same idea used for sorting a list of integers

• remove the first element, recursively sort the remaining list and insert the first element in the sorted list

• same as insertion sort

• get a faster sorting algorithm if we break the list into two lists of half the size, sort each half and combine sorted lists into one

• this algorithm is known as merge-sort and is one of the fastest sorting algorithms

Merge Sorting Lists

recursive subroutine merge_sort(list)

type(element), pointer :: list, temp, list1, list2

integer :: i, j

temp => list

i = 0

do

if (.not. associated(temp)) exit

temp => temp%next

i = i+1

end do

if ( i <= 1) return

i = i/2

temp => list

do j = 1, i-1

temp => temp%next

end do

list1 => list

list2 => temp%next

nullify(temp%next)

call merge_sort(list1)

call merge_sort(list2)

call merge(list1,list2,list)

end subroutine merge_sort

Merging Sorted Lists

subroutine merge(list1, list2, list)

type(element), pointer :: list, list1, list2, temp

if (list1%value < list2%value) then

list => list1

list1 => list1%next

else

list => list2

list2 => list2%next

end if

temp => list

do

if ((.not. associated(list1)) .or. (.not.associated(list2))) & exit

if (list1%value < list2%value) then

temp%next => list1

temp => temp%next

list1 => list1%next

else

temp%next => list2

list2 => list2%next

temp => temp%next

end if

end do

if (.not. associated(list1)) then

temp%next => list2

else

temp%next => list1

end if

end subroutine merge

! time required for merge sort is proportional to nlog₂n

! rather than n² as merging and splitting require time

! proportional to n

Quick Sort

• quick sort is another sorting algorithm which when implemented properly gives the fastest known sorting algorithm for random inputs

• useful for sorting arrays rather than lists

• main idea – pick one element, put it in its correct position, all elements < than it to its left and others to its right

• recursively sort left and right halves

• expressed easily using recursion

Quick Sort

recursive subroutine quick_sort(a)

implicit none

integer, dimension(:), intent(inout) :: a

integer :: i,n

n = size(a)

if ( n > 1) then

call partition(a,i)

call quick_sort(a(:i-1))

call quick_sort(a(i+1:))

end if

contains

Partition

subroutine partition(a,j)

integer, dimension(:), intent(inout) :: a

integer,intent(out) :: j

integer :: i,temp

i = 1 ; j = size(a)

do

do

if ( i > j ) exit

if (a(i) > a(1)) exit

i = i+1

end do

do

if ((j < i) .or. (a(j) <= a(1))) exit

j = j-1

end do

if ( i >= j) exit

temp = a(i)

a(i) = a(j)

a(j) = temp

end do

temp = a(j) ; a(j) = a(1) ; a(1) = temp

end subroutine partition

end subroutine quick_sort