1 V Adamchik Recursions Victor Adamchik Fall of 2005 Plan 1 Forms of Recursion 1 1 Recursion with parameters 1 2 Course of value recursion 1 2 1 The Fibonacci Numbers 1 2 2 N bit Strings 1 3 Double recursion 1 3 1 The Archimedes number 1 3 2 The Ackermann function 1 4 Iterations 1 4 1 Infinite continued fractions 1 4 2 The Newton iteration Forms of Recursion In the previous lecture we have formally introduced recursion and recursive definition It has been noted that recursion has a lot in common with induction However you have to understand the main difference between them Induction is a method of proof Recursion is a method of construction defining The simplest example of recursion is a primitive recursion which is a way of defining f n 1 in terms of f n All primitive recursive functions are Turing computable The simplest examples of primitive recursive functions are sum product factorial and exponentiation over nonnegative integers int sum int x int y if x 0 y 0 return x y else return 1 sum x 1 y int product int x int y if x 0 y 0 return 0 else return y product x 1 y V Adamchik 21 127 Concepts of Mathematics In the following sections we consider the following forms of recursion recursion with parameters course of value recursion double recursion iterations Recursion with Parameters The Towers of Hanoi You all know the game Towers of Hanoi You have three pegs and a collection of disks of different sizes Initially all disks are stacked up at peg 1 the largest disk at the bottom then the next largest and so on up to the smallest disk which sits on top A move in this game consists of moving the top disk from one peg to another subject to the condition that a larger disk may never come to rest on a smaller one The objective is to find a sequence of admissible moves that will bring all the disks to peg number 2 The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883 The puzzle is well known to students of Computer Science since it appears in virtually all introductory text on data structures and discrete mathematics A couple lectures back we proved by induction that tt takes 2n 1 moves to move n disks from the first peg to the third peg Here we develop a recursive solution Let T n 1 3 be the minimum number of moves needed to solve the puzzle with n disks We will derive a recursive formula for T N 1 3 We break down the problem into three steps 1 move n 1 disks from 1 to 2 2 move one disk from 1 to 3 3 move n 1 disks from 2 to 3 1 peg n disks 2 peg 0 disk 3 peg 0 disk 1 peg 1 disk 2 peg n 1 disks 3 peg 0 disk 1 peg 0 disk 2 peg n 1 disks 3 peg 1 disk 1 peg 0 disk 2 peg 0 disk 3 peg n disks Therefore a recursive solution is given by T n 1 3 T n 1 1 2 T 1 1 3 T n 1 2 1 Such recursion is called a recursion with parameters If we ignore parameters we get the following equation for number of moves T n 2T n 1 1 V Adamchik 3 Course of value Recursion The Fibonacci Numbers Fibonacci was born 1170 in Pisa Italy and died in 1250 His real name is Leonardo Pisano In 1202 he wrote a book Liber Abbaci meaning Book of Calculating It helped bring arithmetic in Europe up to Arab standards One of Fibonacci s accomplishments was to determine how rabbits reproduce A man has one pair of rabbits at a certain place entirely surrounded by a wall We wish to know how many pairs can be bred from it in one year if the nature of these rabbits is such that they breed every month one pair male and female that in turn will begin to breed in the second month after their birth month 1 2 3 4 5 repro 0 1 2 3 5 non repro 1 0 1 2 3 total 1 2 3 5 8 This provides the definition for Fibonacci numbers Fn 2 F0 Fn 1 0 F1 Fn 1 Note we use two values Fn and Fn 1 in the definition Such a recurion is called a courseof value recursion Course of value recursion allows the use of any number of values for previous arguments Lucas numbers are the companions to the Fibonacci numbers and satisfy the same recurrence by different initial conditions Ln 2 L0 Ln 1 2 L1 Ln 1 N bit Strings Let Sn denotes the number of n bit strings that do not contain the pattern 111 Develop the recurent formula for Sn V Adamchik 21 127 Concepts of Mathematics Consider three cases 1 strings begin with 0 2 strings begin with 10 3 strings begin with 11 Suppose an n bit string begins with 0 and does not contain 111 Then by removing the first bit we get the n 1 bit string that does not contain 111 Therefore there are Sn 1 such strings Suppose an n bit string begins with 10 and does not contain 111 Then the n 2 bit string following 10 and does not contain 111 Therefore there are Sn 2 such strings Suppose an n bit string begins with 11 and does not contain 111 The third bit must be 0 Then the n 3 bit string following 110 and does not contain 111 Therefore there are Sn 3 such strings Thus Sn Sn 1 Sn 2 Sn 3 Initial conditions S1 S2 S3 2 4 7 Double Recursion The Archimedes Number Primitive recursion is used to define functions of one variable but with one or more parameters Double recursion allows the recursion to run on two variables Let us consider so called the Archimedes problem I will try to show you by means of geometrical proofs which you will be able to follow that of the numbers named by me some exceed not only the number of the mass of sand equal in magnitude to the earth filled up in the way described but also that of a mass equal in magnitude to the universe Archimedes defines his number recursively as h 0 n 1 h m 1 0 h m a h m 1 n 1 a h m 1 n V Adamchik 5 Solving the double recurence assuking that a 108 Archimedes gets an estimate of 1063 for the number of grains of sand needed to fill the universe Let us unwind a particular cases when m 0 h 1 0 1 h 1 n 1 a h 1 n The first argument of h is a parameter therefore by denoting h 1 n h n we get h 0 1 h n 1 a h n This suggests that Archimedes double recursion is reducible to primitive recursion In …