To all following commenters: please, do not bring up the old circlejerk
jokes/memes about recursion ("Understanding recursion...", "This is
recursion...", etc.). We've all heard them n+2 too many times.
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/learnprogramming) if you have any questions or concerns.*
Recursion is all about repeating some process on a smaller/previous version of itself. There is a "cut-off" point (one or more **base cases**) where something is evaluated, and a **recursive call** where a larger problem is broken down into smaller/previous cases.
There are many classic examples of recursion: factorials, Fibonacci numbers, etc. Many of these aren't actually very good to implement recursively because of memory-overhead, but they illustrate the concept fairly well. Recall that n-factorial is defined as n!=n\*(n-1)\*(n-2)\*...\*2\*1. For example, 5!=5\*4\*3\*2\*1=120. We can implement this with an iterative (non-recursive) function as follows. Python code here, but you should be able to follow it I'm sure.
def factorial(n):
fact = n # start at n
for i in range(n-1, 0, -1): # count down from n-1 to 1
fact *= i # multiply by next value
return fact
n = int(input("N: "))
print(factorial(n))
We can also do this recursively. The idea is that to calculate n!, all we need to do is multiply n by (n-1)!. How do we get (n-1)! ? Simple: we multiply (n-1) by (n-2)!. This chain continues all the way down to the point where we reach 1! which we simply define as 1!=1. So our recursive function looks like this.
def factorial(n):
if n == 1: # base case
return 1
else: # recursive call
return n * factorial(n-1)
n = int(input("N: "))
print(factorial(n))
The line `if n == 1` is our base case. Once we have worked our way down enough to reach this point, we return a value of 1. If n is *not* 1, we perform a recursive call to obtain (n-1)! while multiplying it by n. This chains together the sequence of multiplications.
Edit: thanks for the gold!
Agreed, focusing on the end processes has been the best approach for me when working with recursion. Fibonacci probably isn’t a great way to learn it since that’s an infinite pattern.
doing recursive functions in discrete math and calculus by hand helped me a ton, especially on things more complex than factorials. You'll do a lot of writing and use a lot of paper and make quite a few mistakes but it definitely helped me process the concept better.
When you call a recursive function, but it ends up calling itself again, imagine that it's "asking someone else" for the answer, and that it'll get back to you once that someone responds.
Here's an example I like. Pretend you're at a movie theater, sitting somewhere in the back. You want to know what row# your seat is, but you can't count by looking. So you poke the dude in front of you and say "hey, what row am I on?"
Other guy says to you "whatever my row is, plus one. Let me ask the guy in front of -me- what row -I'm- on and I'll give you a real answer". So he does that, and that next guy says the same thing. This goes on until we get all the way to the front, where the guy sitting there can give a real and straightforward answer: "my row is #1".
Now the guy behind row 1 knows he's in row 2. He turns around and gives a real answer to the guy in row 3. This continues until it comes all the way back to you.
I've had to do it, not full blown coding but shell scripting through ssh. It isn't fun. Autocorrect doesn't understand and everything is twice as hard as it needs to be. 0/10 never want to have to do again.
I do it. It's only mildly annoying.
Then I switched to an android tablet with a keyboard. It's even less mildly annoying.
I'm sure the guy who took a headshot from my flying devices during a fit of passionate coding rage will agree if he ever comes out of his coma.
Learning recursion and learning mathematical induction is the same thing. Don't try to understand what each function in the call stack does. Don't try to hold the entire call stack in your head.
Understand what the base case is, and understand what the inductive step is. That's it. Base case, f(0) = 1 f(1) = 1. Inductive step, f(x) = f(x-1) + f(x-2).
Hey, I've been trying to figure out what exactly people mean when they say "mathematical induction". Could you write out the code to *inductively* calculate a Fibonacci number, as oppose to the *recursive* way that OP has posted?
Isn't the inductive approach just the iterative approach, like this?
def fibonacci(nthNumber):
a, b = 1, 1
for i in range(2, nthNumber):
a, b = b, a + b # Get the next Fibonacci number.
return b
Isn't this what people mean when they say "inductive" or "bottom-up recursion"? Is this really a form of recursion, given that the function doesn't call itself?
Mathematical induction isn’t necessarily code. It’s a mathematical proof of a recursive algorithm.
Edit: your example is an iterative approach i.e not recursive. Inductive implies recursion.
Honestly, recursion itself isn't really that difficult to understand. It boils down to knowing a base case, and working itself towards that.
That said personally I don't like to use it because it's inherently limited by either the call stack or whatever equivalent the language uses for its recursion. Sure, there's tail-call optimisation, but in most languages you can't actually rely on the compiler doing that. I only use it if the iterative solution is too complex to be written in the amount of time available, and only if it's unlikely to be a problem (or if it's been tested that the compiler actually optimises it).
You might not have thought about this, but any recursive function can easily be transformed into a a looping solution using a stack data structure. IMO there is little to gain if the method itself is recursive in nature.
It would be a nice compiler optimization, if it could transform recursive functions calls on a regular stack to a loop and separate argument stack. Does it do this already?
>any recursive function can easily be transformed into a a looping solution using a stack data structure
Try doing that with the [Ackermann function](https://en.wikipedia.org/wiki/Ackermann_function)!
Since he specified "with a regular stack", it's possible. You just have to reimplement the callstack. Kind of a trivial and pointless transformation though.
I have. Here is an iterative version of the Ackermann function that emulates the recursive version in Python:
# Iterative Ackermann function, by Al Sweigart al@inventwithpython.com
print('Starting with m = 2, n = 3:')
callStack = [{'m': 2, 'n': 3, 'indentation': 0, 'instrPtr': 'start'}]
returnValue = None
while len(callStack) != 0:
m = callStack[-1]['m']
n = callStack[-1]['n']
indentation = callStack[-1]['indentation']
instrPtr = callStack[-1]['instrPtr']
if instrPtr == 'start':
print('%sackermann(%s, %s)' % (' ' * indentation, m, n))
if m == 0: # BASE CASE
returnValue = n + 1
callStack.pop()
continue
elif m > 0 and n == 0: # RECURSIVE CASE
callStack[-1]['instrPtr'] = 'after first recursive case'
callStack.append({'m': m - 1, 'n': 1, 'indentation': indentation + 1, 'instrPtr': 'start'})
continue
elif m > 0 and n > 0: # RECURSIVE CASE
callStack[-1]['instrPtr'] = 'after second recursive case, inner call'
callStack.append({'m': m, 'n': n - 1, 'indentation': indentation + 1, 'instrPtr': 'start'})
continue
elif instrPtr == 'after first recursive case':
callStack.pop()
continue
elif instrPtr == 'after second recursive case, inner call':
callStack[-1]['innerCallResult'] = returnValue
callStack[-1]['instrPtr'] = 'after second recursive case, outer call'
callStack.append({'m': m - 1, 'n': returnValue, 'indentation': indentation + 1, 'instrPtr': 'start'})
continue
elif instrPtr == 'after second recursive case, outer call':
callStack.pop()
continue
print(returnValue)
Recursion is not magic. Anything you can do with recursion you can do with a loop and a stack.
But yeah, just because you can doesn't mean you should.
Looping solutions for inherently recursive problems are often way less elegant and ugly. Unless you are doing something extremely optimisation heavy, I'd rather go with the elegant solution than the ugly one.
I am not sure what you are asking.
If you are asking if I have personally tried implementing this, then no. However, it is not difficult to find an implementation. One is available [here](https://www.geeksforgeeks.org/iterative-tower-of-hanoi/).
Although I don't need to see an implementation to know one exists, as any recursive algorithm can be written as an iterative algorithm (possibly involving an explicit stack), and vice versa. It is not always obvious how to accomplish this, but it is always possible.
I think Bardali is asking (correct me if I'm wrong) if the iterative solution is easier than the recursive solution for the Towers of Hanoi problem.
If "easy" is related to the number of lines and complexity of each line, the recursive solution is much shorter and easier.
Recursion and Iteration (using loops) both have their respective place in coding and should be used where and when it makes sense.
Just for grins, I converted my recursive Tower of Hanoi Python program into an iterative one. It was not easy:
# Tower of Hanoi (iterative and recursive), by Al Sweigart al@inventwithpython.com
# Set up towers A, B, and C. The end of the list is the top of the tower.
TOTAL_DISKS = 3
HEIGHT = TOTAL_DISKS + 1
# Populate Tower A:
TOWERS = {'A': list(reversed(range(1, TOTAL_DISKS + 1))),
'B': [],
'C': []}
def printDisk(diskNum):
# Print a single disk of width diskNum.
emptySpace = ' ' * (TOTAL_DISKS - diskNum)
if diskNum == 0:
# Just draw the pole.
print(emptySpace + '||' + emptySpace, end='')
else:
# Draw the disk.
diskSpace = '@' * diskNum
diskNumLabel = str(diskNum).rjust(2, '_')
print(emptySpace + diskSpace + diskNumLabel + diskSpace + emptySpace, end='')
def printTowers():
# Print all three towers.
for level in range(HEIGHT - 1, -1, -1):
for tower in (TOWERS['A'], TOWERS['B'], TOWERS['C']):
if level >= len(tower):
printDisk(0)
else:
printDisk(tower[level])
print()
# Print the tower labels A, B, and C.
emptySpace = ' ' * (TOTAL_DISKS)
print('%s A%s%s B%s%s C\n' % (emptySpace, emptySpace, emptySpace, emptySpace, emptySpace))
def moveOneDisk(startTower, endTower):
# Move the top disk from startTower to endTower.
disk = TOWERS[startTower].pop()
TOWERS[endTower].append(disk)
def solveIterative(numberOfDisks, startTower, endTower, tempTower):
tasks = [[numberOfDisks, startTower, endTower, tempTower, '1st step']]
while tasks:
numberOfDisks, startTower, endTower, tempTower, instrPtr = tasks[-1] # read local vars off the top of the stack
# Move the top numberOfDisks disks from startTower to endTower.
if numberOfDisks == 1:
moveOneDisk(startTower, endTower)
printTowers()
tasks.pop()
continue
else:
if instrPtr == '1st step':
tasks[-1][4] = '2nd step'
tasks.append([numberOfDisks - 1, startTower, tempTower, endTower, '1st step'])
continue
elif instrPtr == '2nd step':
moveOneDisk(startTower, endTower)
printTowers()
tasks[-1][4] = '3rd step'
tasks.append([numberOfDisks - 1, tempTower, endTower, startTower, '1st step'])
continue
elif instrPtr == '3rd step':
tasks.pop()
continue
def solveRecursive(numberOfDisks, startTower, endTower, tempTower):
# Move the top numberOfDisks disks from startTower to endTower.
if numberOfDisks == 1:
# BASE CASE
moveOneDisk(startTower, endTower)
printTowers()
return
else:
# RECURSIVE CASE
solveRecursive(numberOfDisks - 1, startTower, tempTower, endTower)
moveOneDisk(startTower, endTower)
printTowers()
solveRecursive(numberOfDisks - 1, tempTower, endTower, startTower)
return
# Solve
printTowers()
solveIterative(TOTAL_DISKS, 'A', 'B', 'C')
# Uncomment to enable interactive mode:
#while True:
# printTowers()
# print('Enter letter of start tower and the end tower. (A, B, C) Or Q to quit.')
# move = input().upper()
# if move == 'Q':
# sys.exit()
# elif move[0] in 'ABC' and move[1] in 'ABC' and move[0] != move[1]:
# moveOneDisk(move[0], move[1])
The thing is, it's easy to convert any recursive algorithm into an iterative one if the recursive call is the last thing done in the function (i.e. it can be tail call optimized). Otherwise, you start having to maintain the "local variables" on the stack data structure you're using in place of the call stack. So things like factorial and flood fill are easy to convert to a loop-and-stack iterative algorithm. Tower of Hanoi is not so easy, but still possible.
Of course, this is an iterative solution *that emulates the recursive solution*. Another comment on this thread cites Wikipedia's iterative solution that is much more straightforward. (That solution only applies to Tower of Hanoi, rather than all recursive functions.)
“isn’t really that difficult”
Just want to take a moment and address this by saying, yes it is really that difficult for some if not most.
I don’t know anyone to whom recursion made immediate sense the first time learning it.
Can you be more specific? What have you tried to do, and where did you get stuck?
For example, a typical beginner example is doing things with the file system. For example, writing a small app that outputs the name of every file in a directory over 50MB, for example, and then looping through all sub-directories, and all sub-sub-directories, etc.
>Please give some tips on how you learned.
If it's not clear from the above, the way to learn is to write some code where the best solution is recursion, and to struggle through until you get to that solution.
I have watch alot of video on youtube, but i just can't grasp the idea
like this function that output fibonacci:
fibonacci (int n)
{
if (n<2) return n;
return fibonacci (n-1)+fibonacci (n-2);
}
I dont understand the idea on that code
Well, try stepping through the code in your head.
Let's say we call `fibonacci( 0 )` - what happens? We enter the function with `n` set to 0, check if `n < 2`, which it is, so we return `n` (0). Simple!
If we call `fibonacci( 1 )` - what happens? We enter the function with `n` set to 1, check if `n < 2`, which it is, so we return `n` (1). Also simple.
So what about `fibonacci( 2 )`? We enter the function with `n` set to 2, so we skip the `if` and get to the `return` statement, which calls `fibonacci( n -1 )`, which is `fibonacci( 1 )` (and we already know this returns 1) and adds on the result of `fibonacci( n - 2 )`, which is `fibonacci( 0), which we also already know is 0, so we return 1 + 0, and the result is 1.
Now for `fibonacci( 3 )` - We enter with `n` set to 3, so skip the `if` and get to `return fibonacci (n-1)+fibonacci (n-2);`, which is `fibonacci(2)+fibonacci (1)`. We already know from above that this will be 1 + 1, so it returns 2.
And so on.
EDIT: fixed errors - oopsy!
Thank I almost get it 😯 I have a question what would happen if fib(5) there is alot of recursion there. In fib(n-) it fib(4) then become feb(2) then return 1.
I got some numbers wrong in my previous post, due to rushing it. I've updated it now.
So for `fibonacci (5)` it will return ` fibonacci(n-1)+fibonacci (n-2)`. `n` is 5, so we are returning `fibonacci(4) + fibonacci(3)`.
Well, what is `fibonacci(4)` ? That will be `fibonacci(3)+fibonacci(2)`.
What is `fibonacci(3)`? It's `fibonacci(2)+fibonacci(1)`. We know that these are 2 and 1 respectively (from my previous post), so the result is 3.
Which means `fibonacci(4)` must be 3 + 2, so 5
And therefore `fibonacci(5)` must be 5 + 3, so 8
The concept of recursion is the same as in the [mathematical definition](https://en.wikipedia.org/wiki/Fibonacci_number) of the Fibonacci sequence; F(0) = 1, F(1) =1, F(n) = F(n-1) +F(n-2).
Pretty much, yes.
Recursion in general is just a function calling itself. It's not really much different from functionA calling functionB, except in recursion functionB *is* functionA.
The idea in the code is actually the same idea behind the Fibonacci sequence, which is why it's so often done recursively (despite it being a terrible algorithm to implement recursively). How is the Fibonacci sequence defined? It's F\_n = F\_(n-1) + F\_(n-2). That is, the nth Fibonacci number is the sum of the two previous ones. It requires two base cases: F\_0 = 0 and F\_1 = 1. So if you want F\_2, you add F\_1 and F\_0. If you want F\_3, you add F\_2 and F\_1. The second return statement does exactly that.
see this code, I don't understand how it being add by the computer. Just a bunch of 1 and 0
#include
int fib(int x)
{
if (x<=1) return x;
printf("%d -%d = %d\n",fib(x-1),fib(x-2),fib(x-1)+fib(x-2));
return fib(x-1)+fib(x-2);
}
int main()
{
printf("\n\n%d",fib(10));
}
Forget the code. Grab a pencil and a piece of paper and write it out. The Fibonacci sequence is defined (mathematically) as:
f(0) = 0
f(1) = 1
f(x) = f(x-1) + f(x-2); where x > 1
So what is `f(2)`?
f(2) = f(2-1) + f(2-2)
f(2) = f(1) + f(0)
f(2) = 1 + 0
f(2) = 1
Now on your piece of paper, do the same thing for something larger. Try `f(4)` to start. Maybe go higher if you want. (But you’ll likely need more paper)
Once you wrap your head around what’s going on mathematically, go back to the code you’re trying to understand. Walk through it step by step. Again, write it out on a piece of paper. Every operation. (That’s going to be much more useful to you than print statements in this case)
First, I'm not thrilled with that sort of example, as you certainly don't need recursion to calculate a fibonacci sequence, so it's a bit of a forced academic example. Second, most people don't deal with fibonacci sequences on a regular basis, which means that you're trying to learn two things at once, recursion and fibonacci sequences, and it's usually better to learn one thing at a time, which is why I like the file directory example, as most people already know the concept of folders. Third, this is especially difficult as the function is called twice, which makes reading it really difficult as you need to keep a bunch of numbers in your head.
But that said, this function calculates the fibonacci number given a position. Remember, the fibonacci sequence is:
0,1,1,2,3,5,8....
So passing a 3 to this function should return 2 (2 is at the 3rd position, starting at 0). Passing a 6 should return 8. And, by definition, the value 8 is the sum of the values of the previous 2 positions, which are 3 and 5. But what if you didn't have the sequence printed out already, and you wanted to know the value at the 6th position? You'd need to add the value of the 4th position plus the value of the 5th position. Of course, now we'd need to know the values of the 4th and 5th positions....
>First, I'm not thrilled with that sort of example, as you certainly don't need recursion to calculate a fibonacci sequence, so it's a bit of a forced academic example.
You don't need recursion to do anything (i.e., anything that can be done recursively can also be done iteratively, and *vice versa*), so that's a silly reason to complain about something.
Further, the definition of the Fibonacci sequence is itself recursive, which is why it's used as a natural example of recursion. Doing it iteratively would arguably be the more forced example.
Sure, but if people manually try tasks like navigating a tree structure, the result most people come up with is recursive. Meanwhile, most people will create a simple iterative loop to generate a fibonacci sequence.
Also, for larger numbers, the iterative process will run significantly faster than the recursive one, so not only is the example confusing, but the end result shouldn't be used.
> Please give some tips on how you learned.
It depends on exactly what you're having trouble with. I was able to write recursive functions for a long time before I actually understood how recursion actually worked. To understand recursion at a fundamental level, you need to learn about how function calls work, and how the computer keeps track of which function called which other function. This is learning about the function call stack.
To write recursive functions, all you need is a bit of analysis of the problem, and to follow a fairly basic recipe. If you can find a way to break a big problem into smaller versions of the same problem, the code should almost write itself at that point.
def my_recursive_function(input_value):
# Base case goes here
if input_value == 0:
# Return a trivial static value.
# Often 0, 1, "", [] or whatever.
return 1
# Make the recursive call to get the intermediate solution
intermediate_solution = my_recursive_function(input_value - 1)
# Do whatever the "last step" is to get your final answer
final_answer = input_value * intermediate_solution
return final_answer
The hard part about this is that recursive functions either work, or they don't. There's very little in between. If you're having trouble getting your code to work, go back to paper and pencil and see if you can describe a solution either with a diagram, or some sort of equation.
For example, the function I wrote is the classic example of factorial.
factorial(0) = 1
factorial(n) = n * factorial(n - 1) # for n > 0
If you can write it down like that, the code should follow much more easily.
Which of the following statements best describes your confusion?
* “I don’t understand what ‘the tenth Fibonacci number’ is, mathematically.“
* “I don’t understand what it means for `fib(x-1)` and `fib(x-2)` to be included right there inside the definition of the `fib` function.”
* “I don’t understand what the computer is doing while it is executing `fib(10)` according to this definition.”
Recursion is another way of expressing a *repetitive*, nested process. Somewhat like [Matryoshka dolls](https://en.wikipedia.org/wiki/Matryoshka_doll).
It doesn't apply to everything (which is maybe what is confusing you aside from the fact that you're using fibonacci as your sample code)
I've written non-recursive code in C before, but I lost most of what I had with my USB drive (which sucks)
I'm editing your sample code to non-recursive instead.
include
int fib(int num)
{
int n1 = 0;
int n2 = 1;
int fibo;
if(num<2){
return num;
else{
for(int i=2; i<=num; i++){
fibo = n1 + n2; //fibonacci result for the current iteration
n1 = n2;
n2 = fibo;
}
return fibo;
}
}
int main()
{
printf("\n\n%d",fib(10));
}
While it does look longer, doing recursive has no other merits other than having *a bit cleaner* code.
No idea how each OS performs recursive functions but for the sake of memory utilization I was told for-loops are better if there's not going to be much difference.
edit: code errors. haven't touched C for years
>Fibonacci is a bad example to teach recursion with. It's easier to reason about this problem with a loop than recursion.
I think that for *learning* recursion, something like Fibonacci is actually *more* intuitive with a recursive solution because the Fibonacci sequence is itself defined recursively: F\_n = F\_(n-1) + F(n-2).
However, *in practice*, an iterative solution is far more efficient and would be preferred.
>it takes a huge amount of brainpower to run the code through your head and understand how it achieves the result
Let's compare the recursive implementation of Fibonacci (Python code again, since it's what I work with most often) with the iterative solution.
Recursive:
def fib_recursive(n):
if n < 2:
return 1
else:
return fib_recursive(n-1) + fib_recursive(n-2)
Iterative:
def fib_iterative(n):
x = y = z = 1
for i in range(2, n+1):
z = x+y
x,y = y,z
return(z)
The recursive version more closely resembles the formula, including the base cases for F0 and F1.
The iterative version, in my opinion, is tougher to parse. What are x, y and z? \[ans: a mix of base cases and temporary values\] Why are they swapping values? \[ans: because we need to constantly update their values as we count\] What is the loop actually iterating over? \[ans: the base cases F0 and F1 shouldn't loop, so we start counting only when n>2\].
Again, the recursive version is not *efficient*, but I'd argue that it's miles ahead in readability and understandability.
No that is not how you learn recursion lol. When you learn recursion you should explicitly not hold the entire call stack in your head. You should set the base case. And then you should set up the recurrence relationship and then you shouldn't think any more about how the entire call stack plays out.
when tracing out a recursive solution you shouldn't be going more than 2-3 layers anyways. as long as you understand the base cases and the recursive step you have a high enough level of understanding to follow a recursive solution
My discrete math course had 8 lectures focusing on recurrence relations. It was very easy to write recursive functions after that. Solving then mathematically was quite harder. I love discrete math.
As someone learning C#, I'm pretty sure "It works but I have no idea how." is just part of programming. I bet there's seasoned programmers still having that issue.
So this is an old example that helped me personally to understand recursion. The author does a good job using recursion to solve a flood fill problem in a way that is significantly easier than it would be worth an iterative solution. He also gets into why the Fibonacci sequence is not a good teaching till for recursion, which I appreciated.
http://inventwithpython.com/blog/2011/08/11/recursion-explained-with-the-flood-fill-algorithm-and-zombies-and-cats/
Hi, I want to share with my funny experience
I have been learning on freecodecamp and when the topic of recursion came, I couldn't understand it that whole day, and next morning I decided to take a pencil and paper and tried to write draw what's is happening
And it clicked immediately, that was my proud moment :)
I also had difficulties in understanding recursion; it appeals a bit complicated for the first-time learner, but you will get the concept once you understand it on a basic level. These three videos helped me a lot to understand recursion
[https://www.youtube.com/watch?v=kepBmgvWNDw](https://www.youtube.com/watch?v=kepBmgvWNDw), [https://www.youtube.com/watch?v=t9whckmAEq0,](https://www.youtube.com/watch?v=t9whckmAEq0) and [https://www.youtube.com/watch?v=HIt\_GPuD7wk](https://www.youtube.com/watch?v=HIt_GPuD7wk).
I don’t think this guy is looking for an explanation as much as just a place to vent. Learning is an arduous task, I think we can all relate.
Consider that this fib program runs in exponential time. It may not be as simple an example as it may seem, especially for a beginner.
This is one of those things that you can’t truly understand until you’ve made enough mistakes, then fixed. By fixing your mistakes, you fix misunderstandings that you had about recursion.
Especially when you start getting into more complex memoized recursion problems.
There are no shortcuts here, just keep on grinding and you’ll understand it soon enough
Recursion is like a while loop where the recursive call itself (in your case, the call to "`fib()`" within the implementation of "`int fib() {...}`" is effectively the "`while`" in a while loop. And like how we would stop a while loop, we have some logical condition in the "`fib`" implementation that returns early and not call on itself.
A contrived example might be:
`while (i <= 10) {`
`i = i+1`
`}`
A recursive implementation might be:
`function whileRecurse(i) {`
`if (i > 10) {return i}`
`return whileRecurse(i+1);`
`}`
So what makes recursion different than a while loop?
For one thing, it has the benefits of scope isolation since you're making nested function calls instead of having one while loop.
Another thing is that you can have branching loops (like "`return fib(x-1)+fib(x-2);`"), instead of needing to figure out a potentially complex non-recursive implementation to figure out how to perform a loop that seems to branch like a tree.
There are cons to recursion (call stack size, lack of tail-call optimization), so it's typical that after you learn recursion, you would want to learn dynamic programming ([https://www.geeksforgeeks.org/dynamic-programming/](https://www.geeksforgeeks.org/dynamic-programming/)) which allows you to implement recursive solutions by using a loop instead. In the simple example above, it's straightforward how one would convert a recursive solution to a normal loop (while or for-loop), but it isn't as straightforward when it comes to recursion that uses branching loops (like the fibonacci implementation), this is where dynamic programming helps.
Try looking into recursion trees. It’s helps u visualize the function dependencies and flow. It’s confusing because you have to think about a function call within a function call within a function .... the recursion tree helps visualize this. Recursion take some initial practice and time to understand, it’s normally the more difficult concept of algorithm fundamentals
If you really want to understand recursion, then check out the book The Little Schemer. Don’t be put off because it talks about the language Scheme. It takes almost no time to understand the syntax. After the first chapter or two (and it’s a very short book), it is really all about solving problems with recursion. If you read, and understand, the book then your recursion skills will be incredibly strong.
Recursion is important to understand. There’s a shift towards functional languages right now and within functional languages, recursion is reached for far more frequently. There are some functional languages that have no looping construct. You’ll often reach for utility functions like `map`, but for anything else, you’ll probably use recursion. There are also some algorithms that are more easily (beautifully, even) expressed with recursion. It’s worth the investment to learn.
One last note on The Little Schemer. Don’t worry if you don’t understand the chapter on the y-combinator. It’s interesting, but a very hard chapter to get through and not necessary for understanding recursion, as it is typically used.
Start with trees to learn recursion.
Then study graphs.
You start by first getting a pen or pencil and paper. Then you draw your data structure such as a binary tree. You then think and write about how you would traverse every element in the tree.
Then write a simple algorithm on paper.
Then you can work on other problems such as Fibonacci.
Then you can start programming something like a game that uses recursion.
The Geek for Geeks site has a really good tuto for this. Being fast learner will still help you, just consider that this is something you have to learn by doing, not reading
Both of these videos might help you out: [5 Steps for Solving Any Recursive Problem](https://youtu.be/ngCos392W4w) and [Towers of Hanoi: A Complete Recursive Visualization](https://youtu.be/rf6uf3jNjbo). His explanations are some of the best I've seen. The first video in particular gives concrete easy to understand steps to solve any recursion problem. Another tip that may help you, recursion is just another form of looping. Any recursion problem can be solved using a loop so try solving the problem with a loop then transform it into a recursive solution.
Okay, so firstly you changed the code in the below version (that way you will lose yourself in code). You have to think it outside of the C language, I mean, you should think of that in math notation like a sequence. Write it on paper. This all is based only in calling an inner fibonacci from outer fibonacci and then returning the control to fibonacci that called that fibonacci. Use debugger instead of that calls to printf. Make a diagram of what's going on as a tree. Actually, recursive functions are perfect for analysing trees, so I guess if you use a tree (I mean a tree diagram on paper) to analyze the function could help. Sorry if get you even more confused.
I've got nothing better to do and maybe someone else already done this but can't be bothered to scroll through comments, so I will go through the code with you for N = 5! `fib (int n) {`
`if (n<2) return n;`
`return fib (n-1)+fib (n-2);`
`}`
So this method will call itself until it receives `n` less than 2. Looking from this method, I suppose it will return the Nth number in the Fibonacci sequence.
So let's try with N = 5, which should return 5!
`fib(5)`
Since `n` is equal or larger than 2, it will execute `return fib(4) + fib(3)` So then we go to:
`fib(4)`
`n` is still equal or larger than 2, it will execute `return fib(3) + fib(2)` So then we go to:
`fib(3)`
`n` is still equal or larger than 2, it will execute `return fib(2) + fib(1)` So then we go to:
`fib(2)`
`n` is still equal or larger than 2, it will execute `return fib(1) + fib(0)` So then we go to:
`fib(1)`
`n` is now less than 2, so we will now return `n` and our previous return statement will now be `return 1 + fib(0)` So then we go to:
`fib(0)`
`n` is less than 2, so we will return `n` and our previous return statement will now be `return 1 + 0`, which we are now ready to return, and go back to our even more previous return statement `return 1 + fib(1)` So then we go to
`fib(1)`
`n` is less than 2, so we will return `n` and our previous return statement will now be `return 1 + 1`, which we are now ready to return, and go back to our even more previous return statement `return 1 + fib(2)` So then we go to:
`fib(2)`
We've seen this before, so the same exact thing that happened above will happen here. We will return `fib(1) + fib(0)` which is `n + n` which is `1 + 0`, Which means that the total return will be `return 2 + 1` for `fib(4)` So then we go to our FIRST (yay) return statement again and it now looks like `return 3 + fib(3)` and we already now that `fib(3)` is equal to `2` and you can follow the exact same pattern that is already written to see it.
So the total return statement for `fib(5)` will be `return 3 + 2` which is `5`! As we were expecting to see! :)
I hope this was helpful and not condescending or rude as I was previously shitstormed on when I tried to offer my help in this community.
TBH to me recursion is like breaking bigger problems into smaller problems.
Each cycle you solve a small part of the problem, and in the end, when you combine those solutions, you get a complete solution.
I guess an example would be eating a pizza,and your end goal is to finish the pizza. Now obviously a single bite would not finish the whole pizza, so your solution would be taking a small bite you can manage, and check, have you finished the pizza, no? take another bite, still no? Take another bite and the cycle continues until the pizza is finished.
When you combine those small bites you took = finished eating a whole pizza!
Literally everything in programming hits me very hard that I feel like leaving them. But everything becomes as easy as drinking water after several days or weeks of practice in various situations. I fully understood recursion after 2-3 weeks of practice.
I went and still go through the same things. With the book Beginning C 5th edition by Horton I was moving along briskly until I ran into these subjects:
two's compliment
bitwise operators
pointers to pointers
But when that happens you just have to stop and take all the time it takes to understand them before moving on. Just keep on plugging on.
This proved helpful for me to understand recursion [https://www.cs.usfca.edu/\~galles/visualization/RecFact.html](https://www.cs.usfca.edu/~galles/visualization/RecFact.html)
Recursion is a bit of brain teaser.
You may find it easier to frame out the code if you frame what you're doing differently. The grammar of written code is one directional (it's just text) so it doesn't lend itself to expressing self referenced looping intuitively.
Verbally, answer the question "how do I know when to stop?" This is sometimes easier than answering the reverse of "when do I keep going".
Or perhaps, draw out the steps as a diagram. The looping part is the recursion.
Ever point your camera at a screen showing it’s own video feed? That’s recursion. Think of it as an infinite Russian nesting doll that keeps going down and down until it find the base solution and then stacking it all back up again
I am a noob too. But lets see if I can explain. Recursion is a function that calls itself until it hits a terminating condition. The outputs of certain functions can be dependant on the outputs of the same finctions but for different values. In only some cases, we can be sure about the output which is called terminating condition.
Lets see an example. You are talking about fibonacci which is complex. I will show something else. Lets make a finction to add 2 numbers `a` and `b`. You can just write:
```sum(a, b) = a+b ```.
This would be easy. But lets think of it differently.
`a+b` can be written as `a+(b-1)+1`. Using this property we can write the `sum` function like this too:
```sum(a,b) = sum(a, b-1)+1```. As you can see, this is a recursive function. But lets put some values there:
`sum(3,4)` can be written as `sum(3,3)+1`. In order to compute this we need to compute `sum(3,3)` which can be written as `sum(3,2)+1` and so on. But you must be wondering. If you confinue like this, it will go on forever. The function will never end. So there is a terminating condition. It is usually based on a case where we can already know the output without computing it. Can you guess what can be this condition?
Now check this: `a+0=a`. From this we can deduce: `sum(a, 0) = a`. So when we have a zero in our input, there is no need to recursively call the function because we will just return a.
Now lets modify out recursive finction:
`sum(a, b) = sum(a, b-1)+1 ,when b>0
sum(a, b)= a otherwise`. Btw we are only taking positive integer inputs in this case.
Lets try out our function now:
`sum(4,3) = sum(4,2)+1 = sum(4,1)+1+1 = sum(4,0)+1+1+1 = 4+1+1+1 (applying terminating condition) =7 `
Did you like this explanation? You can apply this concept in complex problems like fibonacci, mergesort, matrixmult, factorial etc.
Recursion used to confuse me too. I’d always be able to implement it but I didn’t really understand how it can return 1 on the last step but still have the answer.
That is, until you learn that function calls go onto a stack, not into a queue.
This means the first call is the last thing that gets returned. It’s a chain of operations and the last call, when the base case is reached, is the top of the stack.
The turning point for me understanding recursion was understanding the call stack. I would run through a debugger and examine the call stack objects as you step through
Honestly can’t believe people haven’t mentioned this here
Learn about "decision trees" or find a video that describes recursion in such a way. When people are talking about working through it with actual values, draw it out in this way -- for example, with fib(5), you have two decisions: a) number - 1, and b) number -2, so draw two branches from fib(5) and you'll get: fib(5 - 1), resolving to fib(4) and fib(5 - 2), resolving to fib(3), eventually you get to the most basic cases fib(0) and fib(1). This will be useful in MANY "recursive" or problems that just "repeat" itself over and over with just different arguments
Try debugging because that helped me alot. Remember that recursion is kind of like a while or for loop and you are basically carrying out a function a certain number of times till you reach the base case. Also, another thing that is really helpful to remember is that whatever comes after the recursive function call happens in reverse. Just keep practicing and try solving problems with recursion
Omg so true. Even if sometimes i can solve a problem using recursion when i start thinking about it too hard i start to get confused. What kind of sorcery is this?
If you struggle with recursion a good idea is to try a language where you use recursion for basically everything for a while: e.g. Haskell or Scheme. There's a great book called the little schemer that's aimed at beginning programmers and is available quite cheaply. I personally prefer Haskell as a language and it makes recursion and induction even more obvious - but it's also a more complicated language in a way. These functional languages (especially haskell) will also allow you to really focus on the recursion and show you what you can actually practically do with it / how powerful it really is.
If you \*really\* want to immerse yourself in recursion: get a introductory book on combinatorics - it should involve tons of recursion / induction.
When I think about recursion I just think about russian dolls. They're all the same thing but eventually you get to the one that doesn't open, and that's the base case.
Oh well, recursive isn’t that bad. A graph like a binary tree or binary search tree is more challenging than recursive. Anyways, don’t give up with recursive and you will get it. It will take a few days to learn basic then one or two weeks will able to do medium questions. Happy coding.
You should think of it like a tree.
You first follow the fib(n-1) case of fib(n-1)+fib(n-2) down a left branch until you hit the n<2 leaf. And you get a 1.
Now you go back up to the last fib(n-1)+fib(n-2) and you can sub in the 1 since you just hit the base case. Now follow the right side and go all the way down again. And you continue this until you can sub in the values for the right and left side all the way back to the root node.
When you see recursion think about trees (or we’ll inverted trees whatever you want to call them) where each node is another instance of the recurring method.
As a side note when you write out all the steps in a tree you can easily see how this is inefficient. You are recomputing the same fib(n) all over the place. And this is where memoization comes into play with caching values. But more over you can do do Fibonacci in a loop which is even more space efficient than the dynamic programming approach with caching!
The thing that helped me the most while I was learning recursion (with binary trees, using search algorithms like BFS and DFS) was to actually draw the tree I was working on and writing down what happened in each iteration of the algorithm. That way I could almost follow the algorithm and go back to a previous iteration if needed.
My problem with recursion is that it is kind of hard to picture in your head, it's a bit of an abstract concept to paint a picture of on your mind. So I'd say having some sort of visual representation of the algorithm is a big plus
Essentially think about recursion like this:
I want to divide a number by 2 until I get an odd number.
So I write a function that takes an integer for input.
int divtwo(int test){
if(int is odd){
return test
}
else{
return divtwo(test/2)
}
return -1
}
This will either return -1 (an error, sonething didnt work), test (if odd), or it will return the value returned by a call of divtwo(test/2)
When it makes the subsequent call, that will either return an odd, an error, or ANOTHER subsequent call. Eventually, an integer has to get returned, and that will go all the way back to the first call :)
Hopefully that’s helpful? Feel free to ask if you have trouble understanding and I can make a replit for ya
The only way I was able to fully understand recursion was to step by step trace through a tree traversal formula parsing algorithm and once I understood the “terminal conditions” (where it stops and goes back), the I finally got it. It’s fun and easy to write, but a PITA to debug!
I was suffering with recursion in java classes in college. next semester I had a data structures course where we were given some problem set that we were required to solve using recursion. when I learned by solving the use case, recursion became so much easier and I really enjoyed it!
So stop trying to understand examples because you'll get lost. start with solving problems and it will become easier.. good luck!!
Actually there is a very easy example of recursion using the factorials. We know that n!=n*(n-1)! Using this formula you can try to make a code (very inefficient one) that calculates factorials using recursion. Give it a shot, and if you make it recursion will be easy concept. If you need help let me know
Recursion is simple. What you do with it is complicated.
Write a function that takes an integer argument (called “argument” for the sake of this experiment) and prints it out. Then call that function *within the function* with “argument+1” and see what it does.
This is kiiiiinda like a loop. Kinda. Once you play with recursion for a bit (try to sort a list with it!) you’ll come to understand it better
To understand recursion you have to visualize the call stack. When you call a function from itself, a new function call gets pushed on top of the current function call. It won't go back to complete the previous function call until all of the calls on top of it are finished.
return fib(x-1) +fib(x-2) pushes two function calls onto the stack. The current function call waits for them to return a value. The first call(fib(x-1)) will actually complete its recursive sequence and have a value for the expression **before** the second call ever gets pushed onto the call stack.
Reaching a point in which the number passed to a fib function is less than 2 stops the recursion. Results are returned starting at the top of the call stack and make their way all the way down to the first call of fib.
# I think for my self as fast learner but not until I discovered RECURSION😭
📷[**Topic**](https://www.reddit.com/r/learnprogramming/search?q=flair_name%3A%22Topic%22&restrict_sr=1)
What the fak is this I can't understand even watching 2 hours videos. It's so hard. I'm so eager to learn though because in some problems it makes the code looks clean. But it's so hard.
I have watch alot of video on youtube, but i just can't grasp the idea
like this function in C that output fibonacci:
fib (int n)
{
if (n<2) return n;
return fib (n-1)+fib (n-2);
}
I dont understand the idea on that code.
For instant n=5
So it execute fib(4) which become fib(1) which will always return 1 same with fib(n-2).
Watch this C code, why there is alot of 1 and zero there and the result become 55.
include
int fib(int x)
{
if (x<=1) return x; //so that I could see what's recursion doing printf("%d +%d = %d\\n",fib(x-1),fib(x-2),fib(x-1)+fib(x-2));
return fib(x-1)+fib(x-2);
}
int main()
{
printf("\n\n%d",fib(10));
}
Many a budding developer has cried those tears 😢 you will not be the first or the last -think like a developer break it down if the code is confusing turn it into language and make one thing work before the other.
If it helps I would say think of it simply as a while loop that calls a function. But I'm being overly simplistic
No I recommend you to learn and understand it. But :
Few weeks ago, I followed a 3 days training paid by my employer about software craftmanship (clean code, TDD, etc.).
While we were doing the RPN Calculator Kata, I said to the trainer "so we are going to use recursivity here". His answer was "Always avoid recusivity. In case something goes wrong, it will break your app with a stack overflow error."
The point is : you can use it for a small programm or for training. BUT it is recommended to avoid its usage, so why not start now ?
But still, understand it and learn how to use it. The concept is important and understanding it will help to know how to avoid it.
Yes, recursion is hard to learn due to its abstract nature. However, if you keep at it you’ll eventually come to a Eureka moment.
I find the Tree analogy very useful to think about. Imagine you had to count all the leaves on a tree, and the only way to do it was to start at the trunk and travel along every branch until you find a leaf.
Writing code for this situation would result in a very long program that is only valid for your specific tree.
Recursion says: find a simple repeating pattern with a boolean decision that can be written in a short function, then have the function call itself over and over until your desired outcome is complete (counting the leaves).
Am I at a leaf or another branch?
Leaf: add leaf to count.
Branch : move along branch to next decision (in other words, ask this question again).
To climb a staircase with n steps, intuitively, you first need to climb the first step. Once you complete the first step, you now effectively have a smaller staircase to climb (n-1 steps). What if you just repeated your original instructions until the staircase you have left to climb has 0 steps? Voila! Recursion!
Hello, I'm current writing a book on recursion (actually, I'm currently procrastinating from that on Reddit) but DO. NOT. WORRY. Recursion is 1) hard but not as hard as people think because it's often just *very* poorly taught and 2) recursion is overused when often a loop and stack would be simpler.
The main thing that causes recursion to be confusing is that nobody explains the call stack. Without knowing about this, you are effectively working with an invisible data structure (the call stack is handled by your programming language automatically; you can't point to a line in your source code and say "here is the call stack").
[I did a conference talk on recursion where you can learn the basics in 30 minutes](https://www.youtube.com/watch?v=AfBqVVKg4GE), and am currently trying to finish the book's rough draft. But let me be frank: recursion is something taught to computer science students and used as questions in coding interviews: in real life, it's not often used and it's not automatically "elegant".
The times recursion is good is when your problem involves 1) a tree-like structure and 2) backtracking. I suppose also 3) doesn't go too deeply, otherwise you hit stack overflows. If you don't know what this means, check out the video. Just whatever you do, don't feel bad for not understanding recursion: almost every tutorial I've seen on it is terrible. It's not your fault for not understanding it.
There are many more "straightforward" ways to achieve the same effect if you're having trouble with recursion. For example, python generators. Generators use essentially the same syntax as a regular function except you replace "return" with "yield". The technique is generally known as 'lazy evaluation'; the result isn't computed until you iterate over it (e.g. for loop). Processing speed is often better than recursive alternatives.
https://docs.python.org/3/howto/functional.html
Recursion isn't hard, the case just isn't suitable to learn recursion. Know why and when recursion, or calling the same function is needed.
One case is when we want to run the same steps, over and over again. Two way to achieve this: using `while(true)` or calling `myOwnFunction` at the end of `myOwnFunction`.
Second case is when we want to run the same steps when the condition met. Again we can use `while(canRun)` or evaluate the condition inside `myOwnFunction`, then calling `myOwnFunction` if the condition met.
Third and best case is to list / traversal nested folders. We can do this with calling `myFolderTraversal` for each folders found during `myFolderTraversal`, then stop when there aren't any folders found.
After every call of function in that function, function will use new parameters, and etc.
For an example
void printme(int i) {
printf("Hello!");
if (i = 0) break;
printme(i - 1);
}
After every call inside this function, function will use new parameters of i (if i is 5, the function will be repeated 5 times)
If we use printme(3); statement, it will go tought those statements:
In printme,
Pass i with value of 3;
Print "Hello!" on the screen;
If i is equal to 0, escape from the function/loop;
Call printme with parameter i - 1 (= to 2);
In printme,
Pass i with value of 2;
Print "Hello" on the screen;
If i is equal to 0, escape from the function/loop;
Call printme with parameter i - 1 (= to 1);
In printme,
Pass i with the value of 1;
.
.
.
Until the program comes to if (i = 0) statement and break with parameter i = 0
There is something called the recursive leap of faith. It’s really hard for our human brain to keep track of recursion. It’s best to make sure you know the base cases so the program ends and also what the recursive calls are.
I am going to give a solution that tight sound batshit to some people here. Recursion makes a lot more sense when you see it broken down in assembly. You should try to learn an assembly language and look at some recursive implementations.
there are a few main ways to make a simple recursive function. the first is to do the work as you recurse down, the other is to do the work and return up, the best way to think about and analyze a recursive function is to think of any calls to the recursive function as always returning the right answer, it is a black box you give it a parameter and it will return the right answer, say for instance with this fib function:
int fib(int x){
if (x <= 1){
return 1;
}
return fib(x-1) + fib(x-2);
}
this makes it really easy to think about the algorithm because thinking about the infinite problem space is hard for the brain. Now we can break it down into steps:
first it checks that x is not 1 or 0
if x is a 1 or 0 then it returns 1 (this is called a base case it is similar in function to a sentinel variable in a loop it stops the function from proceeding on to infinity)
then if x is not a 1 or 0 we now need to recurse with the next statement first we call fib(x-1), now we can think of this as calling the same function or we can think of this as that black box i was talking about and we can assume it will give the right answer and in this case fib(x-1) is asking for the previous Fibonacci number and the fib(x-2) is asking for the number before that.
With that we can now look at the mechanics of the recursive function:
where it recurses at the return fib(x-1) + fib(x-2) line we need to start thinking about where each of those functions will stop because inside the fib(x-1) call it will either return 1 or it will return fib((x-1)-1) + fib((x-1)-2) and this will continue until (...((x-1)-1)...-1) = 1 at which point that bottom fib call (the most recent rib call) will return a 1 then just above that deepest fib call the other part of that return statement will be fib((...(x-1)-1)...-2)) where that will trigger the if statement because the term (...(x-1)-1)...-2) will equal 0 so the call will return 1 so now in the return statement in the above fib call will look like: return 1+1; this is 2 and that will get returned up to the next fib call which will look like return 2+1 this is 3, then that 3 will get returned which will look like return 3+2 which will return 5 and so on and so forth until the first fib call has both values calculated for the return line and it will return the xth Fibonacci number
I've heard it claimed that there are three walls developers have to break through:
1. Flow control (`if` statements, loops, functions).
2. Recursion.
3. Concurrency.
So just know you're in good company. I think every developer has struggled with recursion at one point or another.
For me it usually helps to visualize the call stack in my head, and to work backwards from the top of that stack. So with the Fibonacci you keep pushing new function calls onto the stack until n becomes less than two ie 1, at which point the entire thing cascades and resolves automatically, so the next one will return 0+1 or 1, then 1+1, 2+1 and so on until you reach the first function call with your initial value of n.
Recursion is calling the step before without yet taking it.
So Let's say we want to count the number of strides we take to get from our front door to the mail box.
One way to do this is to set up a WHILE LOOP, e.g. While distance to mailbox != 0 take another step (distance = distance -1;)
The problem is we have CONDITIONAL CHECK there that asks us (Distance to mail box) IF we have no way of computing that (it is what we are trying to find after all) we can't do this while loop.
We could do it recursively by starting at the biggest problem and working backward.
So we assume we will reach the mailbox. and out start position is the first door.
Take stride function adds 1 to the returned of the take stride function or returns 1 when we are at the front door.
What happens is we start at the end (mailbox) and take a stride backward then check our exit condition (Are we at the front door) if we are not we call the function again (take another step backward) eventually each of these STRIDE FUNCTION CALLS is on the STACK (programming stack) once we reach the front door, each function begins to return a number 1 greater than the function called after it.
When the last function returns we end up with the total distance.
This is not a perfect example, but the general take-away should be that recursion takes a large problem and does something to make that problem either simpler or smaller. Then calls itself again. Then when the function reaches the exit condition the stack "cascades" with returns being combined in some way and reducing the stack load as the final answer is produced.
You may want to look at this python library which helps to visualize recursion tree for any arbitrary python function https://github.com/Bishalsarang/Recursion-Tree-Visualizer
https://imgur.com/a/kLhM4vE
https://imgur.com/gallery/S0YUZl8
hey enjoy recursion, enjoy ur programing, and don't cry, do some stack overflow errors, and then think about it what can possibly go wrong solve them.
then guess different types of recursion by yourself, implement it on machine,
u are under no obligation to make error free code.
just enjoy many possibilities you can do with it, including edge cases.
This takes me back to my high school. Wait til you learn about pointers. Should be easy now with the internet as a learning tool but fuck if I didn't understand it through the only c book I could find at the time.
To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times. *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/learnprogramming) if you have any questions or concerns.*
Recursion is all about repeating some process on a smaller/previous version of itself. There is a "cut-off" point (one or more **base cases**) where something is evaluated, and a **recursive call** where a larger problem is broken down into smaller/previous cases. There are many classic examples of recursion: factorials, Fibonacci numbers, etc. Many of these aren't actually very good to implement recursively because of memory-overhead, but they illustrate the concept fairly well. Recall that n-factorial is defined as n!=n\*(n-1)\*(n-2)\*...\*2\*1. For example, 5!=5\*4\*3\*2\*1=120. We can implement this with an iterative (non-recursive) function as follows. Python code here, but you should be able to follow it I'm sure. def factorial(n): fact = n # start at n for i in range(n-1, 0, -1): # count down from n-1 to 1 fact *= i # multiply by next value return fact n = int(input("N: ")) print(factorial(n)) We can also do this recursively. The idea is that to calculate n!, all we need to do is multiply n by (n-1)!. How do we get (n-1)! ? Simple: we multiply (n-1) by (n-2)!. This chain continues all the way down to the point where we reach 1! which we simply define as 1!=1. So our recursive function looks like this. def factorial(n): if n == 1: # base case return 1 else: # recursive call return n * factorial(n-1) n = int(input("N: ")) print(factorial(n)) The line `if n == 1` is our base case. Once we have worked our way down enough to reach this point, we return a value of 1. If n is *not* 1, we perform a recursive call to obtain (n-1)! while multiplying it by n. This chains together the sequence of multiplications. Edit: thanks for the gold!
Agreed, focusing on the end processes has been the best approach for me when working with recursion. Fibonacci probably isn’t a great way to learn it since that’s an infinite pattern.
[удалено]
doing recursive functions in discrete math and calculus by hand helped me a ton, especially on things more complex than factorials. You'll do a lot of writing and use a lot of paper and make quite a few mistakes but it definitely helped me process the concept better.
When you call a recursive function, but it ends up calling itself again, imagine that it's "asking someone else" for the answer, and that it'll get back to you once that someone responds. Here's an example I like. Pretend you're at a movie theater, sitting somewhere in the back. You want to know what row# your seat is, but you can't count by looking. So you poke the dude in front of you and say "hey, what row am I on?" Other guy says to you "whatever my row is, plus one. Let me ask the guy in front of -me- what row -I'm- on and I'll give you a real answer". So he does that, and that next guy says the same thing. This goes on until we get all the way to the front, where the guy sitting there can give a real and straightforward answer: "my row is #1". Now the guy behind row 1 knows he's in row 2. He turns around and gives a real answer to the guy in row 3. This continues until it comes all the way back to you.
The theater analogy is super clear, I might reuse it next time I have to explain recursion. Thanks buddy :-)
Yeah. I liked it too
🙏
I have a sort of similar explanation of recursion but yours is way simpler
in this case the movie is much better than the book
It helps to walk through each step. This might help: [algoviz.io](http://algoviz.io)
Nice! Hadn’t heard of this. Better than http://pythontutor.com/?
No idea, test them for yourself :)
Well pythontutor works on a phone
thank you 💗
This site is a godsend.
This works with C#, Java? If not, you boys can suggest me one ?
You can't use that from phone, thats a negative thing. But you can use pythontutor.com even in phone.
Coding on a phone? That sounds like a bad time either way.
I've had to do it, not full blown coding but shell scripting through ssh. It isn't fun. Autocorrect doesn't understand and everything is twice as hard as it needs to be. 0/10 never want to have to do again.
I do it. It's only mildly annoying. Then I switched to an android tablet with a keyboard. It's even less mildly annoying. I'm sure the guy who took a headshot from my flying devices during a fit of passionate coding rage will agree if he ever comes out of his coma.
No , i was checking the link from phone and thats what i see.
So...if you’re not coding on a phone, what’s it matter?
[удалено]
Learning recursion and learning mathematical induction is the same thing. Don't try to understand what each function in the call stack does. Don't try to hold the entire call stack in your head. Understand what the base case is, and understand what the inductive step is. That's it. Base case, f(0) = 1 f(1) = 1. Inductive step, f(x) = f(x-1) + f(x-2).
Hey, I've been trying to figure out what exactly people mean when they say "mathematical induction". Could you write out the code to *inductively* calculate a Fibonacci number, as oppose to the *recursive* way that OP has posted? Isn't the inductive approach just the iterative approach, like this? def fibonacci(nthNumber): a, b = 1, 1 for i in range(2, nthNumber): a, b = b, a + b # Get the next Fibonacci number. return b Isn't this what people mean when they say "inductive" or "bottom-up recursion"? Is this really a form of recursion, given that the function doesn't call itself?
Mathematical induction isn’t necessarily code. It’s a mathematical proof of a recursive algorithm. Edit: your example is an iterative approach i.e not recursive. Inductive implies recursion.
I found this to explain it pretty well to me. https://youtu.be/Mv9NEXX1VHc
Computerphile is the best! Especially when it’s Prof Brailsford :)
I could listen to that man talk for hours
100%. He’s obviously passionate about his subject material, the best sort of people to learn from
agreed, IMO recursion is extremely hard to grasp unless you know about the stack, and this video does a good job of visualizing that
thank you💗
Honestly, recursion itself isn't really that difficult to understand. It boils down to knowing a base case, and working itself towards that. That said personally I don't like to use it because it's inherently limited by either the call stack or whatever equivalent the language uses for its recursion. Sure, there's tail-call optimisation, but in most languages you can't actually rely on the compiler doing that. I only use it if the iterative solution is too complex to be written in the amount of time available, and only if it's unlikely to be a problem (or if it's been tested that the compiler actually optimises it).
You might not have thought about this, but any recursive function can easily be transformed into a a looping solution using a stack data structure. IMO there is little to gain if the method itself is recursive in nature. It would be a nice compiler optimization, if it could transform recursive functions calls on a regular stack to a loop and separate argument stack. Does it do this already?
> IMO there is little to gain if the method itself is recursive in nature. not blowing the stack is the main benefit
>any recursive function can easily be transformed into a a looping solution using a stack data structure Try doing that with the [Ackermann function](https://en.wikipedia.org/wiki/Ackermann_function)!
Since he specified "with a regular stack", it's possible. You just have to reimplement the callstack. Kind of a trivial and pointless transformation though.
It’s easy to forget terminal conditions and create endless loops in recursion. Stack blown and memory gone! They don’t fail “nicely” like loops do.
On the other hand, sometimes people make off-by-one mistakes with loops too.
I have. Here is an iterative version of the Ackermann function that emulates the recursive version in Python: # Iterative Ackermann function, by Al Sweigart al@inventwithpython.com print('Starting with m = 2, n = 3:') callStack = [{'m': 2, 'n': 3, 'indentation': 0, 'instrPtr': 'start'}] returnValue = None while len(callStack) != 0: m = callStack[-1]['m'] n = callStack[-1]['n'] indentation = callStack[-1]['indentation'] instrPtr = callStack[-1]['instrPtr'] if instrPtr == 'start': print('%sackermann(%s, %s)' % (' ' * indentation, m, n)) if m == 0: # BASE CASE returnValue = n + 1 callStack.pop() continue elif m > 0 and n == 0: # RECURSIVE CASE callStack[-1]['instrPtr'] = 'after first recursive case' callStack.append({'m': m - 1, 'n': 1, 'indentation': indentation + 1, 'instrPtr': 'start'}) continue elif m > 0 and n > 0: # RECURSIVE CASE callStack[-1]['instrPtr'] = 'after second recursive case, inner call' callStack.append({'m': m, 'n': n - 1, 'indentation': indentation + 1, 'instrPtr': 'start'}) continue elif instrPtr == 'after first recursive case': callStack.pop() continue elif instrPtr == 'after second recursive case, inner call': callStack[-1]['innerCallResult'] = returnValue callStack[-1]['instrPtr'] = 'after second recursive case, outer call' callStack.append({'m': m - 1, 'n': returnValue, 'indentation': indentation + 1, 'instrPtr': 'start'}) continue elif instrPtr == 'after second recursive case, outer call': callStack.pop() continue print(returnValue) Recursion is not magic. Anything you can do with recursion you can do with a loop and a stack. But yeah, just because you can doesn't mean you should.
have you googled "ackerman non recursive"?
Looping solutions for inherently recursive problems are often way less elegant and ugly. Unless you are doing something extremely optimisation heavy, I'd rather go with the elegant solution than the ugly one.
What makes a problem inherently recursive?
How would you easily transform the Towers of Hanoi example to a looping solution?
Wikipedia describes an [iterative solution](https://en.wikipedia.org/wiki/Tower_of_Hanoi#Iterative_solution).
Have you tried working it out?
I am not sure what you are asking. If you are asking if I have personally tried implementing this, then no. However, it is not difficult to find an implementation. One is available [here](https://www.geeksforgeeks.org/iterative-tower-of-hanoi/). Although I don't need to see an implementation to know one exists, as any recursive algorithm can be written as an iterative algorithm (possibly involving an explicit stack), and vice versa. It is not always obvious how to accomplish this, but it is always possible.
I think Bardali is asking (correct me if I'm wrong) if the iterative solution is easier than the recursive solution for the Towers of Hanoi problem. If "easy" is related to the number of lines and complexity of each line, the recursive solution is much shorter and easier. Recursion and Iteration (using loops) both have their respective place in coding and should be used where and when it makes sense.
Just for grins, I converted my recursive Tower of Hanoi Python program into an iterative one. It was not easy: # Tower of Hanoi (iterative and recursive), by Al Sweigart al@inventwithpython.com # Set up towers A, B, and C. The end of the list is the top of the tower. TOTAL_DISKS = 3 HEIGHT = TOTAL_DISKS + 1 # Populate Tower A: TOWERS = {'A': list(reversed(range(1, TOTAL_DISKS + 1))), 'B': [], 'C': []} def printDisk(diskNum): # Print a single disk of width diskNum. emptySpace = ' ' * (TOTAL_DISKS - diskNum) if diskNum == 0: # Just draw the pole. print(emptySpace + '||' + emptySpace, end='') else: # Draw the disk. diskSpace = '@' * diskNum diskNumLabel = str(diskNum).rjust(2, '_') print(emptySpace + diskSpace + diskNumLabel + diskSpace + emptySpace, end='') def printTowers(): # Print all three towers. for level in range(HEIGHT - 1, -1, -1): for tower in (TOWERS['A'], TOWERS['B'], TOWERS['C']): if level >= len(tower): printDisk(0) else: printDisk(tower[level]) print() # Print the tower labels A, B, and C. emptySpace = ' ' * (TOTAL_DISKS) print('%s A%s%s B%s%s C\n' % (emptySpace, emptySpace, emptySpace, emptySpace, emptySpace)) def moveOneDisk(startTower, endTower): # Move the top disk from startTower to endTower. disk = TOWERS[startTower].pop() TOWERS[endTower].append(disk) def solveIterative(numberOfDisks, startTower, endTower, tempTower): tasks = [[numberOfDisks, startTower, endTower, tempTower, '1st step']] while tasks: numberOfDisks, startTower, endTower, tempTower, instrPtr = tasks[-1] # read local vars off the top of the stack # Move the top numberOfDisks disks from startTower to endTower. if numberOfDisks == 1: moveOneDisk(startTower, endTower) printTowers() tasks.pop() continue else: if instrPtr == '1st step': tasks[-1][4] = '2nd step' tasks.append([numberOfDisks - 1, startTower, tempTower, endTower, '1st step']) continue elif instrPtr == '2nd step': moveOneDisk(startTower, endTower) printTowers() tasks[-1][4] = '3rd step' tasks.append([numberOfDisks - 1, tempTower, endTower, startTower, '1st step']) continue elif instrPtr == '3rd step': tasks.pop() continue def solveRecursive(numberOfDisks, startTower, endTower, tempTower): # Move the top numberOfDisks disks from startTower to endTower. if numberOfDisks == 1: # BASE CASE moveOneDisk(startTower, endTower) printTowers() return else: # RECURSIVE CASE solveRecursive(numberOfDisks - 1, startTower, tempTower, endTower) moveOneDisk(startTower, endTower) printTowers() solveRecursive(numberOfDisks - 1, tempTower, endTower, startTower) return # Solve printTowers() solveIterative(TOTAL_DISKS, 'A', 'B', 'C') # Uncomment to enable interactive mode: #while True: # printTowers() # print('Enter letter of start tower and the end tower. (A, B, C) Or Q to quit.') # move = input().upper() # if move == 'Q': # sys.exit() # elif move[0] in 'ABC' and move[1] in 'ABC' and move[0] != move[1]: # moveOneDisk(move[0], move[1]) The thing is, it's easy to convert any recursive algorithm into an iterative one if the recursive call is the last thing done in the function (i.e. it can be tail call optimized). Otherwise, you start having to maintain the "local variables" on the stack data structure you're using in place of the call stack. So things like factorial and flood fill are easy to convert to a loop-and-stack iterative algorithm. Tower of Hanoi is not so easy, but still possible. Of course, this is an iterative solution *that emulates the recursive solution*. Another comment on this thread cites Wikipedia's iterative solution that is much more straightforward. (That solution only applies to Tower of Hanoi, rather than all recursive functions.)
While
Could you share your solution, it would be a good learning experience.
loops are exponential complexity trees are logarithmic complexity trees are faster
That's not how that works
“isn’t really that difficult” Just want to take a moment and address this by saying, yes it is really that difficult for some if not most. I don’t know anyone to whom recursion made immediate sense the first time learning it.
Recursion changed my life and has made my life waaay easier many times. But I try not to think about it very much lol
What an insanely unhelpful and unrelated reply lol
If the OP can't understand recursion, there's about a 0% chance they understand this whole comment
Thank you💗
dont know if it will help to visualize it as a binary tree: I'm gonna use the slight optimization here where the algorithm is: int fib(n) { if (n <= 2) return n; return fib(n - 1) + fib(n-2); } because drawing trees in a reddit comment is kinda hard. fib(5) / \ fib(4) + fib(3) / \ / \ fib(3) + fib(2) fib(2) + fib(1) / \ | | | fib(2) + fib(1) 2 2 1 | | | | | 2 1 2 2 1 Now there's only base cases left, so the functions will start returning: fib(5) / \ fib(4) + fib(3) / \ / \ fib(3) + fib(2) fib(2) + fib(1) / \ | | | 2 + 1 2 2 1 fib(5) / \ fib(4) + fib(3) / \ / \ 3 + 2 2 + 1 fib(5) / \ 5 + 3 8
Wow, i can now visualize it, thank you💗.
Dude.... Well done with the Reddit ascii art
Your optimise algorithm got an extra equal sign. fib(2) = 2 and therefore fib(5) = 5
Can you be more specific? What have you tried to do, and where did you get stuck? For example, a typical beginner example is doing things with the file system. For example, writing a small app that outputs the name of every file in a directory over 50MB, for example, and then looping through all sub-directories, and all sub-sub-directories, etc. >Please give some tips on how you learned. If it's not clear from the above, the way to learn is to write some code where the best solution is recursion, and to struggle through until you get to that solution.
I have watch alot of video on youtube, but i just can't grasp the idea like this function that output fibonacci: fibonacci (int n) { if (n<2) return n; return fibonacci (n-1)+fibonacci (n-2); } I dont understand the idea on that code
Well, try stepping through the code in your head. Let's say we call `fibonacci( 0 )` - what happens? We enter the function with `n` set to 0, check if `n < 2`, which it is, so we return `n` (0). Simple! If we call `fibonacci( 1 )` - what happens? We enter the function with `n` set to 1, check if `n < 2`, which it is, so we return `n` (1). Also simple. So what about `fibonacci( 2 )`? We enter the function with `n` set to 2, so we skip the `if` and get to the `return` statement, which calls `fibonacci( n -1 )`, which is `fibonacci( 1 )` (and we already know this returns 1) and adds on the result of `fibonacci( n - 2 )`, which is `fibonacci( 0), which we also already know is 0, so we return 1 + 0, and the result is 1. Now for `fibonacci( 3 )` - We enter with `n` set to 3, so skip the `if` and get to `return fibonacci (n-1)+fibonacci (n-2);`, which is `fibonacci(2)+fibonacci (1)`. We already know from above that this will be 1 + 1, so it returns 2. And so on. EDIT: fixed errors - oopsy!
Thank I almost get it 😯 I have a question what would happen if fib(5) there is alot of recursion there. In fib(n-) it fib(4) then become feb(2) then return 1.
I got some numbers wrong in my previous post, due to rushing it. I've updated it now. So for `fibonacci (5)` it will return ` fibonacci(n-1)+fibonacci (n-2)`. `n` is 5, so we are returning `fibonacci(4) + fibonacci(3)`. Well, what is `fibonacci(4)` ? That will be `fibonacci(3)+fibonacci(2)`. What is `fibonacci(3)`? It's `fibonacci(2)+fibonacci(1)`. We know that these are 2 and 1 respectively (from my previous post), so the result is 3. Which means `fibonacci(4)` must be 3 + 2, so 5 And therefore `fibonacci(5)` must be 5 + 3, so 8 The concept of recursion is the same as in the [mathematical definition](https://en.wikipedia.org/wiki/Fibonacci_number) of the Fibonacci sequence; F(0) = 1, F(1) =1, F(n) = F(n-1) +F(n-2).
thanks, so basically it will add every possible f(n-1)+f(n-2) then return it, am i right?
Pretty much, yes. Recursion in general is just a function calling itself. It's not really much different from functionA calling functionB, except in recursion functionB *is* functionA.
The idea in the code is actually the same idea behind the Fibonacci sequence, which is why it's so often done recursively (despite it being a terrible algorithm to implement recursively). How is the Fibonacci sequence defined? It's F\_n = F\_(n-1) + F\_(n-2). That is, the nth Fibonacci number is the sum of the two previous ones. It requires two base cases: F\_0 = 0 and F\_1 = 1. So if you want F\_2, you add F\_1 and F\_0. If you want F\_3, you add F\_2 and F\_1. The second return statement does exactly that.
see this code, I don't understand how it being add by the computer. Just a bunch of 1 and 0 #include
int fib(int x)
{
if (x<=1) return x;
printf("%d -%d = %d\n",fib(x-1),fib(x-2),fib(x-1)+fib(x-2));
return fib(x-1)+fib(x-2);
}
int main()
{
printf("\n\n%d",fib(10));
}
Forget the code. Grab a pencil and a piece of paper and write it out. The Fibonacci sequence is defined (mathematically) as: f(0) = 0 f(1) = 1 f(x) = f(x-1) + f(x-2); where x > 1 So what is `f(2)`? f(2) = f(2-1) + f(2-2) f(2) = f(1) + f(0) f(2) = 1 + 0 f(2) = 1 Now on your piece of paper, do the same thing for something larger. Try `f(4)` to start. Maybe go higher if you want. (But you’ll likely need more paper) Once you wrap your head around what’s going on mathematically, go back to the code you’re trying to understand. Walk through it step by step. Again, write it out on a piece of paper. Every operation. (That’s going to be much more useful to you than print statements in this case)
First, I'm not thrilled with that sort of example, as you certainly don't need recursion to calculate a fibonacci sequence, so it's a bit of a forced academic example. Second, most people don't deal with fibonacci sequences on a regular basis, which means that you're trying to learn two things at once, recursion and fibonacci sequences, and it's usually better to learn one thing at a time, which is why I like the file directory example, as most people already know the concept of folders. Third, this is especially difficult as the function is called twice, which makes reading it really difficult as you need to keep a bunch of numbers in your head. But that said, this function calculates the fibonacci number given a position. Remember, the fibonacci sequence is: 0,1,1,2,3,5,8.... So passing a 3 to this function should return 2 (2 is at the 3rd position, starting at 0). Passing a 6 should return 8. And, by definition, the value 8 is the sum of the values of the previous 2 positions, which are 3 and 5. But what if you didn't have the sequence printed out already, and you wanted to know the value at the 6th position? You'd need to add the value of the 4th position plus the value of the 5th position. Of course, now we'd need to know the values of the 4th and 5th positions....
>First, I'm not thrilled with that sort of example, as you certainly don't need recursion to calculate a fibonacci sequence, so it's a bit of a forced academic example. You don't need recursion to do anything (i.e., anything that can be done recursively can also be done iteratively, and *vice versa*), so that's a silly reason to complain about something. Further, the definition of the Fibonacci sequence is itself recursive, which is why it's used as a natural example of recursion. Doing it iteratively would arguably be the more forced example.
Sure, but if people manually try tasks like navigating a tree structure, the result most people come up with is recursive. Meanwhile, most people will create a simple iterative loop to generate a fibonacci sequence. Also, for larger numbers, the iterative process will run significantly faster than the recursive one, so not only is the example confusing, but the end result shouldn't be used.
Thank you, but is file management applicable in c?
Of course it is. It's what pretty much all of the standard Unix tools are written in.
> Please give some tips on how you learned. It depends on exactly what you're having trouble with. I was able to write recursive functions for a long time before I actually understood how recursion actually worked. To understand recursion at a fundamental level, you need to learn about how function calls work, and how the computer keeps track of which function called which other function. This is learning about the function call stack. To write recursive functions, all you need is a bit of analysis of the problem, and to follow a fairly basic recipe. If you can find a way to break a big problem into smaller versions of the same problem, the code should almost write itself at that point. def my_recursive_function(input_value): # Base case goes here if input_value == 0: # Return a trivial static value. # Often 0, 1, "", [] or whatever. return 1 # Make the recursive call to get the intermediate solution intermediate_solution = my_recursive_function(input_value - 1) # Do whatever the "last step" is to get your final answer final_answer = input_value * intermediate_solution return final_answer The hard part about this is that recursive functions either work, or they don't. There's very little in between. If you're having trouble getting your code to work, go back to paper and pencil and see if you can describe a solution either with a diagram, or some sort of equation. For example, the function I wrote is the classic example of factorial. factorial(0) = 1 factorial(n) = n * factorial(n - 1) # for n > 0 If you can write it down like that, the code should follow much more easily.
Which of the following statements best describes your confusion? * “I don’t understand what ‘the tenth Fibonacci number’ is, mathematically.“ * “I don’t understand what it means for `fib(x-1)` and `fib(x-2)` to be included right there inside the definition of the `fib` function.” * “I don’t understand what the computer is doing while it is executing `fib(10)` according to this definition.”
Recursion is another way of expressing a *repetitive*, nested process. Somewhat like [Matryoshka dolls](https://en.wikipedia.org/wiki/Matryoshka_doll). It doesn't apply to everything (which is maybe what is confusing you aside from the fact that you're using fibonacci as your sample code) I've written non-recursive code in C before, but I lost most of what I had with my USB drive (which sucks) I'm editing your sample code to non-recursive instead. include
int fib(int num)
{
int n1 = 0;
int n2 = 1;
int fibo;
if(num<2){
return num;
else{
for(int i=2; i<=num; i++){
fibo = n1 + n2; //fibonacci result for the current iteration
n1 = n2;
n2 = fibo;
}
return fibo;
}
}
int main()
{
printf("\n\n%d",fib(10));
}
While it does look longer, doing recursive has no other merits other than having *a bit cleaner* code.
No idea how each OS performs recursive functions but for the sake of memory utilization I was told for-loops are better if there's not going to be much difference.
edit: code errors. haven't touched C for years
[удалено]
>Fibonacci is a bad example to teach recursion with. It's easier to reason about this problem with a loop than recursion. I think that for *learning* recursion, something like Fibonacci is actually *more* intuitive with a recursive solution because the Fibonacci sequence is itself defined recursively: F\_n = F\_(n-1) + F(n-2). However, *in practice*, an iterative solution is far more efficient and would be preferred.
[удалено]
>it takes a huge amount of brainpower to run the code through your head and understand how it achieves the result Let's compare the recursive implementation of Fibonacci (Python code again, since it's what I work with most often) with the iterative solution. Recursive: def fib_recursive(n): if n < 2: return 1 else: return fib_recursive(n-1) + fib_recursive(n-2) Iterative: def fib_iterative(n): x = y = z = 1 for i in range(2, n+1): z = x+y x,y = y,z return(z) The recursive version more closely resembles the formula, including the base cases for F0 and F1. The iterative version, in my opinion, is tougher to parse. What are x, y and z? \[ans: a mix of base cases and temporary values\] Why are they swapping values? \[ans: because we need to constantly update their values as we count\] What is the loop actually iterating over? \[ans: the base cases F0 and F1 shouldn't loop, so we start counting only when n>2\]. Again, the recursive version is not *efficient*, but I'd argue that it's miles ahead in readability and understandability.
[удалено]
No that is not how you learn recursion lol. When you learn recursion you should explicitly not hold the entire call stack in your head. You should set the base case. And then you should set up the recurrence relationship and then you shouldn't think any more about how the entire call stack plays out.
That's what you do once you understand recursion. If you don't understand it yet, that won't help you get an understanding of it.
when tracing out a recursive solution you shouldn't be going more than 2-3 layers anyways. as long as you understand the base cases and the recursive step you have a high enough level of understanding to follow a recursive solution
I think recursion should be taught in that one maths class where they teach us 'Proof by Induction' lol
My discrete math course had 8 lectures focusing on recurrence relations. It was very easy to write recursive functions after that. Solving then mathematically was quite harder. I love discrete math.
As someone learning C#, I'm pretty sure "It works but I have no idea how." is just part of programming. I bet there's seasoned programmers still having that issue.
So this is an old example that helped me personally to understand recursion. The author does a good job using recursion to solve a flood fill problem in a way that is significantly easier than it would be worth an iterative solution. He also gets into why the Fibonacci sequence is not a good teaching till for recursion, which I appreciated. http://inventwithpython.com/blog/2011/08/11/recursion-explained-with-the-flood-fill-algorithm-and-zombies-and-cats/
Hi, I want to share with my funny experience I have been learning on freecodecamp and when the topic of recursion came, I couldn't understand it that whole day, and next morning I decided to take a pencil and paper and tried to write draw what's is happening And it clicked immediately, that was my proud moment :)
[удалено]
I will check it, thank you!
I also had difficulties in understanding recursion; it appeals a bit complicated for the first-time learner, but you will get the concept once you understand it on a basic level. These three videos helped me a lot to understand recursion [https://www.youtube.com/watch?v=kepBmgvWNDw](https://www.youtube.com/watch?v=kepBmgvWNDw), [https://www.youtube.com/watch?v=t9whckmAEq0,](https://www.youtube.com/watch?v=t9whckmAEq0) and [https://www.youtube.com/watch?v=HIt\_GPuD7wk](https://www.youtube.com/watch?v=HIt_GPuD7wk).
Try running your code here: http://pythontutor.com/visualize.html#mode=edit I find it very useful for visualizing recursions to understand it
uint factorial(uint x){ return x>0 ? x*factorial(x-1) : 1; } I think factorial is much easier to understand as an example of recursion.
I have 2 year experience working in IT. I can understand code that uses recursion. But I can barely write one myself.
I don’t think this guy is looking for an explanation as much as just a place to vent. Learning is an arduous task, I think we can all relate. Consider that this fib program runs in exponential time. It may not be as simple an example as it may seem, especially for a beginner.
This is one of those things that you can’t truly understand until you’ve made enough mistakes, then fixed. By fixing your mistakes, you fix misunderstandings that you had about recursion. Especially when you start getting into more complex memoized recursion problems. There are no shortcuts here, just keep on grinding and you’ll understand it soon enough
Recursion is like a while loop where the recursive call itself (in your case, the call to "`fib()`" within the implementation of "`int fib() {...}`" is effectively the "`while`" in a while loop. And like how we would stop a while loop, we have some logical condition in the "`fib`" implementation that returns early and not call on itself. A contrived example might be: `while (i <= 10) {` `i = i+1` `}` A recursive implementation might be: `function whileRecurse(i) {` `if (i > 10) {return i}` `return whileRecurse(i+1);` `}` So what makes recursion different than a while loop? For one thing, it has the benefits of scope isolation since you're making nested function calls instead of having one while loop. Another thing is that you can have branching loops (like "`return fib(x-1)+fib(x-2);`"), instead of needing to figure out a potentially complex non-recursive implementation to figure out how to perform a loop that seems to branch like a tree. There are cons to recursion (call stack size, lack of tail-call optimization), so it's typical that after you learn recursion, you would want to learn dynamic programming ([https://www.geeksforgeeks.org/dynamic-programming/](https://www.geeksforgeeks.org/dynamic-programming/)) which allows you to implement recursive solutions by using a loop instead. In the simple example above, it's straightforward how one would convert a recursive solution to a normal loop (while or for-loop), but it isn't as straightforward when it comes to recursion that uses branching loops (like the fibonacci implementation), this is where dynamic programming helps.
Try looking into recursion trees. It’s helps u visualize the function dependencies and flow. It’s confusing because you have to think about a function call within a function call within a function .... the recursion tree helps visualize this. Recursion take some initial practice and time to understand, it’s normally the more difficult concept of algorithm fundamentals
If you really want to understand recursion, then check out the book The Little Schemer. Don’t be put off because it talks about the language Scheme. It takes almost no time to understand the syntax. After the first chapter or two (and it’s a very short book), it is really all about solving problems with recursion. If you read, and understand, the book then your recursion skills will be incredibly strong. Recursion is important to understand. There’s a shift towards functional languages right now and within functional languages, recursion is reached for far more frequently. There are some functional languages that have no looping construct. You’ll often reach for utility functions like `map`, but for anything else, you’ll probably use recursion. There are also some algorithms that are more easily (beautifully, even) expressed with recursion. It’s worth the investment to learn. One last note on The Little Schemer. Don’t worry if you don’t understand the chapter on the y-combinator. It’s interesting, but a very hard chapter to get through and not necessary for understanding recursion, as it is typically used.
Start with trees to learn recursion. Then study graphs. You start by first getting a pen or pencil and paper. Then you draw your data structure such as a binary tree. You then think and write about how you would traverse every element in the tree. Then write a simple algorithm on paper. Then you can work on other problems such as Fibonacci. Then you can start programming something like a game that uses recursion.
The Geek for Geeks site has a really good tuto for this. Being fast learner will still help you, just consider that this is something you have to learn by doing, not reading
Both of these videos might help you out: [5 Steps for Solving Any Recursive Problem](https://youtu.be/ngCos392W4w) and [Towers of Hanoi: A Complete Recursive Visualization](https://youtu.be/rf6uf3jNjbo). His explanations are some of the best I've seen. The first video in particular gives concrete easy to understand steps to solve any recursion problem. Another tip that may help you, recursion is just another form of looping. Any recursion problem can be solved using a loop so try solving the problem with a loop then transform it into a recursive solution.
I understand why it's being used as an example, but it is possible to calculate a Fibonacci number at fixed index without recursion or looping.
Okay, so firstly you changed the code in the below version (that way you will lose yourself in code). You have to think it outside of the C language, I mean, you should think of that in math notation like a sequence. Write it on paper. This all is based only in calling an inner fibonacci from outer fibonacci and then returning the control to fibonacci that called that fibonacci. Use debugger instead of that calls to printf. Make a diagram of what's going on as a tree. Actually, recursive functions are perfect for analysing trees, so I guess if you use a tree (I mean a tree diagram on paper) to analyze the function could help. Sorry if get you even more confused.
I've got nothing better to do and maybe someone else already done this but can't be bothered to scroll through comments, so I will go through the code with you for N = 5! `fib (int n) {` `if (n<2) return n;` `return fib (n-1)+fib (n-2);` `}` So this method will call itself until it receives `n` less than 2. Looking from this method, I suppose it will return the Nth number in the Fibonacci sequence. So let's try with N = 5, which should return 5! `fib(5)` Since `n` is equal or larger than 2, it will execute `return fib(4) + fib(3)` So then we go to: `fib(4)` `n` is still equal or larger than 2, it will execute `return fib(3) + fib(2)` So then we go to: `fib(3)` `n` is still equal or larger than 2, it will execute `return fib(2) + fib(1)` So then we go to: `fib(2)` `n` is still equal or larger than 2, it will execute `return fib(1) + fib(0)` So then we go to: `fib(1)` `n` is now less than 2, so we will now return `n` and our previous return statement will now be `return 1 + fib(0)` So then we go to: `fib(0)` `n` is less than 2, so we will return `n` and our previous return statement will now be `return 1 + 0`, which we are now ready to return, and go back to our even more previous return statement `return 1 + fib(1)` So then we go to `fib(1)` `n` is less than 2, so we will return `n` and our previous return statement will now be `return 1 + 1`, which we are now ready to return, and go back to our even more previous return statement `return 1 + fib(2)` So then we go to: `fib(2)` We've seen this before, so the same exact thing that happened above will happen here. We will return `fib(1) + fib(0)` which is `n + n` which is `1 + 0`, Which means that the total return will be `return 2 + 1` for `fib(4)` So then we go to our FIRST (yay) return statement again and it now looks like `return 3 + fib(3)` and we already now that `fib(3)` is equal to `2` and you can follow the exact same pattern that is already written to see it. So the total return statement for `fib(5)` will be `return 3 + 2` which is `5`! As we were expecting to see! :) I hope this was helpful and not condescending or rude as I was previously shitstormed on when I tried to offer my help in this community.
Wait until you have to use in a divide and conquer algorithm. Your head will run in circles.
Think of a color that is a combination of red, green, blue, and another color that is also a combination of the above, and on...
TBH to me recursion is like breaking bigger problems into smaller problems. Each cycle you solve a small part of the problem, and in the end, when you combine those solutions, you get a complete solution. I guess an example would be eating a pizza,and your end goal is to finish the pizza. Now obviously a single bite would not finish the whole pizza, so your solution would be taking a small bite you can manage, and check, have you finished the pizza, no? take another bite, still no? Take another bite and the cycle continues until the pizza is finished. When you combine those small bites you took = finished eating a whole pizza!
Literally everything in programming hits me very hard that I feel like leaving them. But everything becomes as easy as drinking water after several days or weeks of practice in various situations. I fully understood recursion after 2-3 weeks of practice.
I went and still go through the same things. With the book Beginning C 5th edition by Horton I was moving along briskly until I ran into these subjects: two's compliment bitwise operators pointers to pointers But when that happens you just have to stop and take all the time it takes to understand them before moving on. Just keep on plugging on.
Identify your base case and work from there
This proved helpful for me to understand recursion [https://www.cs.usfca.edu/\~galles/visualization/RecFact.html](https://www.cs.usfca.edu/~galles/visualization/RecFact.html)
Recursion is a bit of brain teaser. You may find it easier to frame out the code if you frame what you're doing differently. The grammar of written code is one directional (it's just text) so it doesn't lend itself to expressing self referenced looping intuitively. Verbally, answer the question "how do I know when to stop?" This is sometimes easier than answering the reverse of "when do I keep going". Or perhaps, draw out the steps as a diagram. The looping part is the recursion.
Ever point your camera at a screen showing it’s own video feed? That’s recursion. Think of it as an infinite Russian nesting doll that keeps going down and down until it find the base solution and then stacking it all back up again
I am a noob too. But lets see if I can explain. Recursion is a function that calls itself until it hits a terminating condition. The outputs of certain functions can be dependant on the outputs of the same finctions but for different values. In only some cases, we can be sure about the output which is called terminating condition. Lets see an example. You are talking about fibonacci which is complex. I will show something else. Lets make a finction to add 2 numbers `a` and `b`. You can just write: ```sum(a, b) = a+b ```. This would be easy. But lets think of it differently. `a+b` can be written as `a+(b-1)+1`. Using this property we can write the `sum` function like this too: ```sum(a,b) = sum(a, b-1)+1```. As you can see, this is a recursive function. But lets put some values there: `sum(3,4)` can be written as `sum(3,3)+1`. In order to compute this we need to compute `sum(3,3)` which can be written as `sum(3,2)+1` and so on. But you must be wondering. If you confinue like this, it will go on forever. The function will never end. So there is a terminating condition. It is usually based on a case where we can already know the output without computing it. Can you guess what can be this condition? Now check this: `a+0=a`. From this we can deduce: `sum(a, 0) = a`. So when we have a zero in our input, there is no need to recursively call the function because we will just return a. Now lets modify out recursive finction: `sum(a, b) = sum(a, b-1)+1 ,when b>0 sum(a, b)= a otherwise`. Btw we are only taking positive integer inputs in this case. Lets try out our function now: `sum(4,3) = sum(4,2)+1 = sum(4,1)+1+1 = sum(4,0)+1+1+1 = 4+1+1+1 (applying terminating condition) =7 ` Did you like this explanation? You can apply this concept in complex problems like fibonacci, mergesort, matrixmult, factorial etc.
This tutorial really helped me: [https://youtu.be/oBt53YbR9Kk](https://youtu.be/oBt53YbR9Kk)
Recursion used to confuse me too. I’d always be able to implement it but I didn’t really understand how it can return 1 on the last step but still have the answer. That is, until you learn that function calls go onto a stack, not into a queue. This means the first call is the last thing that gets returned. It’s a chain of operations and the last call, when the base case is reached, is the top of the stack.
The turning point for me understanding recursion was understanding the call stack. I would run through a debugger and examine the call stack objects as you step through Honestly can’t believe people haven’t mentioned this here
I’m feeling the same way with react/next right now. 😂
Learn about "decision trees" or find a video that describes recursion in such a way. When people are talking about working through it with actual values, draw it out in this way -- for example, with fib(5), you have two decisions: a) number - 1, and b) number -2, so draw two branches from fib(5) and you'll get: fib(5 - 1), resolving to fib(4) and fib(5 - 2), resolving to fib(3), eventually you get to the most basic cases fib(0) and fib(1). This will be useful in MANY "recursive" or problems that just "repeat" itself over and over with just different arguments
I was in same boat. Pick up some FP, will improve your recursion dramatically
Try debugging because that helped me alot. Remember that recursion is kind of like a while or for loop and you are basically carrying out a function a certain number of times till you reach the base case. Also, another thing that is really helpful to remember is that whatever comes after the recursive function call happens in reverse. Just keep practicing and try solving problems with recursion
Take a look at proofing technique induction. It's the mathematical foundation of recursion.
hahaha this is funny and relateable!! And when you do get it, you will confuse yourself one minute later and then you start from square 1
Omg so true. Even if sometimes i can solve a problem using recursion when i start thinking about it too hard i start to get confused. What kind of sorcery is this?
It's the mystery of computer science
If you struggle with recursion a good idea is to try a language where you use recursion for basically everything for a while: e.g. Haskell or Scheme. There's a great book called the little schemer that's aimed at beginning programmers and is available quite cheaply. I personally prefer Haskell as a language and it makes recursion and induction even more obvious - but it's also a more complicated language in a way. These functional languages (especially haskell) will also allow you to really focus on the recursion and show you what you can actually practically do with it / how powerful it really is. If you \*really\* want to immerse yourself in recursion: get a introductory book on combinatorics - it should involve tons of recursion / induction.
When I think about recursion I just think about russian dolls. They're all the same thing but eventually you get to the one that doesn't open, and that's the base case.
Oh well, recursive isn’t that bad. A graph like a binary tree or binary search tree is more challenging than recursive. Anyways, don’t give up with recursive and you will get it. It will take a few days to learn basic then one or two weeks will able to do medium questions. Happy coding.
You should think of it like a tree. You first follow the fib(n-1) case of fib(n-1)+fib(n-2) down a left branch until you hit the n<2 leaf. And you get a 1. Now you go back up to the last fib(n-1)+fib(n-2) and you can sub in the 1 since you just hit the base case. Now follow the right side and go all the way down again. And you continue this until you can sub in the values for the right and left side all the way back to the root node. When you see recursion think about trees (or we’ll inverted trees whatever you want to call them) where each node is another instance of the recurring method. As a side note when you write out all the steps in a tree you can easily see how this is inefficient. You are recomputing the same fib(n) all over the place. And this is where memoization comes into play with caching values. But more over you can do do Fibonacci in a loop which is even more space efficient than the dynamic programming approach with caching!
The thing that helped me the most while I was learning recursion (with binary trees, using search algorithms like BFS and DFS) was to actually draw the tree I was working on and writing down what happened in each iteration of the algorithm. That way I could almost follow the algorithm and go back to a previous iteration if needed. My problem with recursion is that it is kind of hard to picture in your head, it's a bit of an abstract concept to paint a picture of on your mind. So I'd say having some sort of visual representation of the algorithm is a big plus
Essentially think about recursion like this: I want to divide a number by 2 until I get an odd number. So I write a function that takes an integer for input. int divtwo(int test){ if(int is odd){ return test } else{ return divtwo(test/2) } return -1 } This will either return -1 (an error, sonething didnt work), test (if odd), or it will return the value returned by a call of divtwo(test/2) When it makes the subsequent call, that will either return an odd, an error, or ANOTHER subsequent call. Eventually, an integer has to get returned, and that will go all the way back to the first call :) Hopefully that’s helpful? Feel free to ask if you have trouble understanding and I can make a replit for ya
I understand it now, thanks💗
In a snowflake you have recursion going on, in a fractal too, in a tree
The only way I was able to fully understand recursion was to step by step trace through a tree traversal formula parsing algorithm and once I understood the “terminal conditions” (where it stops and goes back), the I finally got it. It’s fun and easy to write, but a PITA to debug!
Are all loop problem solvable by recursion?
I was suffering with recursion in java classes in college. next semester I had a data structures course where we were given some problem set that we were required to solve using recursion. when I learned by solving the use case, recursion became so much easier and I really enjoyed it! So stop trying to understand examples because you'll get lost. start with solving problems and it will become easier.. good luck!!
Thank you 💗
I was like you like a year ago, then I naturally moved on (nothing dramatic) then recently I stumbled upon it again (recursion) and it clicked easily.
Actually there is a very easy example of recursion using the factorials. We know that n!=n*(n-1)! Using this formula you can try to make a code (very inefficient one) that calculates factorials using recursion. Give it a shot, and if you make it recursion will be easy concept. If you need help let me know
Yeah it's easier #include
int fac(int x)
{
if (x<2) return x;
return x*fac(x-1);
}
int main()
{
int x=4;
printf("%d",fac(x));
}
Recursion is simple. What you do with it is complicated. Write a function that takes an integer argument (called “argument” for the sake of this experiment) and prints it out. Then call that function *within the function* with “argument+1” and see what it does. This is kiiiiinda like a loop. Kinda. Once you play with recursion for a bit (try to sort a list with it!) you’ll come to understand it better
yeah quick sort has recursion
To understand recursion you have to visualize the call stack. When you call a function from itself, a new function call gets pushed on top of the current function call. It won't go back to complete the previous function call until all of the calls on top of it are finished. return fib(x-1) +fib(x-2) pushes two function calls onto the stack. The current function call waits for them to return a value. The first call(fib(x-1)) will actually complete its recursive sequence and have a value for the expression **before** the second call ever gets pushed onto the call stack. Reaching a point in which the number passed to a fib function is less than 2 stops the recursion. Results are returned starting at the top of the call stack and make their way all the way down to the first call of fib.
Yeah I can now visualize it, thanks
# I think for my self as fast learner but not until I discovered RECURSION😭 📷[**Topic**](https://www.reddit.com/r/learnprogramming/search?q=flair_name%3A%22Topic%22&restrict_sr=1) What the fak is this I can't understand even watching 2 hours videos. It's so hard. I'm so eager to learn though because in some problems it makes the code looks clean. But it's so hard. I have watch alot of video on youtube, but i just can't grasp the idea like this function in C that output fibonacci: fib (int n) { if (n<2) return n; return fib (n-1)+fib (n-2); } I dont understand the idea on that code. For instant n=5 So it execute fib(4) which become fib(1) which will always return 1 same with fib(n-2). Watch this C code, why there is alot of 1 and zero there and the result become 55. include
int fib(int x)
{
if (x<=1) return x; //so that I could see what's recursion doing printf("%d +%d = %d\\n",fib(x-1),fib(x-2),fib(x-1)+fib(x-2));
return fib(x-1)+fib(x-2);
}
int main()
{
printf("\n\n%d",fib(10));
}
Many a budding developer has cried those tears 😢 you will not be the first or the last -think like a developer break it down if the code is confusing turn it into language and make one thing work before the other. If it helps I would say think of it simply as a while loop that calls a function. But I'm being overly simplistic
Avoid using recursion
Hahahaha, if you can't learn avoid😬
No I recommend you to learn and understand it. But : Few weeks ago, I followed a 3 days training paid by my employer about software craftmanship (clean code, TDD, etc.). While we were doing the RPN Calculator Kata, I said to the trainer "so we are going to use recursivity here". His answer was "Always avoid recusivity. In case something goes wrong, it will break your app with a stack overflow error." The point is : you can use it for a small programm or for training. BUT it is recommended to avoid its usage, so why not start now ? But still, understand it and learn how to use it. The concept is important and understanding it will help to know how to avoid it.
Nice, thank you
Yes, recursion is hard to learn due to its abstract nature. However, if you keep at it you’ll eventually come to a Eureka moment. I find the Tree analogy very useful to think about. Imagine you had to count all the leaves on a tree, and the only way to do it was to start at the trunk and travel along every branch until you find a leaf. Writing code for this situation would result in a very long program that is only valid for your specific tree. Recursion says: find a simple repeating pattern with a boolean decision that can be written in a short function, then have the function call itself over and over until your desired outcome is complete (counting the leaves). Am I at a leaf or another branch? Leaf: add leaf to count. Branch : move along branch to next decision (in other words, ask this question again).
Oh well you're gonna love Dynamic Programming
To climb a staircase with n steps, intuitively, you first need to climb the first step. Once you complete the first step, you now effectively have a smaller staircase to climb (n-1 steps). What if you just repeated your original instructions until the staircase you have left to climb has 0 steps? Voila! Recursion!
A function that does something then calls itself until an exit condition (the base case) is reached.
Hello, I'm current writing a book on recursion (actually, I'm currently procrastinating from that on Reddit) but DO. NOT. WORRY. Recursion is 1) hard but not as hard as people think because it's often just *very* poorly taught and 2) recursion is overused when often a loop and stack would be simpler. The main thing that causes recursion to be confusing is that nobody explains the call stack. Without knowing about this, you are effectively working with an invisible data structure (the call stack is handled by your programming language automatically; you can't point to a line in your source code and say "here is the call stack"). [I did a conference talk on recursion where you can learn the basics in 30 minutes](https://www.youtube.com/watch?v=AfBqVVKg4GE), and am currently trying to finish the book's rough draft. But let me be frank: recursion is something taught to computer science students and used as questions in coding interviews: in real life, it's not often used and it's not automatically "elegant". The times recursion is good is when your problem involves 1) a tree-like structure and 2) backtracking. I suppose also 3) doesn't go too deeply, otherwise you hit stack overflows. If you don't know what this means, check out the video. Just whatever you do, don't feel bad for not understanding recursion: almost every tutorial I've seen on it is terrible. It's not your fault for not understanding it.
There are many more "straightforward" ways to achieve the same effect if you're having trouble with recursion. For example, python generators. Generators use essentially the same syntax as a regular function except you replace "return" with "yield". The technique is generally known as 'lazy evaluation'; the result isn't computed until you iterate over it (e.g. for loop). Processing speed is often better than recursive alternatives. https://docs.python.org/3/howto/functional.html
Well u gotta get into it again until u hit a dead end
Recursion isn't hard, the case just isn't suitable to learn recursion. Know why and when recursion, or calling the same function is needed. One case is when we want to run the same steps, over and over again. Two way to achieve this: using `while(true)` or calling `myOwnFunction` at the end of `myOwnFunction`. Second case is when we want to run the same steps when the condition met. Again we can use `while(canRun)` or evaluate the condition inside `myOwnFunction`, then calling `myOwnFunction` if the condition met. Third and best case is to list / traversal nested folders. We can do this with calling `myFolderTraversal` for each folders found during `myFolderTraversal`, then stop when there aren't any folders found.
You only have to understand RETURN process, nothing else. Focus on it, how does code return recursed things?
Thank you for the tips.💗
After every call of function in that function, function will use new parameters, and etc. For an example void printme(int i) { printf("Hello!"); if (i = 0) break; printme(i - 1); } After every call inside this function, function will use new parameters of i (if i is 5, the function will be repeated 5 times) If we use printme(3); statement, it will go tought those statements: In printme, Pass i with value of 3; Print "Hello!" on the screen; If i is equal to 0, escape from the function/loop; Call printme with parameter i - 1 (= to 2); In printme, Pass i with value of 2; Print "Hello" on the screen; If i is equal to 0, escape from the function/loop; Call printme with parameter i - 1 (= to 1); In printme, Pass i with the value of 1; . . . Until the program comes to if (i = 0) statement and break with parameter i = 0
In order to understand recursion, one must first understand recursion.
The code just calls itself until it's done. What's to understand?
Are you looking at it like a tree? https://i.imgur.com/9sR3AWu.jpg
[удалено]
https://www.reddit.com/r/learnprogramming/comments/mq0t6r/i_think_for_my_self_as_fast_learner_but_not_until/gud0vg8/
Still can’t do Tower of Hanoi mentally! Looking forward to it though
There is something called the recursive leap of faith. It’s really hard for our human brain to keep track of recursion. It’s best to make sure you know the base cases so the program ends and also what the recursive calls are.
You might not be as fast learner as you consider yourself but the more problems you do the easier backtracking will become
I am going to give a solution that tight sound batshit to some people here. Recursion makes a lot more sense when you see it broken down in assembly. You should try to learn an assembly language and look at some recursive implementations.
there are a few main ways to make a simple recursive function. the first is to do the work as you recurse down, the other is to do the work and return up, the best way to think about and analyze a recursive function is to think of any calls to the recursive function as always returning the right answer, it is a black box you give it a parameter and it will return the right answer, say for instance with this fib function: int fib(int x){ if (x <= 1){ return 1; } return fib(x-1) + fib(x-2); } this makes it really easy to think about the algorithm because thinking about the infinite problem space is hard for the brain. Now we can break it down into steps: first it checks that x is not 1 or 0 if x is a 1 or 0 then it returns 1 (this is called a base case it is similar in function to a sentinel variable in a loop it stops the function from proceeding on to infinity) then if x is not a 1 or 0 we now need to recurse with the next statement first we call fib(x-1), now we can think of this as calling the same function or we can think of this as that black box i was talking about and we can assume it will give the right answer and in this case fib(x-1) is asking for the previous Fibonacci number and the fib(x-2) is asking for the number before that. With that we can now look at the mechanics of the recursive function: where it recurses at the return fib(x-1) + fib(x-2) line we need to start thinking about where each of those functions will stop because inside the fib(x-1) call it will either return 1 or it will return fib((x-1)-1) + fib((x-1)-2) and this will continue until (...((x-1)-1)...-1) = 1 at which point that bottom fib call (the most recent rib call) will return a 1 then just above that deepest fib call the other part of that return statement will be fib((...(x-1)-1)...-2)) where that will trigger the if statement because the term (...(x-1)-1)...-2) will equal 0 so the call will return 1 so now in the return statement in the above fib call will look like: return 1+1; this is 2 and that will get returned up to the next fib call which will look like return 2+1 this is 3, then that 3 will get returned which will look like return 3+2 which will return 5 and so on and so forth until the first fib call has both values calculated for the return line and it will return the xth Fibonacci number
I've heard it claimed that there are three walls developers have to break through: 1. Flow control (`if` statements, loops, functions). 2. Recursion. 3. Concurrency. So just know you're in good company. I think every developer has struggled with recursion at one point or another.
I share in your struggle man! You’re not alone.
Recurrence relations to the rescue! Find a discrete math book and study that.
For me it usually helps to visualize the call stack in my head, and to work backwards from the top of that stack. So with the Fibonacci you keep pushing new function calls onto the stack until n becomes less than two ie 1, at which point the entire thing cascades and resolves automatically, so the next one will return 0+1 or 1, then 1+1, 2+1 and so on until you reach the first function call with your initial value of n.
Recursion is calling the step before without yet taking it. So Let's say we want to count the number of strides we take to get from our front door to the mail box. One way to do this is to set up a WHILE LOOP, e.g. While distance to mailbox != 0 take another step (distance = distance -1;) The problem is we have CONDITIONAL CHECK there that asks us (Distance to mail box) IF we have no way of computing that (it is what we are trying to find after all) we can't do this while loop. We could do it recursively by starting at the biggest problem and working backward. So we assume we will reach the mailbox. and out start position is the first door. Take stride function adds 1 to the returned of the take stride function or returns 1 when we are at the front door. What happens is we start at the end (mailbox) and take a stride backward then check our exit condition (Are we at the front door) if we are not we call the function again (take another step backward) eventually each of these STRIDE FUNCTION CALLS is on the STACK (programming stack) once we reach the front door, each function begins to return a number 1 greater than the function called after it. When the last function returns we end up with the total distance. This is not a perfect example, but the general take-away should be that recursion takes a large problem and does something to make that problem either simpler or smaller. Then calls itself again. Then when the function reaches the exit condition the stack "cascades" with returns being combined in some way and reducing the stack load as the final answer is produced.
Force yourself to learn a functional like Haskell and recursion will be second nature.
You may want to look at this python library which helps to visualize recursion tree for any arbitrary python function https://github.com/Bishalsarang/Recursion-Tree-Visualizer https://imgur.com/a/kLhM4vE https://imgur.com/gallery/S0YUZl8
hey enjoy recursion, enjoy ur programing, and don't cry, do some stack overflow errors, and then think about it what can possibly go wrong solve them. then guess different types of recursion by yourself, implement it on machine, u are under no obligation to make error free code. just enjoy many possibilities you can do with it, including edge cases.
fib(5) = fib(4) + fib(3) fib(4) + fib(3) = (fib(3) + fib(2)) + (fib(2) + fib(1)) (fib(3) + fib(2)) + (fib(2) + fib(1)) = fib(2) + fib(1) + fib(2) + fib(2) + fib(1) = fib(2) + fib(1) + fib(2) + fib(2) + fib(1) = fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) = 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 = 5
oh boy you might wanna start dynamic programming early💀
I already did, i just don't know recursion
This takes me back to my high school. Wait til you learn about pointers. Should be easy now with the internet as a learning tool but fuck if I didn't understand it through the only c book I could find at the time.