# What is Recursion: Definition + 120 Threads

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
1. ### 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. ### 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. ### Java 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. ### 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. ### 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. ### Python 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. ### 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. ### 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. ### B What Are Solutions for Universal Linear Recursions?

https://www.testsite.cocoams.org/linrec.pdf
10. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### Insights Recursion in Programming and When to Use or Not to Use It

Continue reading...
19. ### 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. ### 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. ### 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. ### 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. ### 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. ### [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. ### 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. ### 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. ### Python 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. ### 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. ### 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. ### 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. ### 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. ### Recursion: Avoiding Stack Overflow Errors

Upto how many levels of recursion can be used in an algorithm to avoid stack overflow error ?
34. ### 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. ### 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. ### 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. ### 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. ### 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.

45. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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?