What is a RECURSIVE FUNCTION in C Language?

Question

is it that the function call is given inside the function itself? or where is it given?

Answer 1

recursive function: a procedure or subroutine, implemented in a programming language, whose implementation references itself .

Recursion in computer science is a way of thinking about and solving problems. It is, in fact, one of the central ideas of computer science. [1] Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem. [2]

"The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions." [3]

Most high-level computer programming languages support recursion by allowing a function to call itself within the program text. Imperative languages define looping constructs like “while” and “for” loops that are used to perform repetitive actions. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code. Computability theory has proven that these recursive only languages are mathematically equivalent to the imperative languages, meaning they can solve the same kinds of problems even without the typical control structures like “while” and “for”.



Tree created using the Logo programming language and relying heavily on recursion.Contents [hide]

1 Recursive algorithms

2 Recursive programming

2.1 Examples of recursively defined procedures (generative recursion)

2.1.1 Factorial

2.1.2 Fibonacci

2.1.3 Greatest common divisor

2.1.4 Towers of Hanoi

2.1.5 Binary search

2.2 Recursive data structures (structural recursion)

2.2.1 Linked lists

2.2.2 Binary trees

2.3 Recursion versus iteration

3 Tail-recursive functions

4 Order of function calling

4.1 Function 1

4.2 Function 2 with swapped lines

5 Direct and indirect recursion

6 See also

7 Notes and References

8 External links



[edit] Recursive algorithms

A common method of simplification is to divide a problem into sub-problems of the same type. As a computer programming technique, this is called divide and conquer, and it is key to the design of many important algorithms, as well as being a fundamental part of dynamic programming.

Virtually all programming languages in use today allow the direct specification of recursive functions and procedures. When such a function is called, the computer (for most languages on most stack-based architectures) or the language implementation keeps track of the various instances of the function (on many architectures, by using a call stack, although other methods may be used). Conversely, every recursive function can be transformed into an iterative function by using a stack.

Any function that can be evaluated by a computer can be expressed in terms of recursive functions without the use of iteration,[citation needed] in continuation-passing style; and conversely any recursive function can be expressed in terms of iteration.[citation needed]

To make a very literal example out of this: If an unknown word is seen in a book, the reader can make a note of the current page number and put the note on a stack (which is empty so far). The reader can then look the new word up and, while reading on the subject, may find yet another unknown word. The page number of this word is also written down and put on top of the stack. At some point an article is read that does not require any explanation. The reader then returns to the previous page number and continues reading from there. This is repeated, sequentially removing the topmost note from the stack. Finally, the reader returns to the original book. This is a recursive approach.

Some languages designed for logic programming and functional programming provide recursion as the only means of repetition directly available to the programmer. Such languages generally make tail recursion as efficient as iteration, letting programmers express other repetition structures (such as Scheme's map and for) in terms of recursion.

Recursion is deeply embedded in the theory of computation, with the theoretical equivalence of μ-recursive functions and Turing machines at the foundation of ideas about the universality of the modern computer.

[edit] Recursive programming

Creating a recursive procedure essentially requires defining a "base case", and then defining rules to break down more complex cases into the base case. Key to a recursive procedure is that with each recursive call, the problem domain must be reduced in such a way that eventually the base case is arrived at.

Some authors classify recursion as either "generative" or "structural". The distinction is made based on where the procedure gets the data that it works on. If the data comes from a data structure like a list, then the procedure is "structurally recursive"; otherwise, it is "generatively recursive".[4]

Many well-known recursive algorithms generate an entirely new piece of data from the given data and recur on it. HTDP (How To Design Programs) refers to this kind as generative recursion. Examples of generative recursion include: gcd, quicksort, binary search, mergesort, Newton's method, fractals, and adaptive integration.[5]

[edit] Examples of recursively defined procedures (generative recursion)

[edit] Factorial

A classic example of a recursive procedure is the function used to calculate the factorial of an integer.

Function definition:

Pseudocode (recursive):

function factorial is:input: integer n such that n >= 1output: [n × (n-1) × (n-2) × … × 1]

    1. if n is 1, return 1

    2. otherwise, return [ (n) × factorial(n-1) ]

end factorial



A recurrence relation is an equation that relates later terms in the sequence to earlier terms[6].

Recurrence relation for factorial:

bn = n * bn-1

b0 = 1

Computing the recurrence relation for n = 4:

b4           = 4 * b3             = 4 * 3 * b2

             = 4 * 3 * 2 * b1

             = 4 * 3 * 2 * 1 * b0

             = 4 * 3 * 2 * 1 * 1

             = 4 * 3 * 2 * 1

             = 4 * 3 * 2

             = 4 * 6

             = 4 * 6

             = 24



Example Implementations:

Scheme (programming language): C (programming language):

;; Input: Integer n such that n >= 1

(define (fact n)

  (if (= n 1)

      1

      (* n (fact (- n 1)))))

//INPUT: n is an Integer such that n >= 1

int fact(int n)

{

   if (n == 1)

      return 1;

   else

      return n * fact(n - 1);

}



This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages:

Pseudocode (iterative):

function factorial is:input: integer n such that n >= 1output: [n × (n-1) × (n-2) × … × 1]

    1. create new variable called running_total with a value of 1

    2. begin loop

          1. if n < 1, exit loop

          2. set running_total to (running_total × n)

          3. decrement n

          4. repeat loop

    3. return running_total

end factorial



Scheme (programming language), however, is a functional programming language and does not define any looping constructs. It relies solely upon recursion to perform all looping. Because Scheme is tail-recursive, a recursive procedure can be defined that implements the factorial procedure as an iterative process - meaning that it uses constant space but linear time.

Example implementations:

Scheme (programming language): C (programming language):

;; Input: Integer n such that n >= 1

(define (fact n)

  (fact-iter 1 n))



(define (fact-iter prd n)

  (if (= n 1)

      prd

      (fact-iter (* prd n) (- n 1))))

//INPUT: n is an Integer such that n > 0

int fact(int n)

{

   int prd = 1;



   while(n >= 1)

   {

      prd *= n;

      n--;

   }



   return prd;

}



[edit] Fibonacci

Another well known recursive sequence is the Fibonacci numbers. The first few elements of this sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21...

Function definition:

Pseudocode

function fib is:

input: integer n such that n >= 0

    1. if n is 0, return 0

    2. if n is 1, return 1

    3. otherwise, return [ fib(n-1) + fib(n-2) ]

end fib



Recurrence relation for Fibonacci:

bn = bn-1 + bn-2

b1 = 1, b0 = 0

Computing the recurrence relation for n = 4:

  b4            = b3 + b2

                = b2 + b1 + b1 + b0

                = b1 + b0 + 1 + 1 + 0

                = 1 + 0 + 1 + 1 + 0

                = 3



Example Implementations:

Scheme (programming language): C (programming language):

;; n is an integer such that n >= 0

(define (fib n)

  (cond ((= n 0) 0)

        ((= n 1) 1)

        (else

          (+ (fib (- n 1))

             (fib (- n 2))))))

//INPUT: n is an integer such that n >= 0

int fib(int n)

{

   if (n == 0)

      return 0;

   else if (n == 1)

      return 1;

   else

      return [ fib(n-1) + fib(n-2) ]

}



These implementations are especially bad because each time the function is executed, it will make two function calls to itself each of which in turn makes two more function calls and so on until they "bottom out" at 1 or 0. This is an example of "tree recursion", and grows exponentially in time and linearly in space requirements.[7]

[edit] Greatest common divisor

Another famous recursive function is the Euclidean algorithm, used to compute the greatest common divisor of two integers.

Function definition:

Pseudocode (recursive):

function gcd is:

input: integer x, integer y such that x >= y and y > 0

    1. if y is 0, return x

    2. otherwise, return [ cgd( y, (remainder of x/y) ) ]

end gcd



Recurrence relation for greatest common divisor, where "x % y&q

Answer 2

suppose you want to write a programme to find a factorial of number 10...(i.e.10! = 10*9*8*7*6*5*4*3*2*1 = 3628800)

consider the following programme

int factorial( int num );      /* Function prototype */

int main()

{

    int result, number;

    number = 10;

    .

    .

    .

    result = factorial( number );

}

int factorial( int num )      /* Function definition */

{

    .

    .

    .

    if ( num > 0 )

        return( num * factorial( num - 1 ) );

}

when mail() calls function factorial the argument is 10

hence in the return function values will be

return( 10 * factorial( 9 ) );

now second time when facorial calls itself argument is 9 hence

return(10 * 9 * factorial (8));

.

.

.

return(10*9*8*7*6*5*4*3*2*1* factorial(0));

since num is zero, factorial function will not call itself...hence this calculated value get returned to mail function

In the above example factorial function calls itself...this function is called as recursive function...

and hence recursive function is the function where it calls itself ...

one more thing to be noticed is that you need to provide a conditin to stop the recursion (i.e. calling the function itself ) , otherwise your programme will hang up in finite loop...in above example "if ( num > 0 )" condition is given to stop the recursion.

Your second question:

I thing in C, cbrt() is not a valid function in math.h...

you can use pow () function instead..

eg.

if you want a cube root of 10, 100, 1000 then...'

/* pow example */

#include <stdio.h>

#include <math.h>

int main ()

{

  printf ("Cube root of 10 = %lf\n", pow (10, 1/3));

  printf ("Cube root of 100 = %lf\n", pow (100, 1/3));

  printf ("Cube root of 1000 = %lf\n", pow (1000 ,1/3));

  return 0;

}

Answer 3

1. A recursive function is the one, which calls itself from within itself.

Stack is used as the primary data structure for handling recursions.

Considr a program to calculate the factorial of a number:

main ()

{

   .....

  fact (4);

  ....

}

Now, we know that,

fact (n) is simply n*fact (n-1)

SO, fact (n) can be calculted by simply multiplying n with the fact(n-1).

Then come fact(n-1). fact (n-1) = n*fact (n-2)

This is done till a BASE CONDITION occurs

The base condition here is: fact (1) = 1 and fact (0) =1

Therefore, the recursive function will be:

fact (int n)

{

   if (n==1 || n==0)

       return 1;

   else

       return n * fact (n-1)

}

fact (5) = (5 * fact (4))

              (5 * (4 * fact(3)))

              (5*(4*(3*fact(2))))

              (5*(4*(3*2*(fact(1)))))

We know that fact (1) = 1

so,

              (5 * (4 * (3 * (2 * 1))))

              (5* (4 * (3* 2)))

              (5* (4*6))

              (5*24)

              120

Hence the answer....

2. The cbrt() function may not be declared in the version of MATH.H header file with your C compiler. Do check.

Answer 4

Java tutorials-http://aboutjava.org/

Answer 5

when a function get called by iteself, it is said to be recursive function.

please use pow(double number,double power) defined in math.h

use 0.333 to get cube root.