Намиране на брой възли в двоично дърво (BST) - в дълбините на рекурсията...

Написах едно обяснение за това как точно работи рекурсията в една проста функция за намиране на брой възли. Нищо особено, просто "вникване на дълбоко" в изпълнението на рекурсията, която може да бъде объркваща понякога...

1. Функция за намиране на брой възли
2.  
3.     int N(node *el)
4.     {
5.             if (el == NULL) return 0;
6.             else return N(el->L) + N(el->R) + 1;
7.     }
8.  
9.     Ако имаме дървото:
10.  
11.          5
12.         / \
13.        4   3
14.       / \
15.      2   1
16.  
17.     1. Първо, извикваме функцията със стойността на корена. Т.е -> N(5);
18.     2. При N(5):
19.             - el = 5 (не е NULL), затова НЕ връщаме 0
20.             - връщаме N(el->L) + N(el->R) + 1
21.  
22.             Затова остава:
23.                     return N(4) + N(3) + 1;
24.  
25.     3. При N(4) + N(3) + 1;
26.             - разглеждаме само N(4)
27.             - el = 4 (не е NULL), затова НЕ връщаме 0
28.             - връщаме N(el->L) + N(el->R) + 1
29.             - добавяме и останалата част от предишното извикване, която е 

30. N(3) + 1

31.  
32.             Затова остава:
33.                     return N(2) + N(1) + 1 + N(3) + 1;
34.  
35.     4. При N(2) + N(1) + 1 + N(3) + 1;
36.             - разглеждаме само N(2)
37.             - el = 2 (не е NULL), затова НЕ връщаме 0
38.             - връщаме N(el->L) + N(el->R) + 1

39. - N(el->L) и N(el->R) са NULL, така че N(2) връща само 1

40.             - добавяме и останалата част от предишното извикване, която е 

41. N(1) + 1 + N(3) + 1

42.  
43.             Затова остава:
44.                     return 1 + N(1) + 1 + N(3) + 1;
45.                
46.     5. При 1 + N(1) + 1 + N(3) + 1;
47.             - разглеждаме само N(1)
48.             - el = 1 (не е NULL), затова НЕ връщаме 0

49. - връщаме N(el->L) + N(el->R) + 1

50.             - N(el->L) и N(el->R) са NULL, така че N(1) връща само 1
51.             - добавяме и останалата част от предишното извикване, която е 

52. 1 + 1 + N(3) + 1

53.  
54.             Затова остава:
55.                     return 1 + 1 + 1 + N(3) + 1;
56.  
57.     6. При 1 + 1 + 1 + N(3) + 1;
58.             - разглеждаме само N(3)
59.             - el = 3 (не е NULL), затова НЕ връщаме 0
60.             - връщаме N(el->L) + N(el->R) + 1

61. - N(el->L) и N(el->R) са NULL, така че N(3) връща само 1

62.             - добавяме и останалата част от предишното извикване, която е

63. 1 + 1 + 1 + 1

64.  
65.             Затова остава:
66.                     return 1 + 1 + 1 + 1 + 1;
67.  
68.     7. Броят на възлите е 5.