:  ; linear recursion (define (factorial n)   (if (= n 1)       1       (* n (factorial (- n 1)))))  ; tail recusive: ; linear iterative process:  (define (alt-factorial n [counter 1] [product 1]                        (if (&gt; counter n)                            product                            (alt-factorial n (+ counter 1) (* product counter)))))   (* n (factorial (- n 1))) This return statement multiplies the recursive call with n whereas this return statement: (alt-factorial n (+ counter 1) (* product counter)), with the help of a counter and product variable, is able to put all the calculation within the recursive call. Is this what makes it a tail call and is this all there is to it? Does it not matter that it is using variables because the compiler optimizes to simply use the return value in the next call? Sorry if this question is scattered I'm just having a hard time grasping the concept.
28133
Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean exactly?
114610
I have the following recurrence that I've been pounding on:  $$ a(0)=1\\ a(1)=1\\ a(2)=2\\ a(2n)=a(n)+a(n+1)+n\ \ \ (\forall n&gt;1)\\ a(2n+1)=a(n)+a(n-1)+1\ \ \ (\forall n\ge 1) $$  I don't have much background in solving these things, so I've been googling around looking for different techniques. Unfortunately, I haven't been able to correctly apply them yet. So far I've tried:   Characteristic equations Generating functions Plugging it into Wolfram Alpha Telescoping Observation   I'm sure that one or more of these is the way to go, but my biggest problem right now is figuring out how to deal with the idea that there are different equations for odd and even values of $n$. I'm not necessarily looking for a solution (though it would be gratefully accepted), but any nudges in the right direction would be much appreciated.    To follow up, it turned out that the speed problem described in my comment, below was related to the Decimal implementation in Python 2.7. Switching to Python 3.3 (and Java) made everything many orders of magnitude better.
81954
Is there any way I can 'undo' the factorial operation? JUst like you can do squares and square roots, can you do factorials and factorial roots (for lack of a better term)?   Here is an example: 5! = 120.  Is there a way I can work out the number that must be factorialed (??) to give the answer 120?
18220
I'm writing some cross-platform code between Windows and Mac.  If list::end() "returns an iterator that addresses the location succeeding the last element in a list" and can be checked when traversing a list forward,  what is the best way to traverse backwards?  This code workson the Mac but not on Windows (can't decrement beyond first element):  list&lt;DVFGfxObj*&gt;::iterator iter = m_Objs.end(); for (iter--; iter!=m_Objs.end(); iter--)// By accident discovered that the iterator is circular ? { }   this works on Windows:  list&lt;DVFGfxObj*&gt;::iterator iter = m_Objs.end();     do{         iter--;     } while (*iter != *m_Objs.begin());   Is there another way to traverse backward that could be implemented in a for loop?
107048
If ${n \choose 3} + {n+3-1 \choose 3} = (n)_3$, compute $n$.  Just making sure I am on the right track...  Do I expand each piece out and solve algebraically?
102358
I have an assignment problem that i have been fighting with for a while now..   I have this recursive function:  $$a_n=\begin{cases} 3,&amp;\text{if }n=0\\ 5,&amp;\text{if }n=1\\ 4a_{n-1}-4a_{n-2},&amp;\text{if }n\ge 2\;. \end{cases}$$  We define the generating function $$P(n)=\sum_{n=0}^\infty (a_n+a_{n+1})x^n$$  Now I need to use the definition of $a_n$ in the recursive function to show that $$P(n)=\frac{8-19x}{(1-2x)^2}$$  I cant really get to this result, and I have been trying all sorts of things by now, nothing really leading me anywhere..  I hope some of you can help me!  Thanks
74226
I am trying to find the formula for the number $f(n,k)$ which is defined as the number of $k$-subsets of $[n]$ in which no two elements are consecutive numbers in $[n]$.  From the simple thinking I had made up following recursion:  $$f(n,k) = f(n-1,k) + f(n-2, k-1) $$  This is true since I can construct without last element of $[n]$ then make up $k$-subsets, then otherwise must contain the last element of $[n]$ then construct remaining $k-1$ elements among $[n-2]$ since with the last one, I can't use $n-1$.  However, I had never learned any techniques regarding changing those recursion into a well-summarized formula in terms of $n$ and $k$.  Any guidance would be appreciate.
76946
What are recursive triggers? How can we control them, or prevent infinite recursion?  Are these any risks inherent in them, and any limits that we should be aware of?  Please explain with an example.
5620
I understand Big-O notation, but I don't know how to calculate it for many functions. In particular, I've been trying to figure out the computational complexity of the naive version of the Fibonacci sequence:  int Fibonacci(int n) {     if (n &lt;= 1)         return n;     else         return Fibonacci(n - 1) + Fibonacci(n - 2); }   What is the computational complexity of the Fibonacci sequence and how is it calculated?
15114
Consider a function such that it takes in polynomial function and creates an array of its outputs and then using that array creates another new array by calculating the absolute difference between the first $2$ values and keeps doing this until it reaches an array full of zeros.    This is much easier to show you by example.  For example take $F(x)= x^2$, the first array would be   $1,4,9,16,25,36,49,64,81$ and so on, the second would be  $3,5,7,9,11,13,15,17,19$ ( the difference between the first value and the second one)  but the third one is where it gets interesting as if we continue the pattern we would get an array filled with only $2$'s and after that it would only be zeros.  Lets do another example, $F(x)=x^3$  $1,8,27,64,125,216,343$  $7,19,37,61,91,\dotsc$ but here is the interesting part if we continue this   $12,18,24,30,\dotsc$ and once more then we get   $6,6,6,6,6,\dotsc$ after that it would just be an array of zeros  There are $2$ main observation that I made about this  Firstly, the value that is begin repeated indefinitely is equals to the factorial of the functions power. Meaning that for $F(x)=x^2$ the value being repeated is $2!$. For $F(x)=x^3$ , it's $3! $ and this is true for all polynomials (I tried it up to $x^7$, after that it got too messy)  Secondly, the value that is repeated always occurs on the $n$th iteration of the function. Meaning that for $F(x)=x^2$, we have to go through the processes $2$ times before we find the value. For $F(x)=x^3$, we have to go through it $3$ times before getting the value.  Is there any way to prove this and does this mean anything at all?
84974
int fn();  void whatever() {     (void) fn(); }   Is there any reason for casting an unused return value to void, or am I right in thinking it's a complete waste of time?  Follow up:   Well that seems pretty comprehensive.  I suppose it's better than commenting an unused return value since self documenting code is better than comments. Personally, I'll turn these warnings off since it's unnecessary noise.    I'll eat my words if a bug escapes because of it...
29076
I have a Recurrence: $$a_{0}=1$$ $$  a_{n}=\sum_{k=0}^{n-1}(n-k)a_{k}$$ I have evaluated some a's:$a_{0}=1, a_{1}=1,a_{2}=3,a_{3}=8,a_{4}=21,a_{5}=55,...$. In the previous exercise on had to derive a generating Function for the even indexted Fibonacci Numbers. So these are definitely $F_{0}=1,F_{1}=1,F_{2}=3,F_{3}=8,F_{4}=21,...$   Then I had a detailed look on the summation: $$a_{0}=1$$ $$a_{1}=(1-0)*1=1$$ $$a_{2}=(2-0)*a_{0}+(2-1)*a_{1}=2*1+1*1=3$$ $$a_{3}=(3-0)*a_{0}+(3-1)*a_{1}+(3-2)*a_{2}=3*1+2*1+1*3=8$$ $$a_{4}=(4-0)*a_{0}+(4-1)*a_{1}+(4-2)*a_{2}+(4-3)*a_{3}=4*1+3*1+2*3+1*8=21$$  Its obviously linked to:    But i dont see how to proceed.
29669
If each term $a_k$ is either 0 or 1, how many sequences are there $a_1, a_2, \cdots$ , $a_n$ such that    $$a_1 \leq a_2 \geq a_3 \leq a_4 \cdots?$$   If we let $f_n$ be the number of ways for a n-term sequence, we can get a recursive formula.   Suppose $a_1=1$. Then $a_2=1$ and $a_3=0,1$ which is actually $f_{n-2}$.  Suppose $a_1=0$. If $a_2=1$, we get $f_{n-2}$ by similar reasoning. If $a_2=0$, $a_3=0$ so the cycle repeats. Thus the # of ways in this case is $f_{n-2}+f_{n-4}+f_{n-6}+\cdots$.  So the recursive formula will be $$f_n=2f_{n-2}+f_{n-4}+f_{n-6}+\cdots$$ and $f_1=2, f_2=3$. How do I get a closed form, or did I find the wrong recursive relation?
38364
I want to calculate $u_1, u_2,\ldots,u_n$.  Can anyone help me to define this recursive series: $u_{n+1}=\sin(u_n)$ with $u_0=1.5$ without proc or loops?
90761
A curiosity that's been bugging me. More precisely:     Given any integers $b\geq 1$ and $n\geq 2$, there exist integers $0\leq k, l\leq b-1$ such that $b$ divides $n^l(n^k - 1)$ exactly.   The question in the title is obviously the case when n = 10. This serves as a motivating example: if we take b = 7 and n = 10, then k = 6, l = 0 works (uniquely), and if we calculate $\dfrac{n^k - 1}{b}$, we see that it turns out to be 142857 - the repeating part of the decimal expansion of 1/7. A (very sketchy, but correct!) sketch proof, which I've included for completeness:   Notice that $\dfrac{1}{99\dots 9} = 0.00\dots 01\; 00\dots 01\; 00\dots 01\dots$. Notice that $1/7$ must have either a repeating or a terminating decimal expansion: just perform the long division, and at each stage you will get remainders of 0 (so it terminates) or 1, 2, ..., 6 (so some of these will cycle in some order). It turns out the decimal expansion is repeating, and the 'repeating part' is 142857. This has length (k=)6. $\dfrac{1}{10^6 - 1} = 0.000001\;000001\dots$, so $\dfrac{142857}{10^6 - 1} = 0.142857\;142857\dots = 1/7$, and so $7\times 142857 = 10^6 - 1$. And we can do the same thing with $\dfrac{1}{10\dots 0} = 0.00\dots 01$ and terminating decimals. And the same proof of course holds in my more general setting.   But this (using the long division algorithm after spotting an unwieldy decimal expansion) feels a little artificial to me, and the statement is sufficiently general that I'm sure there must be a direct proof that I'm missing. Of course, the $n^k$ part is easy, but the $n^k-1$ part has me a little stumped. My question is: is there a direct proof of the latter part?  Thanks!
26684
I want to have a function that will return the reverse of a list that it is given -- using recursion. How can I do that?
90018
I am using this simple snippet of code, variants of which I have seen in many places:  for(int k = 0 ; n % 2 == 0 ; k++)     n = n / 2;   This code repeatedly divides num by 2 until it is odd and on completion k contains the number of divisions performed.  I am wondering what the appropriate way to write this using mathematical notation is?  Does this correspond to some named concept?  Of course, $lg\ n$ gives the appropriate $k$ when $n$ is a power of 2, but not for anything else. For example, $k = 1$ when $n = 6$ and $k = 0$ when $n$ is odd.  So it looks it should be specified using a piece-wise function but there may be some mathematical concept or nomenclature here that I am not aware of...