What is Recursive function: Definition and 29 Discussions

In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense. If the function is total, it is also called a total recursive function (sometimes shortened to recursive function). In computability theory, it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines (this is one of the theorems that supports the Church–Turing thesis). The μ-recursive functions are closely related to primitive recursive functions, and their inductive definition (below) builds upon that of the primitive recursive functions. However, not every total recursive function is a primitive recursive function—the most famous example is the Ackermann function.
Other equivalent classes of functions are the functions of lambda calculus and the functions that can be computed by Markov algorithms.
The subset of all total recursive functions with values in {0,1} is known in computational complexity theory as the complexity class R.

View More On Wikipedia.org
Recent contents Top users
  1. T

    MHB Recursive Function for Virus Spread: Finding the General Solution

    Could anyone please help me I am especially stuck on the second part of the question. Thanks very much I really appreciate it.
  2. Wrichik Basu

    Python RecursionError at a place where I have defined no recursive function

    Here is the code that I wrote: import numpy as np global m, n, p, q, arr1, arr2def input(): # Input for first matrix: print("Enter the number of rows of the first matrix: ", end="") globals()['m'] = int(input()) print("Enter the number of columns of the first matrix: ", end="")...
  3. CivilSigma

    Integral of a Recursive Function

    Homework Statement Find the following: $$ \int_0^\inf \frac{x^{a+1}e^{-x/\delta}}{\delta^{a+1}\Gamma(a+1)} dx; \, a > 1 , \delta >0 , 0 \leq x \leq \inf$$ Homework Equations - The Attempt at a Solution The numerator in the integral is constant, so it can be taken outside the integral. I then...
  4. Gionata

    I Recursive square root inside square root problem

    I have been debating this issue for days: I can't find a recursive function of this equation: ##\large{\sqrt{2+\pi \sqrt{3+\pi\sqrt{4+\pi\sqrt{5+\dotsb}}}}}## Starting value 2 always added with pi has been trying to find a solution this for days now, is what I have achieved so far: This...
  5. F

    Using a recursive algorithm to find the value of a game

    Homework Statement Imagine you are playing a game with me, of drawing balls from a box. There are two blue balls and two red balls. They are picked with equal probability, and are drawn without replacement. If you draw a blue ball, I give you $1. If you draw a red ball, you pay me $1.25. What...
  6. bornofflame

    [C] Use recursive function to get the min value of an array

    Homework Statement Using these two prototypes, double minValue( const double a[], unsigned els); double minIndex(const double a[], unsigned els); I am supposed to find the smallest value of an array using the minValue function as well as it's index by using the separate minIndex function and...
  7. S

    Writing a recursive function by using optional parameters

    One way that I often write recursive functions in my work is by having an optional parameter that is used for all calls after the first. For example, here's how I might implement the classic "Find the largest palindrome in a given string" interview-type problem: using System; public static...
  8. G

    C: Recursive function into iterative

    Homework Statement Write an iterative function char* conversion(unsigned int num, int base), that converts an integer num into any base (base <=10). Homework EquationsThe Attempt at a Solution How to transform the following recursive function conversion() into iterative: #include <stdio.h>...
  9. B

    Evaluating a recursive function

    Hello everyone, Here is the problem: Let ##\displaystyle f_0() = \frac{1}{1-x}##, and ##f_n(x) = f_0(f_{n-1}(x))##, where ##n \in \mathbb{N}##. Evaluate ##f_{2014}(2014)##. I first sought after a pattern, and then tried to make a conjecture. Here is what I found: ##\displaystyle f_1(x) =...
  10. G

    Asymptotic time complexity of Recursive function

    Homework Statement I've been asked to develop a recursive function and then analyze the asymptotic time complexity. f(N) = 0, if N < N1 f(N1) = C1 f(N)= A1 + M1*f(M2*N/D1 - S1) Op M3*f(M4*N/D2 - S2), if N > N1 Homework Equations We're to assume that: s1 = s2 = 0 m2 =...
  11. W

    Convergence time of a recursive function

    I have a recursive function that will eventually converge to either a fixed value or a limit cycle. Depending on the inputs, it will converge to different values (or cycles) at different rates. How could I go about measuring the rate of convergence for different inputs, regardless of what type...
  12. S

    Recursive Function Homework: Printing N Asterisks

    Homework Statement Hey, this isn't really homework, but my professor stated that any loop can be represented by a recursive function. Here is an example I made: Following is a loop inside of a recursive function. I have it set up such that it takes n asterisks and prints them on a single...
  13. S

    Simple Recursive Function- returning nan

    Simple Recursive Function-- returning "nan" Homework Statement I have a program that is supposed to simulate a growth population. The details are not of much importance. It is a rather simple program, however, I am having problems with the program returning the final value that it has stored...
  14. L

    Pure Recursive Function for f(n) = 6[SUP]n[/SUP] + 6n

    "Pure Recursive Function" for f(n) = 6n + 6n Howdy! First of all I was going to explain a 'Pure Recursive Function' as how my professor defined it: A pure recursive function is stated by only using previous values of the function.. Like: F(n) = f(n-1) + f(n-2) Which means you can't have a...
  15. J

    Writing a recursive function to compute the Jacobi symbol

    Write a recursive function to compute the Jacobi symbol J(a, n), is defined for relatively prime integers a and n, a> o, \mbox{ and } n > 0 by the formula J(a, n) = 1 \mbox{ if a = 1, } = J(a/2, n)*(-1)^\frac{n^2-1}{8} \mbox{ if a is even, } =J(n \% a, a)*(-1)^\frac{(a-1)*(n-1)}{4} \mbox{...
  16. P

    Error writing recursive function for Bonnet's recursion formula in C

    Bonnet’s recursion formula for Legendre polynomials is P(n,x)=1 for n=0 P(n,x)=x for n=1 and P(n,x)= (2n-1)/n*x*P(n-1,x)-(n-1)/n*P(n-2,x) I tried to write recursive function in C to calculate the value of polynomial for a given n and x float legpol(int n, float x) {...
  17. F

    Translating (Transforming) a recursive function

    Hi, I am having trouble understanding how this works. I am giving the following: y[k+2] - y[k+1] + 0.24y[k] = f[k+2] - 2f[k+1]; y[-2] = 1, y[-1] = 2; f[k] = 0 for k < 0; f[k] = k for k >= 0; I would like to have a program compute the next values in the sequence, so, I need y[-2] = 1 to...
  18. S

    Need help proving a recursive function works

    Homework Statement Prove the correctness of the following recursive algorithm to multiply two natural numbers, for all integer constants c ≥ 2. function multiply(y, z) comment Return the product yz. 1. if z = 0 then return(0) else 2. return(multiply(cy,[ z/c]) + y · (z mod c))...
  19. H

    Recursive function, diff under the integral sign

    Hey i stumbled over a problem which i can't solve: f is a continuous function on [a,b] and F_n is recursive given through: F_1(x)=\int_a^x f(t) \ dt and F_{n+1}=\int_a^x F_n(t) \ dt I have to proof that F_n looks like this: F_n(x)=\frac{1}{(n-1)!}\int_a^x (x-t)^{n-1} f(t) \ dt...
  20. A

    Recursive function equals xmod3 for all x in N

    I have a suspicion that if f(0)=0, and f(x)=min(N\Uf(x-2^i)) where i runs from 0 to i=floor(ln(x)/ln(2)), then f(x)=xmod3 for all natural numbers, x. Can anyone help me prove this inductively?
  21. W

    Solve Recursive Function: A_{n+1}= (8/9)A_n

    Homework Statement Solve the recursive function: A_{n+1} = (8/9)A_{n} + (24/9)*(20/9)^n We want a closed formula for A_n Homework Equations I'm just doing this to work out the surface area of the Menger Sponge. I know the formula's probably out there, but I get this...
  22. E

    Mathematica Recursive Function in Mathematica

    Hello, I want to write a recursive function in Mathematica, how can I do that? Regards
  23. W

    Create a recursive function in prolog

    can anyone help me out with this please i want to create a recursive function in prolog to do the following thing sum lists(X; Y;Z) holds for lists X = [x1; : : : xn], Y = [y1; : : : yn] and Z of numbers if and only if Z = [z1; : : : zn] and zi = xi+yi (1  i  n).
  24. N

    C/C++ Even summation with recursive function in c++

    Hi, I'm a beginner in C++. I wan't to write this program: Write a program that asks the user to enter n numbers –where n entered by the user- and calculates the sum of even numbers only. main function asks the user to enter n and then calls the recursive function Sum to read the values...
  25. S

    You are subscribed to this thread Proving conjecture for recursive function

    Hi, Homework Statement Just having some troubles with a proof i have been asked to do, (sorry for not knowing the math code) basically, f(1)=0, f(2)=1/3 and f(n)= ((n-1)/(n+1))*f(n-2) and I've come up with the conjecture that f(n) = 0 when n is odd, and = 1/(n+1) when n is even...
  26. R

    Simplifying a recursive function

    I am trying to find a formula for f(x) = a*f(x-1) + b*f(x-2) for x≥1, assuming f(-1) and f(0) are known. In other words, I need some expression for f(x) just in terms of a, b, f(-1), and f(0). I tried plugging in stuff and factoring on paper for the first few iterations, but it quickly got out...
  27. G

    What the hell is going on with this recursive function

    I am trying to follow the book on the proof that the factorial is a primitive recursive function and it is confusing as hell. It says 0!=1 y'!=y!y' (y' means the next one so 0=0 0'=1 0''=2 etc. ) We can simply define a two-argument function with a dummy argument, and then get rid of...
  28. N

    Recursive function in a physics equation

    Hoping someone can point out an example of a recursive function in a physics equation. If this is not a valid step that would be great to hear about too. Also if anyone has even tried to introduce such an equation in the past or how it might be represented. [I'm not the best student of maths]...
  29. D

    Writing a Recursive Function for Placing n Queens on an n x n Chessboard

    I have an assignment to write a recursive function that will safely place n Queens on an n x n chessboard. This wasn't all that difficult to figure out. For extra credit I'm supposed to write another function(s) (recursive?) that figures out all the possible solutions. This is, so far...
Back
Top