What is Recursion: Definition and 120 Discussions

Recursion (adjective: recursive) occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition. While this apparently defines an infinite number of instances (function values), it is often done in such a way that no infinite loop or infinite chain of references can occur.

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

    MHB Solving Recursion & Strings Problems

    Hi all, I cannot understand how to do the following question from a practice test paper and urgently need help! For each integer n >=1, let tn be the number of strings of n letters that can be produced by concatenating (running together) copies of the strings 'a", "bc" and "cb". For example...
  2. A

    MHB Recursion and Strong Induction

    Hi, I'm currently having trouble with using strong induction to prove a recursive sequence and don't know where to begin, any help would be great thanks. Define a recursive sequence f(0), f(1), f(2),... by f(0) = 0 f(1) = 1 f(n+1) = 3f(n) + 10f(n-1), for all integers n>=1 Prove by strong...
  3. S

    Exploring t(n): Recursion Tree Analysis

    Homework Statement Let the function t(n) be defined recursively by: ##t(1) = 1## ##t(n) = 3t(\frac{n}{2}) + n + 1## for n a power of two greater than 1. Draw several levels of the recursion tree for t, and answer the following: What will the height of the tree be if n is a power of 2...
  4. S

    Simplifying an Infinite Composite Recursion in a System of Equations

    Hello, I'm working with a system of equations that has an infinite recursion function, and am wondering if its possible to simplify or remove the recursion in terms of the other functions in the system. Any insight into the framework or family of this system is appreciated. Given two...
  5. MarkFL

    MHB CuRio$ty's question at Yahoo Answers regarding a linear homogeneous recursion

    Here is the question: I have posted a link there to this topic so the OP can see my work.
  6. A

    Finding explicit formula of this recursion formula

    Homework Statement Write an explicit formula for the sequence determined by the following recursion formula. t_{1}= 0; t_{n} = t_{n-1} + \frac{2}{n(n+1)} The Attempt at a Solution t_{1} = 0 t_{2} = t_{1} + \frac{2}{2(2+1)} t_{2} = \frac{1}{3} t_{3} = t_{2} + \frac{2}{3(3+1)} t_{3} =...
  7. N

    Matlab Recursion Problem - Need help Understanding It

    They give me this problem in my last exam, I did not get it right - its a very convoluted and I think poorly worded problem. Rants aside, how am I supposed to be able to answer a problem like this on the next exam? What sort of mindset will help me deal with recursion problems of this form? How...
  8. M

    Trouble understanding recursion (Python)

    I'm trying to understand a function which draws a koch curve using a library which draws (lt = left turn, fd = move forward, t represents an object class). def koch(t, n): if n<3: fd(t, n) return m = n/3.0 koch(t, m) lt(t, 60) koch(t, m) rt(t, 120)...
  9. R

    Mathematica How do I avoid the recursion limit in Mathematica?

    I wrote code where you input a prime, P > 3, and the next prime is the output. However it involves using a recursive formula with the number of recursive steps being in the order of P and using the Mod operator. Thus P must be below 255. How can I avoid this. Follows is my code: prime = 127...
  10. E

    Solving the Gamma Function: Using Recursion & Tables

    Homework Statement Questions are in picture. Homework Equations $$ \int _{0}^{\infty }x^{n}e^{-x}dx $$ = $$ Gamma (n+1) = n! $$ Gamma(P+1) $$ = $$Gamma(P)$$ $$ Gamma(P) = (1/P) $$Gamma(P+1)$$ The Attempt at a Solution 2) I have found it from table. 3) I have used recursion and...
  11. B

    What is the form of the following recursion relation?

    what is the "form" of the following recursion relation? Hi all, I have a recursion relation I am trying to solve: {X_n} = \frac{1}{{1 - {\alpha _0} \cdot {X_{n - 1}}}} \to {X_n} = ? What is the "mathematical form" of this recursion-relation? E.g., I know what a homogeneous, linear...
  12. N

    Iteration, recursion, optimization,

    Actually, it is really as easy as it looks. Paradoxically, it may be helpful to regard it as a special case of: 1 2 3 ...n 1 1 2 3 ...n 1 2 3 ...n 1 1 2 3 ...n 1 2 3 ...n 1 2 3 ...n 1 1 2 3 ...n 1 2 3 ...n 1 2 3 ...n 1 2 3 ...n 1 1 2 3 ...n 1 2 3 ...n 1 2 3 ...n 1 2 3 ...n 1 2 3 ...n 1...
  13. N

    Recursion, How does it loop here?

    I skipped all of my lectures since I usually like to understand things on my own but I am regretting it for recursion. I don't know why but I am finding it quite unintuitive and confusing. I have an exam coming tomorrow so I have to make sure that I understand it correctly. I know that...
  14. N

    MATLAB Matlab recursion (error in book?)

    This is what my book gives for recursion of fibonacci sequence (matlab coding). function res = fib(n) if n == 1; res = 0; elseif n == 2 res = 1; else res = fib(n-1) + fib(n-2); end Am I mistaken or this doesn't work for fib(3)? Keep in mind I am still learning about...
  15. Pythagorean

    Generalizing recursion in mapping functions

    I have a mapping function: x_{n+1} = \mu (1-x_n) I have some condition that occurs for: \mu (1-x_0) > 1 (1) which is: x_0 < 1- \frac{1}{\mu} but via the map function, there's an initial condition that leads to the above solution: **UNDER CONSTRUCTION, ERROR FOUND**
  16. N

    Recursion to print a fractal pattern

    C++ Recursion to print a "fractal pattern" I guess I really don't understand how to create a initial case for my recursion Can some advice to where I would need to change the code ___________The problem: Create a recursive function to draw this pattern, given a maximum number of stars (which...
  17. L

    Difference between Recursion and Reduction formulas in Integration?

    This post received no response. Can be deleted. Thanks.
  18. L

    What's the difference between Recursion & Reduction in terms of Integration?

    Homework Statement My book talks about the "reduction formulas" for evaluating trigonometric integrals by parts. However, is this the same thing as "recursive" formulas for integration by parts, a term which is not mentioned in my calculus book? Homework Equations The Attempt at...
  19. Mathelogician

    MHB A question on Transfinite Recursion Theorem schema....

    Hi everybody, In Enderton's "elements of set theory", he first discusses the red and then after some explanations he discusses the brown as the general form of transfinite recursion theorem schema. Then in the blue example, he uses the general form(brown) to show that the first form(red)is a...
  20. N

    Solving Recursion Problems with MMA - R.Gaylord

    Hello, I'm going through Introduction to programming with MMA by R.Gaylord and there is an exemple in chapter 7 about recursively creating k-elements subsets of a given set. subsets[Range[5], 2] should give {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2,5}, {3,4}, {3, 5}, {4, 5}}...
  21. I

    Solving a Quantum Field Theory Recursion Relation Through Self Study

    Hello Everyone! I have a problem I am solving through a self study project from Lowell Brown's book entitled: Quantum Field Theory". It is a math question (basically) on recursion relations. Homework Statement The variational definition gives us the relation: det[1-λK] = exp{tr...
  22. R

    Arrays and recursion in mips assembly language

    Homework Statement Write a MIPS assembly language program that accomplishes the following tasks: 1. The program will prompt the user to enter an Integer between 1 and 10. If the entered number doesn’t satisfy the above condition, use a loop and prompt the user for a new entry (until a valid...
  23. G

    Proving Recursion relations for Bessel Functions

    Homework Statement Solve equations 1) and 2) for J_{p+1}(x) and J_{p-1}(x). Add and subtract these two equations to get 3) and 4). Homework Equations 1) \frac{d}{dx}[x^{p}J_{p}(x)] = x^{p}J_{p-1}(x) 2) \frac{d}{dx}[x^{-p}J_{p}(x)] = -x^{-p}J_{p+1}(x) 3) J_{p-1}(x) + J_{p+1}(x) =...
  24. S

    Proving recursion relations. BFGS non linear optimization

    Homework Statement Please see attached thumbnail Here's what I know. 1)Bk is the Hessian 2) sk = \alpha*p 3)pk is the search direction 4) Alpha is the step size Homework Equations yk = \nablaf(xk+1) -\nablaf(xk Bk+1(xk+1-xk) = \nablaf(xk+1) -\nablaf(xk The Attempt at a Solution...
  25. sunrah

    Recursion relation in the hydrogen atom

    Homework Statement Given the following recursion formula: b_{j} = 2 \frac{kj - a}{j(j+1)-l(l+1)} \cdot b_{j-1} (where a, k and l are constants) how can b_{j = l} \neq 0 if b_{j - 1} = 0. Homework Equations The Attempt at a Solution This is a part question and I really can't see why. if...
  26. X

    Starnge Recursion algorithm definition

    I'm reading the book "Algorithms Design" and a recursion algorithm is defined as: T(n)\leqqT(n/q)+cn But in the Karatsuba’s Algorithm, the recurrence for this algorithm is T (n) = 3T (n/2) + O(n) = O(nlog2 3). The last equation is strange, since 3T(n/2) is bigger than the set. Why they define...
  27. 1

    Induction and Recursion I have NO idea

    I think I'm pretty good at standard induction. Never had a problem. Induction and recursion is mercilessly whooping my ***. Homework Statement Let a1 = 1. For each natural number n > 1, let an = 3an-1 - 1. Prove that for each natural number n, an = 1/2(3n-1 + 1) Homework...
  28. I

    Possible ways of doing recursion

    Hi I just have some questions on the principle of recursion. We use it to build sequences like Fibonacci etc. In such cases, the recursive rule is additive. So its very simple. But imagine the problems of constructing the sequences. This comes often in mathematics when the problem asks to...
  29. M

    Understanding the recursion theorem

    Hi all, Im doing some self study in set theory, but got kind of stuck with a proof my textbook gives about the so called recursion theorem: What I get from this is: Let \phi be a function that maps the result of a function that maps natural numbers to the set a, to the result of...
  30. J

    Recursion Theorem and c.e. sets

    Let \varphi_e denote the p.c. function computed by the Turing Machine with code number e. Given M=\{x : \neg(y<x)[\varphi_y=\varphi_x]\} prove that M is infinite and contains no infinite c.e. subset. I have already proved that M is infinite. A necessary and sufficient condition to prove that M...
  31. 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) {...
  32. P

    Wigner 3j symbol recursion relation

    Hi all! Homework Statement I have to show: \sqrt{(j \pm m ) (j \mp m+1} <j_1 j_2 m_1 m_2 | j_1 j_2 j m\mp 1 > = \sqrt{(j_1 \mp m_1 ) (j_1 \pm m_1+1} <j_1 j_2 m_1 \pm1, m_2 | j_1 j_2 j m > +\sqrt{(j_2 \mp m_2 ) (j_2 \pm m_2+1} <j_1 j_2 m_1 , m_2 \pm1 | j_1 j_2 j m > Homework...
  33. Z

    How to Correctly Reverse Digits in Python Using Recursion?

    Homework Statement def rev(n): '''Return the result of reversing the digits in integer n. For example, rev(512) should return 215.''' pass Homework Equations The Attempt at a Solution def rev(n): '''Return the result of reversing the digits in integer n. For example...
  34. J

    Why is Counting Down Considered Less Work in Recursive Functions?

    In class, we're learning about recursive functions. One example given was figuring out 1 + 2 + 3+ 4 + 5 + 6 + 7 + 8 + 9 + 10. My professor stated to address this, we start with 10 in the function and decrement for the next recursive call, so 10 + f(9). He said going the other way would be...
  35. F

    Comp Sci The Longest Increasing Sequence in a Two-Dimensional Grid of Numbers

    Homework Statement "Write a recursive Java program that finds the longest increasing sequence in a two-dimensional grid of numbers. A sequence is simply a series of adjacent squares. Squares may not be used twice. A grid might have multiple longest sequences. If an input grid does have...
  36. D

    Understanding Transfinite Recursion and Zorn's Lemma

    I am trying to understand the proof of Zorn's lemma from the axiom of choice, but I do not entirely understand the step where we create a increasing sequence (a_i) of sets in a partially ordered set S indexed by ordinals. It is defined through transfinite recursion, but how does that work...
  37. R

    Using a recursion relation to find the number of elements in a partition

    Homework Statement Let S(n,r) denote the number of elements of A_n of rank r. Then S(n,r) satisfies the recursion S(n,r)=(n-r)S(n-1,r-1) + S(n-1,r) Verify this formula for n=4 and r=0,1,2,3,4, using the values S(3,0) = 1 S(3,1)=3 S(3,2)=1 Homework Equations The Attempt at a...
  38. C

    Help with Solving 5a & Understanding Recursion Relations

    Would be really grateful if someone helped me with 5a, and explained the ideas behind recursion relations. I don't know what a recursion relation is, and how to apply for forum ales given Homework Statement http://img839.imageshack.us/img839/2301/recurrencerelation.gif...
  39. H

    Fortran What is the issue with this Fortran recursion problem?

    Hi everybody. I am learning Fortran on my own, and I started doing simple examples like factorials, iterations, and stuff like that. The problem comes in recursion, I'm trying to run this simple factorial program using recursion, but the outcome is completely wrong. I asked to an expert in...
  40. Saladsamurai

    Find Radius of Convergence from Recursion Equation

    Homework Statement Find Radius of Convergence of the corresponding power series solution from Recursion Equation alone: n^2a_{n+2} - 3(n+2)a_{n+1} +3a_{n-1} = 0 \qquad(1) Homework Equations R = 1/L where L = \lim_{n\rightarrow\infty}\left|{\frac{a_{k+1}}{a_k}\right|\qquad(2)...
  41. M

    What is the Python syntax for checking if a number is a palindrome?

    I'm doing the http://projecteuler.net/" problems for garbages and giggles, and was working on problem 4 which requires finding the largest number palindrome (e.g. 10301, 54345) that is the product of two 3-digit numbers. Below is my code, and I'm pretty sure Python will reproduce the error...
  42. M

    Solve Recursion Equation: f(x)=-f(x-1)+g(x)

    Hi I'm doing a project in math and seem to be stuck on one part. I come to trying to solve this recursion equation given by... f(x) = -f(x-1) + g(x) where g(x) is known. Would anyone mind showing me how to go around solving for f(x)? In this case i have g(x)=x^{2} and f(0)=0 and...
  43. H

    Recursion relation convergence

    Homework Statement Consider the sequence \left x_{n}\{\right\} defined by the recursion relation, x_{n+1} = \frac{1}{2} \left( x_{n} + \frac{2}{x_{n}} \right) where x0 > 0. Use the fact that "if a sequence of real numbers is monotonically decreasing and bounded from below, then...
  44. B

    A recursion to arrange a stars it's difficult

    a recursion to arrange a stars ! it's difficult :( hello ! :) my name is bella and i am still a student. I've instructed by my lecturer to create a simple program that will appear such as this output : Enter number of star : 5(user will key in the data) * ** *** **** *****...
  45. A

    Solving Integral Recursion: Proving I(n) for n∈ℕ0

    Can someone help me with this? I don't know how to begin I(n) = integral 1/(1+x^2)^n dx with n ∈ ℕ0 Than: ∀ n ∈ ℕ0, n≠1 : I(n) = 1/(2(n-1)) * x/((1+x^2)^(n-1)) + (2n-3)/(2(n-1)) * I(n-1) I have to prove this, but I don't know how to start
  46. H

    Approximating unsolvable recursion relations

    I have a complicated recursion replation, which I'm sure is unsolvable. (By "unsolvable" I mean that there is no closed form solution expressing \xi_1, \xi_2, \xi_3, etc. in terms of \xi_0.) It goes \frac{(k+4)!}{k!}\xi_{k+4} +K_1 (k+2)(k+1)\xi_{k+2}+ [ K_2 k(k-1) +K_3] \xi_{k} +K_4...
  47. J

    Recursion theorem (set theory)

    There are probably a million theorems called "the recursion theorem" and I'm not sure if this is actually one of them, but there's a remark saying that it defines recursion. It's proven by piecing together 'attempts' (functions defined on subsets of a domain) and states: For X a well-ordered...
  48. J

    What is the Recursion Relation for Series Solutions in Differential Equations?

    Homework Statement I just have a problem with series solutions when I get to the point of needing to find the recursion relation...and a few other problems. Homework Equations Assume y can be written ∑anxn The Attempt at a Solution So, on y'' + xy' + 2y = 0, I got to the point...
  49. D

    Ternary String recursion relation

    I don't understand this at all I have the solution but no idea. I am suppose to find the recursion relation for consecutive 0 in a ternary string(String that contains only 0, 1 and 2) So the solution I have is : Strings starting with 1 = an(The n is the small n for recursion) - 1...
  50. D

    Recursion: find explicit formula

    A(0, x) = x + 1 For : x >=0 A(y, 0) = A(y-1, 1) For : y > 0 A(y, x) = A(y-1, A(y, x-1)) For : y > 0, x > 0 Find A(2,x) for x >= 0 I worked this out... but I am wondering if I am right. Let x be 1 and y be 2. From statement 3 : A(y, x) =...
Back
Top