recursive definitions description of something that refers to itself is called recursive definition in our last formulationthe binary search algorithm makes use of its own description "callto binary search "recursinside of the definition--hencethe label "recursive definition at first glanceyou might think recursive definitions are just nonsense surely you have had teacher who insisted that you can' use word inside its own definitionthat' called circular definition and is usually not worth much credit on an exam in mathematicshowevercertain recursive definitions are used all the time as long as we exercise some care in the formulation and use of recursive definitionsthey can be quite handy and surprisingly powerful the classic recursive example in mathematics is the definition of factorial back in we defined the factorial of value like thisnn( )( ( for examplewe can compute ( )( )( )( recall that we implemented program to compute factorials using simple loop that accumulates the factorial product looking at the calculation of !you will notice something interesting if we remove the from the frontwhat remains is calculation of in generalnn( )in factthis relation gives us another way of expressing what is meant by factorial in general here is recursive definitionn if ( )otherwise this definition says that the factorial of isby definition while the factorial of any other number is defined to be that number times the factorial of one less than that number even though this definition is recursiveit is not circular in factit provides very simple method of calculating factorial consider the value of by definition we have ( ) ( !but what is !to find outwe apply the definition again ( ! [( )( )! ( )( !nowof coursewe have to expand !which requires !which requires since is simply that' the end of it ( ! ( )( ! ( )( )( ! ( )( )( )( ! ( )( )( )( you can see that the recursive definition is not circular because each application causes us to request the factorial of smaller number eventually we get down to which doesn' require another application of the definition this is called base case for the recursion when the recursion bottoms outwe get closed expression that can be directly computed all good recursive definitions have these key characteristics