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. pawlo392

    I Resolve the Recursion of Dickson polynomials

    I am trying to prove the expression for Dickson polynomials: $$D_n(x, a)=\sum_{i=0}^{\lfloor \frac{n}{2}\rfloor}d_{n,i}x^{n-2i}, \quad \text{where} \quad d_{n,i}=\frac{n}{n-i}{n-i\choose i}(-a)^i$$ I am supposed to use the recurrence relation: $$D_n(x,a)=xD_{n-1}(x,a)-aD_{n-2}(x,a)$$ I have...
  2. shivajikobardan

    Comp Sci How do I think about recursion in programming?

    I got the idea for problems like factorials or finding sum from 1 to n, where there's a pattern visible. Like this: Source:https://99x.io/blog/recursion-is-not-hard-here-is-the-right-way-to-think I got it for things like addition, subtraction, division, multiplication of two numbers as well...
  3. D

    Recursion with a Runnable in java

    Hi everyone Could someone show my the correct way to use a recursive runnable? The example I have involves the invokeLater method from SwingUtilities. public void mousePressed( MouseEvent e ) { Runnable runnable = new Runnable( ) { public void run( ) {...
  4. Y

    Coloring each k-th unit in a circle of n units

    suppose you write, clockwise, n numbers (or "units", doesn't matter) in a circle. you then color, clockwise, each k-th number. you do this until you've colored all n numbers, or until you've reached an already colored number. let x be the number of colored numbers. i've figured that if...
  5. topsquark

    MHB Looking for a recursion relation

    I don't know how to do a search for information on a specific equation. It's f(n + 1) = 2 - \dfrac{d(n)}{f(n)}, where d(n) is more or less arbitrary. It came up in some work I've been doing and I can't seem to get anywhere with it. Being non-linear it may not even have a closed form solution...
  6. shivajikobardan

    Confused about recursion in python-depth first search-:

    # Python dictionary to act as an adjacency list graph = { '7' : ['19','21', '14'], '19': ['1', '12', '31'], '21': [], '14': ['23', '6'], '1' : [], '12': [], '31': [], '23': [], '6' : [] } visited = [] # List of visited nodes of graph. def dfs(visited, graph, node): if...
  7. C

    Comp Sci Complexity for generating strings of length k from CNF grammar

    Here's the following code I've written for generating strings of length k given a CNF grammar ( Chomsky Normal Form grammar ) ( The code is a recursive variant of the CYK algorithm ). The algorithm is recursive and uses memoization. def generate_language(rule_dict, start_var, k): mem =...
  8. C

    Comp Sci Validating Braces Placement for Expression Evaluation

    Here's what I've done: Mentor note: replaced icode tags with code=python and \code pair. def valid_braces_placement(s, L): if len(L)==0: return False string = '' for element in L: string = string + str(element) D = ['+','-','*'] return...
  9. coolul007

    B What Are Solutions for Universal Linear Recursions?

    https://www.testsite.cocoams.org/linrec.pdf
  10. C

    DP: proving existence of optimal substructure for "Sherlock and Cost"

    I was attempting to solve the "Sherlock and Cost" problem from HackerRank using DP: But before I went to come up with a recursive relation, I wanted to find if the problem possesses an optimal substructure, and I was following these steps as written at CLRS book: Mentor note: Inline images of...
  11. B

    How to write basic syntax for triangle recursion?

    Hi, I'm new to programming in python [total beginner in programming] and I would like to ask you for your help. Here is what I got so far: import numpy as np import random from math import sqrt p = np.array([(0, 0), (1, 0), (1, (1/sqrt(2)))], dtype=float) t = np.array((0, 0)...
  12. A

    Comp Sci Using Recursion to Calculate (n + r)/(n * r)

    I wirte code but it does not work. I entered n=5 and r=2, result is 0. And I want to calculate this recursively. #include<stdio.h> int func(int n, int r); int main(){ int n,r; int result=0; printf("Enter the number:\n"); scanf("%d",&n); printf("Enter the 2.number:\n")...
  13. A

    Recursively calculate the standard deviation

    #include<stdio.h> #include<math.h> double foo(int n, int mean){ double square; if(n==1){ return(1); } if(n!=0){ square=pow(n-mean,2); return( (sqrt(square)+foo(n-1,mean))/(sqrt(n-1)) ); }} int main(){ int num; double mean; int i; int...
  14. A

    Comp Sci Why Does Using an Uninitialized Pointer Cause a Segmentation Fault in Recursion?

    double foo(int arr[], double *ave, int index){ double *s; *s=*ave; // calculation// return(foo (arr,ave,index)); // other calculation// } I want to keep the ave value during the recursion, because after ave is calculated, I will do another calculation is recursively in this...
  15. A

    Comp Sci Calculating a math formula using void function-recursion in C

    how can i write a function that calculate math formula using void function-recursion in C?
  16. G

    MHB Sequence - inhomogeneous recursion

    I need some help with this task. My theory book only shows examples of how to solve sequences in the form : 𝑎𝑘 = A * 𝑎(𝑘−1) − B * 𝑎(𝑘−2). But I've no idea how to solve this task because of the alternating term. I've included the Answer (called "Svar") to the task.
  17. E

    Proof with recursion and logarithms

    Homework Statement: Suppose f(n) is a function that accepts an integer n as a parameter. When called with n = 1, it executes 2 instructions. When called with a larger value of n, it executes 10n + 30 instructions, two of which are f(n/2). Prove that f(n) executes 10n lg n + 32n − 30...
  18. bhobba

    Insights Recursion in Programming and When to Use or Not to Use It

    Continue reading...
  19. N

    Crossword Puzzle Generation Algorithm

    Hey all, for a dictionary app I have to code I have to implement as crossword game as a side feature, unfortunately this is compulsory, I can't figure out a good way of finding words that intersect each other (esp words that intersect multiple others) without a hell of a lot of goto and while's...
  20. Destroxia

    I DSP: Recurrence Relations in a Linear Algebra Equation

    Hello, I've been working through some Digital Signal Processing stuff by myself online, and I saw a system that I wanted to write down as a Linear Algebra Equation. It's a simple delay feedback loop, looks like this: The (+) is an adder that adds 2 signals together, so the signal from x[n]...
  21. S

    I Y'' + y = 0 solution and recursion relation

    I've found the general solution to be y(x) = C1cos(x) + C2sin(x). I've also found a recursion relation for the equation to be: An+2 = -An / (n+2)(n+1) I now need to show that this recursion relation is equivalent to the general solution. How do I go about doing this? Any help would be...
  22. Math Amateur

    MHB The Recursion Theorem .... Searcoid, Theroem 1.3.24 .... ....

    I am reading Micheal Searcoid's book: "Elements of Abstract Analysis" ... ... I am currently focused on understanding Chapter 1: Sets ... and in particular Section 1.3 Ordered Sets ... I need some help in fully understanding Theorem 1.3.24 ... Theorem 1.3.24 reads as follows: In the...
  23. 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...
  24. 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...
  25. Kaura

    Java Java Sudoku Solving Program: Debugging Help Needed

    I am attempting to create a Sudoku Solving Program in Java This is what I have to far https://pastebin.com/raw/tgnAGKb2 I have spent close to an hour trying to debug it but to no avail Can someone more skilled than I please point me in the right direction?
  26. E

    Java Recursively sorting an array of strings w/o aux. parameter

    One of my professor's assignments is proving particularly tricky for me. It reads: "Write the method public static void sort(String[] a) that sorts the array a in increasing order. The method must be a short recursive program. Do not use quicksort or merge sort. It should be a lot...
  27. L

    Recursion in python functions -- confusion

    example code from python-course.eu def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res...
  28. L

    I Understanding BCFW Recursion: Exploring the Residue Factorization Form in QFT

    Below is a snipet from http://file:///C:/Users/Christian.Hollersen/Downloads/Britto_2011_2%20(1).pdf of Britto. Similar explanation can be found in the QFT books of Zee, Schwarz or the Scattering Amplitude text of Huang. Or any other text that covers BCFW recursion. My dumb question: how and...
  29. MarkFL

    MHB How can we prove the recursive definition of $S$ by induction?

    I was recently sent the following question via PM (which we discourage here), so I thought I would start a thread and help here (and give the OP a link to this thread). Here's the question: (a) We can observe that we may write...
  30. Hughng

    Comp Sci Unmash a string in C++ using recursion

    Homework Statement MUST USE RECURSION TO SOLVE THESE PARTS. Part A: Have a user input a string. Then display this string smashed up as follows: display the first character in the string, then the last, then the second, then the second to last, then the third... So if the string is “abcdef”, it...
  31. M

    I Recursion theorem: application in proof

    I have read a proof but I have a question. To give some context, I first wrote down this proof as written in the book. First, I provide the recursion theorem though. Recursion theorem: Let H be a set. Let ##e \in H##. Let ##k: \mathbb{N} \rightarrow H## be a function. Then there exists a...
  32. R

    Exercise on adding elements to a list

    (mentor note: moved here from another forum hence no template) This is the code with also the explanation of the exercise. There is bit of italian, but everything is clear enough. I actually solved the exercise. /* Add an element of value n before each element of the list that satisfies the...
  33. petrushkagoogol

    Recursion: Avoiding Stack Overflow Errors

    Upto how many levels of recursion can be used in an algorithm to avoid stack overflow error ?
  34. FallArk

    C/C++ How can I create a recursive function to mimic long division in C++?

    When I do things like cout << 1/3; in C++, it will typically output 0.333333, but the actual answer should be 0.3333333 with an infinite amount of 3s, how should I make a function such that will mimic this division recursively?
  35. FallArk

    C/C++ Help with this recursion function in C++

    I need to make a piece of code that reverse a string user input. My solution: #include <iostream> #include <string> using namespace std; string reverseMe(string tmp) { if (tmp.length() == 1) { return tmp; } else { reverseMe(tmp.substr(1, tmp.length())); }...
  36. wololo

    Efficiently Finding Cycles in a Graph: A Scientific Exploration

    Homework Statement Homework Equations Recursion, graphs, DFS The Attempt at a Solution To try to solve this algorithm, I first need to find all the basic cycles in the Graph G. When I have these cycles, I can simply pick the smallest edge in each of them and add them to the set F, while...
  37. tommyxu3

    Calculating Horse Moves in Chinese Chess

    I wrote a recursive function to calculate the number of the way for "horse" to move from one point to another in Chinese Chess in the following, but I cannot get the correct answer. My idea is to sum up the other 8(or less than 8) points' way toward the target. Thanks for any opinions in...
  38. S

    How to solve a recursion relation with a constant using hints?

    I have the recursion relation ##y_{k}=k(2j-k+1)y_{k-1}## and I would like to solve it to obtain ##y_{k}=\frac{k!(2j)!}{(2j-k)!}##. Can you provide some hints on how I might proceed? P.S.: ##j## is a constant.
  39. M

    Bloch Function Recursion Relation of Fourier Components

    Homework Statement This is just a problem to help me understand. Determine the dispersion relations for the three lowest electron bands for a 1-D potential of the form ##U(x) = 2A\cos(\frac{2\pi}{a} x)## Homework Equations I will notate ##G, \,G'## as reciprocal lattice vectors. $$\psi_{nk}(x)...
  40. S

    Implementing Recursion Function w/o FORTRAN 90 Built-in

    I understand that FORTRAN 90 has a built-it recursion function. How could I implement this function without using the built in recursion function? PROGRAM RECURSIVE_FACT IMPLICIT NONE INTEGER, PARAMETER :: M = 100 DOUBLE PRECISION :: fact INTEGER :: I PRINT *...
  41. ognik

    Investigating a Parabolic PDE algorithm

    Homework Statement Hi - I'm on the last chapter of this book and am a bit stuck. I am given a very basic fortran program (code attached in the zip file) and asked to 'investigate its accuracy and stability, for various values of Δt and lattice spacings'. The program is an implementation of the...
  42. ognik

    Derive characteristic equation recursion relation

    Homework Statement Given an NxN symetric tri-diagonal matrix, derive the recursion relation for the characteristic polynomial Pn(λ) Homework Equations Pn(λ) = |A -λI | Pn(λ) = (An,n - λ)Pn-1(λ) - A2n,n-1Pn-2(λ) The Attempt at a Solution This was easy to do by induction, but I am always...
  43. ognik

    Legendre polynomials in the reverse direction

    I have just written a program to calculate Legendre Polynomials, finding for Pl+1 using the recursion (l+1)Pl+1 + lPl-1 - (2l+1).x.Pl=0 That is working fine. The next section of the problem is to investigate the recursive polynomial in the reverse direction. I would solve this for Pl-1 in...
  44. evinda

    MHB Exploring the Cost of a Recursion Tree

    Hi! (Wave) According to my notes: $$T(n)=T\left(\frac{n}{2} \right)+T\left(\frac{n}{4} \right)+T\left(\frac{n}{8} \right)+n$$ Th recursion tree is this: https://www.physicsforums.com/attachments/3626 Cost per level $i \to \left( \frac{7}{8} \right)^{i-1}n, i \geq 1$ Leaf per level $i \to...
  45. Shackleford

    What is the recursive formula for the sequence sn?

    Oddly enough, I don't remember doing a problem like. I have had a problem where I've been given the explicit formula and then asked to use induction to prove that it's correct. I think that I'm supposed to back-substitute sn into the recursion formula and go from there.
  46. L

    Solving Recursion Trees with Log Properties of a Constant

    Hi, I'd like to know the log properties when they are the power of a constant. I've searched everywhere but I can't find it. the reason I want to know it is that, when solving a recursion tree problem, my teacher got an result of n^(log4 3) but I got 3^(log4 n). the base of the log haven't...
  47. gfd43tg

    String reversal using recursion

    Homework Statement Write a function called reverse that uses recursion to reverse any one-dimensional string array.Homework Equations The Attempt at a Solution function out = reverse(str) if length(str) == 0 out = str; else out = [str(end) reverse(str(1:end-1))]; end I am having...
  48. J

    Hydrogen Radial Equation: Recursion Relation & Laguerre Polynomials

    I'm in the first of 3 courses in quantum mechanics, and we just started chapter 4 of Griffiths. He goes into great detail in most of the solution of the radial equation, except for one part: translating the recursion relation into a form that matches the definition of the Laguerre polynomials...
  49. R

    Lagendre Polynomials - using the recursion relation

    (1) P_{l}(u) is normalised such that P_{l}(1) = 1. Find P_{0}(u) and P_{2}(u) We have the recursion relation: a_{n+2} = \frac{n(n+1) - l(l+1)}{(n+2)(n+1)}a_{n} I'm going to include a second similar question, which I'm hoping is solved in a similar way, so I can relate it to the above...
  50. J

    Converting a recursion to a loop

    public static int function(int n, int a, int b){ if (n>0){ if(b==0) return a; else return function(n-1,a,function(n,a,b-1)); } return b; } I have a recursive function of this form, how do I convert it to a loop?
Back
Top