Hi all.. I am having quite a lot of difficulty with recursion. For me it is what is happening internally at each step, what is being returned, what the internal stack looks like.. I understand the basics, the base case, like the Fibonacci sequence. Intellectually I understand depth first searches .. but I simply do not understand what is going on under the hood. I cannot make the connection between what visually is supposed to be happening, vs how the algorithm works.
This towers of Hanoi explanation should be more than sufficient, and yet, it simply leaves me overwhelmed.
I am specifically asking for a tutorial in Java - Thank you.
Videos
I'm going back to school for a second Bachelor's in CS. I just started this year. My Java class was going great for me until we hit the chapter on recursion and I just can't seem to get my head around it. Why or how.
One of our homework problems is to write a method that multiplies two integers together using recursion, and NOT using multiplication or division operators. I get that it's an exercise, and not a likely real-world situation that one would be stranded on a desert island unable to multiply, but I'm finding it super frustrating. The examples the professor talked about in class made a bit more sense to me - calculating Fibonacci sequences and factorials, so I thought I was understanding the material. Nope. Super confused.
Anyone have a better way to explain recursion and why it's useful and how to rewire my brain to think recursively?
A recursive function is a function that calls itself until it reaches a return statement, that stops it from recalling itself. Take your example, the Factorial function. Factorial is a mathematical function that returns the number multiplied by itself - 1 multiplied by itself - 2, ... multiplied by 1, example: factorial of 5 = 5! = 5x4x3x2x1 = 120. it is also equal to itself multiplied by the factorial of itself -1, which is: 5! = 5x4! Take into consideration that 0! = 1. to represent this in a Java code, you need a loop that multiplies the numbers starting from 1, and going till the number you are calculating its factorial. Further more, explaining your code, let us calculate Factorial(5): Factorial() returns an integer.
Initial Call from main(): 5 != 0, then skip the condition (n == 0); t = Factorial(5-1) = Factorial(4);
Second call from Factorial(4): 4 != 0, then skip the condition (n == 0); t = Factorial(4-1) = Factorial(3);
Third call from Factorial(3): 3 != 0, then skip the condition (n == 0); t = Factorial(3-1) = Factorial(2);
Fourth call from Factorial(2): 2 != 0, then skip the condition (n == 0); t = Factorial(2-1) = Factorial(1);
Fifth call from Factorial(1): 1 != 0, then skip the condition (n == 0); t = Factorial(1-1) = Factorial(0);
Sixth call from Factorial(0): 0 == 0, then return value 1;
First return, 1, to Fifth call (Factorial(1)): return n*t = return 1*1 = return value 1;
Second return, 1, to Fourth call (Factorial(2)): return n*t = return 2*1 = return value 2;
Third return, 2, to third call (Factorial(3)): return n*t = return 3*2 = return value 6;
Second return, 6, to second call (Factorial(4)): return n*t = return 4*6 = return value 24;
Second return, 24, to First call (Factorial(5)): return n*t = return 5*24 = return value 120;
Second return, 120, to Initial call (from main()): print(120);
Hope this helps you understand recursion.
When a call is made to another method, a stack frame is created to hold the state of the current method and it is pushed onto the stack. This is regardless of a method calling itself or another method.
When the call returns, the stack frame is popped of the stack, the state of the method is restored and execution continues in the calling method.
Recursion is when a method (directly or indirectly) calls itself. The general form of a recursive method is:
- If a parameter meets a terminating condition, return (usually a result)
- Else adjust parameters for the next iteration and call self
The code your teacher wrote has some style issues. It would be clearer if written like this:
static int factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}
Eradicating the unnecessary variable t and redundant else (there is no "else" when the "if" returns - there is merely continuation of execution)
I would write it like this, eliminating the if altogether:
static int factorial(int n) {
return n == 0 ? 1 : n * factorial(n - 1);
}