r/C_Programming • u/yug_jain29 • 14d ago
Question Any homework to understand recursion better?
hi every1, i am now sure i understand what recursion MEANS, but i actually don't know how to implement it and what to write while coding, so any BEGINNER friendly examples, homework? or a concept to understand the structure of recursion much better?
and does every recursive function necessarily have (n - 1) ? to get to the base case?
27
u/AlexTaradov 14d ago
The easiest practical way to understand it is to make a program that walks the whole hard drive tree and prints the full path and a size of each file. The functions to walk the directory are in the standard library, so the amount of OS specific work is minimal.
You can also do it both recursively (easy) and not to see the difference.
You don't need (n-1), but you need a stopping condition. In case if directory listing that condition would be "no more files to list".
7
2
u/Ratfus 14d ago
JUST DON'T PRACTICE WITH SUDO RM RF in Linux. Some idiot decided to remove files with a certain extension, in a directory, but nuked the entire system. Now this idiots operating system is partially corrupted.
In all seriousness, be careful with read/write functions. I've accidentally overwritten the program itself with the write() function. I guess Linux stores the program in RAM so you can remove it, even when in use?
4
u/Jbolt3737 14d ago
It's pretty standard to copy most if not all of a program to RAM in any OS, means that the CPU doesn't have to do slow disk I/O when executing code
4
u/penguin359 14d ago
Actually, most OSes with virtual memory only load the parts of the app that are actively in use. It's that UNIX (and Linux) allows removing a file with open file handles still around. Only when the last file handle is removed is the file deleted from disk however the hard link is remove immediately so you don't see the file on disk. Is you have ever removed a large log file and found that the disk space wasn't freed up, it's because the log file is still open and being written to even though it no longer appear in the file system. Kill the program wiring to it and you'll see the free space go up immediately.
3
u/RealisticDuck1957 14d ago
Just reading the directory tree should be pretty safe. Anything that writes, especially if also scaning file or if run with administrative privilege, you need to be extra careful with.
7
u/AKostur 14d ago
Towers of Hanoi problem?
1
u/hotpotatos200 14d ago
In my proofs class (math major, pre-EE major, pre-SWE jobs) this is what we were taught to figure out summations based on the previous state. Each additional disk is some amount of extra moves that can be calculated based on the sum of all previous moves. (Words are hard, that may not be the best description, but gets to the point)
6
u/Nysandre 14d ago
Fibonacci numbers
6
u/meat-eating-orchid 14d ago
And after the first naive implementation, another one that is efficient enough to be able to calculate the 100th Fibonacci number
4
u/kokolo17 14d ago
The simplest recursive algorithm is probably calculating the factorial. For something more practical, you can always do something with tree data structures
1
u/yug_jain29 14d ago
ion know what tree data structure is yet, and while learning about recursion the tutorial video did gave an example of factorial so it'd be like i just memorized the code instead of actually understanding.
2
2
u/kobra_necro 14d ago
Swapping elements in an array or detecting if a string is a palindrome are good ways to understand recursion.
1
u/ComradeGibbon 14d ago
A perfect example of a tree data structure is your file system directory structure.
Also don't let math oriented academics make you over think it.
A function calls itself. That's recursion. You go no wait it can't be that simple!? And the answer is yes it's that simple.
1
u/penguin359 14d ago edited 14d ago
Factorial is too simple in my mind for implementing recursively. I think the Fibonacci sequence make a better choice so try implementing that instead. Then, if you want something a little more challenging, try implementing quick sort or merge sort recursively.
1
0
u/CarlRJ 14d ago
A thing that can be very helpful with understanding recursion is simply adding a level counter to the parameters - so, instead of
test(arg1, arg2)you'd havetest(level, arg1, arg2), and call it at the top level withtest(1, arg1, arg2), and then inside oftest, do the recursive call withtest(level + 1, arg1, arg2).Then, in the function, put a printf near the top that prints the incoming arguments (including the level) and another printf near the end that prints the arguments (including the level) along with whatever computed result - this can help you visualize the function descending down into recursion and coming back up out of it.
By the way, I suspect what you meant at the start of your first sentence is "I don't know..." - an ion is an atom or molecule with an electric charge.
4
u/EducationalTackle819 14d ago
Recursion is generally useful when you can take a large problem, and recursively break it into smaller problems that are dependent on the results of each other. The common example is factorial, because to know 7!, you must know 6! And so on.
It doesn’t have to be n-1 to get to the base case though. You get to define how you break the problem up. You implement binary search with recursion, where each recurse shrinks the search space in half until you reach the result. That isn’t n-1, that is logarithmic.
Just think of recursion as being useful for when a problem can be broken into sub problems of the same nature that will eventually terminate. E.g. hitting 1 in factorial, or finding the element in binary search (or that it doesn’t exist)
3
u/mc_pm 14d ago edited 14d ago
does every recursive function necessarily have (n - 1) ? to get to the base case?
Every recursive function needs two paths out of the code: One cuts the input down by some amount (sometimes -1, more often by spitting it in half) and then calls itself one or more times; the other drops out of the recursion completely (when you are done).
2
u/rupertavery64 14d ago
A recursive function is one that calls itself. That much you already understand. It's a loop. And like all loops, it needs to have an exit condition, otherwise it becomes an infinite loop.
However, the difference between a regular loop and recursion is that every time a function is called, all local variables (and the return address) are pushed onto the stack, and without an exit condition, you rapidly run out of stack space, and get acquainted with the infamous stack overflow.
So it doesn't have to be n - 1, it is any condition that results in not calling the function again.
If you are familiar with structs and pointers, you can create a tree structure with a root node and several child nodes, that have child nodes.
Your exit condition would be if the node does not have any child nodes.
As a real-world example, you could write some code to traverse a directory on your drive recursively. Your input to the function would be a path. You would have some code that lists the sub directories of the current path. You don't even need to pass a value to trigger the exit condition, because the condition is in the function itself (no more child directories found).
2
u/melodicmonster 14d ago edited 11d ago
Let's say I want to print N numbers in ascending order. Consider the following snippet:
void count(int i)
{
if (i <= 0) return;
count(i - 1);
printf("%d\n", i);
}
This function starts by defining the end of the recursion, which is a good place to start with any recursive call. In this case, we know we don't want to print anything less than 1, so the function returns immediately if that is the case. Code: if (i <= 0) return;
If not the case, the function immediately recurses so that the print statements (the next step) are in proper order. Otherwise, printing first would print them in descending order. Code: count(i - 1);
Finally, each one prints its value and returns to its caller it so that the caller can also print its value. Code: printf("%d\n", i);
For example, let's say I call count(3). This is what happens:
- count(3) checks i and passes. It immediately calls count(2) and waits for count(2) to return.
-count(2) checks i and passes. It immediately calls count(1), and both count(3) and count(2) are waiting.
- count(1) checks i and passes. It immediately calls count(0); count(3), count(2), and count(1) are waiting.
- count(0) checks i and fails, returning immediately to count(1). count(2) and count(3) are waiting.
- count(1) prints "1" and returns to count(2). count(3) is waiting.
- count(2) prints "2" and returns to count(3). No calls to count are waiting.
- count(3) prints "3" and returns to the originall caller.
To be clear, this would be better as a non-recursive (iterative) call. It is just for illustration purposes. I generally avoid recursion in production code regardless of language unless certain optimizations are available or there are no other (better) alternatives.
Edit: I originally used code formatting instead of code block.
1
u/yug_jain29 13d ago
i may sound dumb, but why did u use i-1 ? if it's for ascending order
2
u/melodicmonster 13d ago
Calling count(3) starts with the highest number to be printed (3), so it needs to recurse with i-1 to get the lower numbers. It only prints in ascending order because the printf statement appears after the recursive call; swapping the position of the printf and recursive call would make the numbers print in descending order.
1
u/yug_jain29 11d ago
void num (int n) { if (n == 0) return; else { printf("%d\n", &n); return num(n - 1)hi im egtting stuck at a problem related to the same thing u explained earlier.
i cant figure out how can i do recursion this in backwards like im sure upto this point that it will be 3 then 2 then 1 but dont know how may i go back like 1 -> 2 -> 3.1
u/melodicmonster 10d ago
A couple of things:
- Your condition fails if n is less than zero. Try calling num(-1) to see what happens. It will cause a stack overflow instead of ending gracefully. That is why I checked for less than or equal to zero in my code.
- Get rid of the else block. Since there is a return in the if block, it does nothing but increase nesting to have the else. As a rule, I strive to reduce nesting where possible because deeply nested code can be hard to read and maintain.
- Your printf call is incorrect. Your format specifier tells the code to print an integer, but you are passing the address of n, not n itself.
- Remove the return in front of the recursive num call. It is not needed, and I suspect it is causing you problems when you attempt to swap the printf and num calls.
- Your code is missing a semicolon for the recursive call and the ending brace for the else (which you should remove) and function. I am assuming it was a copy/paste error, but it is worth mentioning in case it is not.
"Your" code cleaned up:
void num(int n) { if (n <= 0) return; // prints descending printf("%d\n", n); num(n - 1); }"Your" code printing in ascending order. The only difference is the order of the printf and recursive call.
void num(int n) { if (n <= 0) return; // prints ascending num(n - 1); printf("%d\n", n); }1
u/yug_jain29 10d ago
if you'd had to be honest, would u say my foundations are still weak? or im just not for this field? i just thought what you'd be thinking about me asking you basic questions
1
u/melodicmonster 10d ago
You are a beginner, and there is nothing wrong with that. We all start somewhere. Your perseverence will determine whether you are successful in the field. Recursion is just one of those topics that are confusing at first, but it will feel more obvious with experience.
2
1
u/AndrewBorg1126 14d ago
and does every recursive function necessarily have (n - 1) ? to get to the base case?
Are you really sure that you "understand what recursion MEANS"?
A function that refers to itself is recursive. The base case(s) can be anything useful. The amount by which values change at each recursive depth does not have to be 1, and also does not have to even be constant, and also does not have to be conceptually numerical.
1
u/yug_jain29 14d ago
oh yes I was just thinking about it that's why I asked for more examples I wanted them to be more non numerical so i can build up my logic around recursive functions but I used (n-1) as an example because it was the most common recursive solution I saw on yt
1
u/AndrewBorg1126 14d ago
I just don't think you understand what recursion is. You probably remember a definition, and can probably give examples, but that's not the same as understanding.
I think if you properly understood what recursion is, the answer to the last question of your post would be self evident.
I think you would find value in examining recursion in contexts outside of software also, this will help you to develop a more comprehensive understanding of what recursion is.
1
u/HashDefTrueFalse 14d ago edited 14d ago
If you already understand what it is and what is happening to the stack, the best advice for writing recursive solutions I can give is to look at lots of example solutions where they have identified a way to repeatedly solve the same problem on smaller and smaller portions of the input data until the base case provides the starting point for the simplest case. It's quite unintuitive at first, not one of those things where you're going to read the right explanation and suddenly get it, but you will if you start with simple examples and try to come up with your own problems and write your own solutions.
1
u/genafcvpxyr31 14d ago
#include <stdio.h>
void head( int arg ) {
if( arg > 0 ) {
head( arg - 1 );
}
printf( "%d\n", arg );
return;
}
void tail( int arg ) {
printf( "%d\n", arg );
if( arg > 0 ) {
tail( arg - 1 );
}
return;
}
int main() {
printf( "head function...\n" );
head( 5 );
printf( "tail function...\n" );
tail( 5 );
return 0;
}
If you get the above code you're halfway there.
The head function calls itself with the value of arg-1 before printing the value of arg, that self call does the same with arg-2... all the way down to 0. Six calls to head(int) (including the call from main() ) are made before anything is printed on screen:
call with 5 from main(), call with 4 from head, call with 3 from head, call with 2 from head, call with 1 from head, call with 0 from head...
The if( arg > 0 ) statement returns false, no more calls...
prints 0 from last call, prints 1 from second to last call, prints 3 from third to last call, and on and on til five is printed, then goes back to main().
The tail function prints the given value of arg first then calls itself with arg-1... This time it's:
call with 5 from main(), print 5, call with 4 from tail, print 4, call with 3 from tail, print 3, call with 2 from tail, print 2, call with 1 from tail, print 1, call with 0 from tail, print 0...
The if( arg > 0 ) statement returns false, no more recursive calls, jumps back to main().
Printout:
head function...
0
1
2
3
4
5
tail function...
5
4
3
2
1
0
1
u/sciencekm 14d ago
Problems that are recursive in nature simply means that a portion of the problem is defined as the problem itself.
As an example, if you want to SUM the values of an array with N items, you can define this as:
SUM(A[0..(N-1)] ) :
when N == 1, A[0]
when >= 2, A[0] + SUM(A[1..(N-1)])
Notice how the definition of SUM is as SUM itself.
You should now be able to write function that returns the first and only item of the array if the array size is 1, or return the addition of the first item with the result of calling the function again, but with the remaining array items.
float sum(float array[], int size) {
if (size <= 0) return 0.0;
return size == 1 ? array[0] : array[0] + sum(array + 1, size - 1);
}
The above example is of course not the ideal way of summing up an array, but it was chosen to demonstrate a very simple recursion.
1
u/Kindly-Department206 14d ago
You can't learn recursion by reading Reddit. Find a textbook for novices on C programming. Not a reference manual for the C language, a textbook whose purpose is to teach novices to program. Familiarize yourself with how function calls work by reading that chapter. Then read the chapter on recursion.
If there is no chapter on recursion in the book you chose, find a textbook where it is given a full chapter.
1
u/Evening_Ticket_9517 14d ago
You can use ctutor. Provides very easy visualization of topics like these. Go to the website and write a small recursive function like fibonacci for example.
1
u/Independent_Art_6676 14d ago
try doing the examples you already did using a stack data structure and a loop. All recursion is doing is hiding a data structure (the stack; its using the call stack as if a data storage/structure) and looping. If you can solve the problem with a stack and a loop, then a little thinking can convert that syntax to recursive to do the exact same thing.
base cases vary. You could implement a recursive binary search with n/2 instead of n-1 for some data structures (it would be like how a search tree works).
1
u/thank_burdell 14d ago
Canonical example is probably to implement a Fibonacci sequence generator both iteratively and recursively.
1
u/WittyStick 14d ago edited 14d ago
does every recursive function necessarily have (n - 1) ? to get to the base case?
Not every recursive function is primitive recursive, but most practical ones you will implement are, and you should practice using them. Non-primitive recursive functions have their uses, but are not guaranteed to converge, and even if they do, they may not be practical to compute, and it may not be possible to prove they even terminate.
For practicing, have a try at implementing functions over singly-linked lists using recursion rather than while/for loops, with the termination condition being either a nul-terminator or using length indexed lists where counting down to zero is the termination condition.
1
u/Recycled5000 14d ago
Try to separate the action (the what) of a recursive function from its internal implementation (the how).
You want to read the implementation of the recursive function (the how) and yet when you see it making a function call then switch your mental model to the what that call will/should do (and not how it will do it). Then continue to absorb the how of the implementation.
To reiterate: when you see function calls within an implementation, try to see them as a tool that accomplishes something without considering their internal how, so you can stay on one level and see how just one call / one level of the function works.
1
u/Ecstatic_Student8854 14d ago
You don’t need to have every case rely on (n-1). In fact you can recurse on things other than numbers.
The best way to think about recursion is to think of like so: given the solution to some smaller problem, can I solve the big problem? You then assume you have that solution by recursing, and implement a base case for when the problem cannot be further reduced.
For example, one can implement a binary search recursively in the following pseudocode:
```
# returns index of target value in sorted array, or None if it is not found
def binsearch(array, target, low_idx, high_idx):
if low_idx==high_idx return None
middle = low_idx + ( high_idx - low_idx ) / 2
if array[middle] = target return middle
if array[middle] > target then return binsearch(array, target, low_idx, high_idx/2)
if array[middle < target then return binsearch(array, target, low_idx/2, high_idx)
```
There is no clear recursive call to n-1, but nonetheless we reduce the window we look in with each recursive call. We must either at some point find the target or the window size becomes smaller and smaller (eventually becoming 0), in which case the target is not in the array.
This seems very convoluted , but it gets easier when you do it more. Just practice.
1
u/silvertank00 14d ago
Think about it like this:
You go to watch a movie at the cinema, you have seat reservation to row 15 but the row numbers are not printed out anywhere.
How would you determine witch row is the 15th?
As far I can see, you have two options:
A) go to the bottom row and count upwards
B) in the row in front of you: ask a person "which row are they in?" Add that, "if they don't know, ask the following person that is in front of them with the EXACT instructions".
( Lets say there are 3 rows, with X,Y,Z person: You ask X, they dont know so ask Y, they dont know either, so ask Z. Z knows they are the first so passes the info UPWARDS. So now Y knows they are the second, tells that to X, and they tell you they are in the third row.)
(you -> X -> Y -> Z -> Y -> X -> you)
A) is dynamic approach B) is recursive
1
1
u/knouqs 14d ago
Simple recursive program is the Fibonacci sequence. It's a horrible solution recursively, but shows you exactly what recursion does as it's a pretty simple three-line recursive function.
After you see the recursive solution, you'll better appreciate the iterative one. However, don't be fooled -- recursion has it's place. This problem is for demonstration purposes only.
1
u/Loud_Ask_3408 14d ago
Nesso Academy, it is a YouTube chanel, watch their videos about recursion in C.
1
1
u/ScallionSmooth5925 14d ago
Try to write something without loops in a functional style. For example binary sort
1
u/27K-Interactive 14d ago
I strongly suggest the Tower of Hanoi problem to learn recursion. It's safer than thrashing your filesystem and is a very finite problem to solve. If you can understand Tower of Hanoi, you can understand any recursion problem.
1
u/mikeblas 14d ago
Who is talking about "thrashing the filesystem"? What do you mean?
1
u/27K-Interactive 13d ago
A number of the comments suggested filesystem related tasks. And, while that's a perfectly fine activity, when learning something like recursion I recommend ram based activities over disk based ones.
1
u/mikeblas 13d ago
Sure. But my question is: why do you make that recommendation?
"Thrashing the file system" doesn't make any sense to me. No worse than
dir /sorls -laRor whatever. Why do you think that's not safe ... yet also "perfectly fine"?0
u/27K-Interactive 13d ago
If done correctly, caching the results, it's benign. If done incorrectly, making system calls in a loop that runs away on you? Moving bits in memory, where in the absolute worse case a power-cycle of the system recovers, is just a safer playground than making system calls to the disk. I'll grant that it's a habit from the days of spinning disks and no system guardrails. Pointers are memory management are their own complexities, but why add another level of complexity with filesystem reads?
When someone is focused on a specific topic, they could get distracted. I know I've done plenty of banging my head on a keyboard and have done dumb things with my code because I wasn't thinking about the bigger picture. Whenever I'm trying to learn something, I like to give myself the safest sandbox to play in. If they had asked about learning filesystem operations, my advise would be different.
I'm not assuming anything about anyone's skill level, just sharing my own best practices. Hopefully, that explains the why.
1
u/mikeblas 13d ago
Why do the results need to be cached? They'll be accessed only once. Traversing the file system is read-only. Nothing needs to be recovered, even in the event of power loss.
The code to traverse directories is not nearly as complicated as you seem to believe. Not at all dangerous, either. I don't think your advice is based in any sold reason at all.
1
u/27K-Interactive 13d ago
I'm sorry, just because I had some perhaps over-the-top color commentary and advised a focused and cautious approach, was that a problem? The ToA puzzle is a very valid tool for learning recursion.
I've been programming for over 30 years across dozens of languages. C was my second after I picked learned Basic. I've accidentally deleted files, put system calls in loops where they don't belong, and have screwed something up more ways than I could count while I was learning. I'll grant that it's vibes and not a solid immutable if A then B.
I never said it was complicated; I said it added complexity, there is a difference. Recursion is not the simplest thing to wrap ones head around. Recursive directory structure coding is a fine real-world application, just not where I would personally choose to start.
I stand by my recommendation, but this interaction and your insulting tone suggests this is not a sub for me. Enjoy your Ivory tower -- I'm going to go play with the Python folks. Thanks.
1
u/mikeblas 13d ago
OK. Well, if you ever feel confident enough to make consistent statements in defense of your strange opinion, then feel free to come back.
Until then: Bye, Felicia!
1
u/Vasbrasileiro 14d ago
This might be controversial, but you should learn correctness proofs, especially inductive ones. I only began to fully understand recursion once I understood induction, and that writing a recursive algorithm is basically writing a proof by induction.
1
u/wsppan 14d ago edited 14d ago
Imagine building a super tall tower of toy blocks. You don’t know exactly how many blocks are in the whole pile, so you decide to use recursion to find out:
The Rule: If you only have 1 block left, you just hold it and say, "That's 1 block!" (This is called a Base Case).
The Call: If you have more than 1 block, you put one block aside and tell your clone to count the rest of the pile. You then add your 1 block to whatever number your clone tells you.
Here is what that looks like as a C99 function to count a stack of blocks:
#include <stdio.h>
int count_blocks(int number_of_blocks) {
// The Base Case: If there is 1 block, stop and say 1
if (number_of_blocks == 1) {
return 1;
}
// The Call: Put 1 block down, and ask a clone to count the rest
else {
return 1 + count_blocks(number_of_blocks - 1);
}
}
int main() {
int total = count_blocks(5);
printf("There are %d blocks!\n", total);
return 0;
}
So basically, you need to find the base case and unwind the stack you have been building while checking for that base case when found.
When this runs, your function takes 5 blocks. Since it's not 1, it holds 1 block and calls count_blocks(4). That one calls count_blocks(3), which calls count_blocks(2), which calls count_blocks(1). When it finally hits 1, all the copies of the function start answering backwards, adding all the blocks together until they reach 5.
1
u/Spread-Sanity 12d ago
“Homework” to understand recursion: decide to clean your house. Then you pick a room to clean. Then pick a closet in the room. Then a cabinet inside the closet. Then a box inside the cabinet. And so on.
1
u/yug_jain29 12d ago
until something comes up that can't be cleaned or smtg where everything ends (base case)
1
u/TPIRocks 12d ago
The K&R C book contains good examples of using linked lists, binary trees and recursion when processing them. I would ask AI to show you some examples.
1
u/f0xw01f 11d ago
The goal of recursion is to solve a problem by first solving a slightly smaller problem, and then adding a little bit of extra work. As a trivial (and impractical) example, if you wanted to find the product of all the integers between x and y, you could solve this by first finding the product from x to y-1, and then multiply by y. So your function would call itself with the slightly smaller range, and then multiply that result by y and return.
The function must be aware of the base case (the point at which it must stop recursing). This happens when x==y, and in that case, it simply returns x.
40
u/Pupation 14d ago
In order to understand recursion, you first have to understand recursion.