Recursion concept

[Truman]

I'm trying to understand this concept ( by the way, don't know if will ever use it but it's in this tutorial that is really basic and I would be ashame not to learn it ) through a function:

def tri_recursion(k):
	if (k>0):
		result = k + tri_recursion(k-1)
		print(result)
	else:
		result = 0
	return result

print("\n\nRecursion Example Results")
tri_recursion(6)

with an output:

Output:
1
3
6
10
15
21

I think that I understand why output starts with 1 - because whenever execution of function comes to

tri_recursion(k-1)

it starts all over from the top of function until it comes to result 1.
Is this correct? But then, I don't get why it contiunes with 3, 6 etc.

[Larz60+]

Here's a useful example:

the display_dict function takes a dictionary, plain or nested and displays contents:
if it is a nested dictionary, it will re-curse for each level or nesting,

when this occurs, the first instance will run until it encounters a dictionary within the original dictionary.
This won't happen if the dictionary is not nested, but if it is, processing of the first instance is paused while the
second instance is processed, and then picks up after that one has finished. Best way to see this in action is to use a debugger and step through while watching the various operations occurring. If there is more than one level of nesting, it will continue until all are processed.

Think of it as entering a room, going through a door into a second, third ... and then back again.

Animals = {
    'Tommy': {'Type of animal': 'cat', 'color': 'orange', 'Age': 8},
    'Ollie': {'Type of animal': 'cat', 'color': 'black/white', 'Age': 14},
    'Gippy': {'Type of animal': 'dog', 'color': 'Brown', 'Age': 7},
}

def display_dict(thedict):
    for key, value in thedict.items():
        if isinstance(value, dict):
            print(f'{key}:')
            display_dict(value)
        else:
            print(f'    {key}: {value}')

display_dict(Animals)

output:

Output:
Tommy:
    Type of animal: cat
    color: orange
    Age: 8
Ollie:
    Type of animal: cat
    color: black/white
    Age: 14
Gippy:
    Type of animal: dog
    color: Brown
    Age: 7

[ichabod801]

Here's what happens (each indent is a level of recursion):

result = 6 + tri_recursion(5)
  result = 5 + tri_recursion(4)
    result = 4 + tri_recursion(3)
      result = 3 + tri_recursion(2)
        result = 2 + tri_recursion(1)
          result = 1 + tri_recursion(0)
            result = 0
          result = 1 + 0
          print(1)
        result = 2 + 1
        print(3)
      result = 3 + 3
      print(6)
    result = 4 + 6
    print(10)
  result = 5 + 10
  print(15)
result = 6 + 15
print(21)

[Truman]

I assume that tri_recursion(k-1) = return result so that k is each time submitted with result from previous function call.

[ichabod801]

I'm not sure I understand the question. I show the result calculation twice each time it is made in my diagram: first when the recursive call to tri_recursion is made, and a second time at the same indent when the value is returned from that call.

[Truman]

I think that I understand it. By the way, would you like to tell me what tool do you use shows step by step of that whole process?

[ichabod801]

I don't use a tool. I just typed up the diagram by looking at your code. If I have a tricky recursion that I'm having problems figuring out, I would use print lining. That's just adding print statements to your code at strategic points, which is what you were doing already.

[Truman]

I finally got it, have a clear understanding how it works ( function within a function etc...and firs result is from the last one). My brain needs a couple of days to pick up new concepts. :)

[Larz60+]

Don't lose any sleep over this, but Just keep in mind that with recursion every iteration creates an new entry in memory, so if you are dealing with Big data you may run into memory errors. This doesn't usually happen, but you will probably run across it from time to time, and need to keep it in the back of your mind so that you can recognize it.

Typical python stack frame is around 500 bytes.

There's a good writeup on this here: https://www.python-course.eu/recursive_functions.php