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.
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...
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...
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( )
{...
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...
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...
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 =...
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...
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...
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)...
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")...
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...
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.
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...
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...
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]...
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...
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...
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...
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...
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?
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...
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...
Below is a snipet from http://file:///C:/Users/Christian.Hollersen/Downloads/Britto_2011_2%20(1).pdf [Broken] 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...
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...
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...
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...
(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...
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?
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()));
}...
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...
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...
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.
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)...
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 *...
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...
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...
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...
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...
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.
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...
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...
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...
(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...
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?